본문 바로가기

알고리즘 풀이

 (50)
(공통문제) n-queens 공통문제로 backtracking의 대표 문제인 n-queens 가 선택되었다. n-queens 를 예전에 답을 본적이 있지만, 역시나.. 이번에도 답을 봐버렸다.이참에 확실히 정리하고 넘어가는 것이 좋을 것 같아, 최대한 자세하게 풀이를 적을 것이다. (내가 이해할 수 있도록) backtracking 이란?backtracking 이란 어떤 노드의 유망성(promising)을 점검한 뒤, 유망하지 않다면 해당 노드의 부모노드로 돌아가(backtracking) 다음 잣기 노드에 대한 검색을 계속 진행하는 과정의 방법이다.(출처 - http://emzei.tistory.com/223 ) n-queen 문제가 무엇인지에 대해선.. 다른 곳에 자세히 나와있으니 그걸 보도록 하고, 문제를 풀기위해선 상태공간 트리..
백준 2292번 벌집 https://www.acmicpc.net/problem/2292 위 문제를 보다보니.. 벌집이 생성 될 때 규칙을 찾을 수 있었다. 첫번째 육각형의 최대 값은 1두번째 육각형의 최대 값은 7세번째 육각형의 최대 값은 19네번째 육각형의 최대 값은 37다섯번째 육각형의 최대 값은 61 즉, 1 7 19 37 61... 순으로 증가하는 셈인데, 여기에 -1을 해주면0 6 18 36 60 으로 6의 배수가 되는 것을 알 수 있었다. 첫째항은 0 * 6 = 0두번째항은 1 * 6 = 1세번째항은 3 * 6 = 18네번째항은 6 * 6 = 36다섯번째항은 10 * 6 = 60이므로, 앞자리 곱셈의 규칙을 찾아내면 되는 것이다. 앞자리의 0 1 3 6 10 의 규칙은 이전 항에서 1 2 3 4 씩 증가되고, 이는..
백준 2163번 초콜릿 자르기 https://www.acmicpc.net/problem/2163 이번 문제는.. 좀 어려운 줄 알았는데, 그렇지 않았다.간단하게 풀이를 말하자면 N * 5 초콜렛이 있을 때, N번 가로로 형태로 하여 초콜릿을 자르면 5칸 짜리 초콜렛이 N줄이 생기게 된다.이 후, 5칸 짜리 초콜렛을 모두 1칸으로 만들면 되는 것이다. 1번째줄 4번2번째줄 4번3번째줄 4번 ... N번째줄 4번이라 생각하며 식을 세우면서 풀고 있었는데.. 가만히 생각해보니2 * 3 초콜릿은 = 5번3 * 3 초콜릿은 = 8번10 * 20 초콜릿은 = 199번 즉, 초콜릿의 너비 - 1 만큼이 최소횟수가 되는 것이다... #include using namespace std;int main(){ int n, m; cin >> n >> m ..
(공통문제) 지그재그 배열 #include #include using namespace std; int* getStartPos (int _startPos, int _n) { int x, y, moveRow, moveCol; int *info = new int[5]; switch (_startPos) { case 1 : info[0] = _startPos; info[1] = _startPos; info[2] = 1; info[3] = 1; info[4] = true; break; case 2 : info[0] = _n; info[1] = _startPos; info[2] = -1; info[3] = 1; info[4] = true; break; case 3 : info[0] = _n; info[1] = _n; info[2] = -1..
백준 1965번 상자넣기 https://www.acmicpc.net/problem/1965 이번 문제를 풀 땐 n번째 마다 최대로 넣을 수 있는 상자를 계산하는 것으로 점화식을 구성하였다. 즉, num[n] = n번째에서 가장 최대로 넣을 수 있는 상자의 수 가 된다.이것을 기준으로, n번째 상자에 왔을 때 (n-1, n-2, n-3, ... 1)번째 상자를 탐색하면서n번째 상자가 n-1번째 상자보다 크면, num[n]을 비교하여 최대값을 갱신해주면 된다. 그리고 처음에 num[n] = 1 로 초기화 시켜준 것은 상자의 배열이 9 8 7 6 5 라면 답은 1이기 때문이다.(간단하게 말하면, 어느 자리에서든 상자에 최소 1개를 넣을 수 있다는 뜻이다.) #include #include #define MAX 1000using nam..
백준 2178번 미로탐색 https://www.acmicpc.net/problem/2178 이 문제에서 도착지점에 도착할 수 있는 최소의 칸 수가 답이라하여, cmath 의 min 함수를 사용할 필요는 없다. 왜냐하면 특정 (n, m) 좌표에 도착할 때는 항상 최소값을 가지기 때문이다. 위의 사항을 주의하고 기본적인 dfs 알고리즘을 적용시키면 답을 도출시킬 수 있다. #include #include #include #pragma warning(disable:4996)using namespace std;int main(){ char map[101][101]; int row, col, d[101][101] = {0, }; int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; cin >> ..
백준 2156번 포도주 시식 https://www.acmicpc.net/problem/2156 처음 문제를 접했을 땐, 월요일(20일)에 풀었던 계단 오르기와 동일한 규칙인 것으로 생각했었다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 하지만, 문제의 조건 중에 '선택하면' 이란 단어를 보고 다른 문제라는 것을 알게되었다. 왜냐하면 계단오르기는 n 번째 계단을 무조건 밟는 것이기 때문에, dp 배열마다 n번째 계단의 값을 더하였기 때문이다. for(int n = 2 ; n n번째 포도주 시식 여부dp[n][2] : n-2 단계에서 -> n번재 포도주 시식 여부로 설정하였다. 각 column 별로 확인하면, dp[n]..
백준 1912번 연속합 https://www.acmicpc.net/problem/1912 이 문제는 그저께 계단 오르기처럼 점화식을 세우기 보단.. 예시 입력으로 부터 규칙을 찾아내려 하였다. 10 10 -4 3 1 5 6 -35 12 21 -1 처음엔 실수 했던 것이, 양수만 모두 더하는 경우만 생각하였었다.즉, 위 예제에서 2번째는 음수(-4)이므로 더하지 않고, 3번째(3) ~ 6번째(6)까지만 더한 값만을 고려한다거나, 12 + 21만 고려한다거나 하는 경우만 생각했다. 위 예제에선 운 좋게 답은 맞았을 지 몰라도, 12와 21이 1과 2라면 답은 달라지게 된다. 10 10 -4 3 1 5 6 -35 1 2 -1그 이유는10 -4 +3 +1 +5 +6 = 21인데,10 -4 +3 +1 +5 +6 = 15이기 때문이다.처..

티스토리툴바