Study/알고리즘 & 자료구조 (10) 썸네일형 리스트형 [백준] 2294 - 동전 2 보자마자 다이나믹 프로그래밍으로 풀어야겠구나 생각했던 문제이다. n = 3, k = 7, 동전은 2, 5, 7가 있다고 가정했을 때를 살펴보자. k 0 1 2 3 4 5 6 7 동전 개수 0 inf inf inf inf inf inf inf 2, 5, 7의 가치를 가진 동전으로는 k == 1을 만들 수 없으므로 계속 inf이다. k 0 1 2 3 4 5 6 7 동전 개수 0 inf 1 inf inf inf inf inf 2의 가치를 가진 동전으로 k == 2를 만들 수 있으므로, cache[2]는 cache[2 - 2] + 1과 cache[2] 중 작은 수인 cache[2 - 2] + 1 = cache[0] + 1 = 1이 된다. 이런 식으로 cache를 채워나가면, k 0 1 2 3 4 5 6 7 동전.. [백준] 9663 - N-Queen 백트래킹 문제의 대표적인 유형인 N-Queens 문제이다. n = 4인 경우를 가정하고 문제를 풀어보면, 다음과 같은 체스판이 있을 때, 각 행 번호를 인덱스로 갖는 col 배열을 생각해볼 수 있다. col = [0, 0, 0, 0] 즉, col[i] = j 이면 i번째 행의 j번째 열에 퀸이 있다는 뜻이다. 0번째 행부터 3번째 행까지 위에서부터 순서대로 퀸을 놓아야 하는데 (탐색) 이 때, 현재 놓으려고 하는 퀸이 이전에 이미 놓은 퀸에 의해서 잡힐 위치인지 확인하고 (조건 확인) 잡힐 위치라면 탐색을 멈추고 (가지치기) 이전 단계로 돌아가서 새로운 위치에 퀸을 놓는다. (백트래킹) 이와 같은 과정을 반복하여 4개의 퀸을 놓을 수 있는 모든 경우의 수를 찾는다. 코드는 다음과 같다. # 백트래킹을 진.. 이전 1 2 다음
