본문 바로가기

CS/Algorithm90

[Programmers][C++] 43165 타겟 넘버 [Programmers][C++] 43165 타겟 넘버 문제 https://programmers.co.kr/learn/courses/30/lessons/43165 풀이 풀다보니 코드가 지저분하네요ㅠㅠ. 재귀를 이용해서 숫자 사이 사이에 + 나 -를 넣어줍니다. 백트레킹을 이용해 같은 자리에 두가지를 넣고 재귀를 돌려요. 결과값이 들어가는 string의 길이가 numbers.size의 2배가 되었을 때 계산해줍니다. 이 때 타겟 수와 계산 값이 일치하면 result값을 올려줍니다. 코드 #include #include using namespace std; int iter; int res = 0; int calc(string calc_res) { int num_res = 0; for (int i = 0; i.. 2019. 1. 31.
[BOJ][C++] N-Queen [BOJ][C++] N-Queen 문제 https://www.acmicpc.net/problem/9663 풀이 크기가 N X N인 체스판에 N개의 퀸을 공격할 수 없게 배치합니다. 저는 체스를 모르기 때문에 퀸의 이동 방향을 찾아보고 풀었습니다. 퀸의 공격 범위는 상, 하, 좌, 우, 대각선이 가능합니다. 즉, 퀸 하나를 배치하면 퀸이 있는 행과 열은 다른 퀸을 놓을 수 없습니다. 또한 대각선에도 놓을 수 없습니다. 그렇기 때문에 굳이 2차원 배열을 만들 필요 없이 1차원 배열에 퀸이 있는 row를 입력받으면 됩니다. 하나의 col에는 하나의 퀸만 들어가야 하고 N만큼 for문을 돌면서 퀸을 놓고 앞서 놓은 퀸을 공격할 수 있는지 판단하면 됩니다. 앞서 놓은 퀸들을 공격할 수 없으면 재귀로 그 다음 퀸을.. 2019. 1. 17.
[BOJ][C++] 1987 알파벳 [BOJ][C++] 1987 알파벳 문제 https://www.acmicpc.net/problem/1987 풀이 (0,0)에서 시작하여 알파벳 중복이 되지 않도록 이동을 합니다. 이 때, 이미 이동한 칸은 지나갈 수 없고 말이 최대 몇 칸을 이동하는지 구하는 문제입니다. 모든 경우를 매번 따져보는 것은 효율적이지 않기 때문에 현재 위치에서 이동시키고 돌아오도록 코드를 짰습니다. 코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int R, C, res = 0; char map[20][20]; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; vector alphabet; int now.. 2019. 1. 17.
[BOJ][C++] 15683 감시 [BOJ][C++] 15683 감시 문제 https://www.acmicpc.net/problem/15683 풀이 이 문제에서는 감시 카메라마다의 모든 방향 경우를 정한 뒤 감시 영역을 체크하는 방식으로 풀었습니다. 구조체를 활용하여 0과 6이 아닌 CCTV의 수를 입력받을 때 마다 구조체에 정보를 담아 vector에 넣어주었습니다. 그 후 이 벡터를 방향 정하는 알고리즘으로 넘겨줍니다. 벡터 내의 CCTV를 모두 돌아주면서 방향을 정해줍니다. 이 때, 재귀를 활용하여 모든 경우의 수를 따질 수 있도록 설계합니다. cnt 변수로 몇 번째 CCTV의 방향을 체크중인지 확인합니다. 모든 CCTV의 수와 cnt가 일치하면 방향에 따른 감시 영역을 체크하는 함수로 넘어갑니다. 감시 영역을 체크한 뒤 사각지대의 .. 2019. 1. 17.

티스토리툴바