문제https://www.acmicpc.net/problem/9663 사용 알고리즘백트레킹 풀이1. 퀸은 상, 하, 좌, 우, 대각선을 원하는 만큼 갈 수 있다. 여기서 '상하, 좌우, 대각선' 3가지로 나눠서 확인하였다.2. 상하 - 한 줄에 퀸 한 개씩 놓으며 백트레킹을 진행하였다. 좌우 - 한 열에 한 개의 퀸만 가능하기 때문에 index에 관한 딕셔너리로 관리하였다. 대각선 - 해당 줄(i)에 매칭 되는 값을 리스트에 넣어 관리하였다. 대각선의 경우 일정한 비율로 증가, 감소하기 때문에 (한 줄 전에 것은 열의 값이 +1 또는 -1 -> 즉, x줄 전의 값은 y+x 또는 y-x) x1 - x2와..

문제https://www.acmicpc.net/problem/2116 사용 알고리즘구현, 브루트포스 풀이고려사항1. 가장 처음 주사위의 바닥 눈이 얼마인지2. 쌓인 주사위의 위, 아래에 6 또는 5가 사용되었는지 후기1. 이 문제의 keypoint는 주사위가 위, 아래만 주어지면 나머지 네 면은 돌릴 수 있다는 것이다.때문에, 위, 아래 어떠한 숫자가 사용되었는지 확인 후 그것을 제외한 가장 큰 수를 찾으면 된다. 2. 이 문제에서 변경되는 것은 첫 주사위의 바닥에 있는 숫자 뿐이다.이외의 값들은 다 이 숫자에 따라 맞춰진 값이지 추가적으로 변경할 것이 없어 DFS를 사용하지 않아도 된다.따라서전체 경우의 수 = 바닥에 놓일 수 있는 면의 경우의 수(6) * 주사위 갯수(N)만큼 진행하게 된다. 3. ..

문제https://www.acmicpc.net/problem/1446사용 알고리즘DP 풀이고려사항1. 지름길 관리 방법2. 바로 전에 길에서 온 값과 현재 길에 적혀있는 값 비교3. 현재 지점에서 갈 수 있는 지름길 탐색 후기1. 이 문제의 keypoint는 지름길 사용 유무에 따른 값 갱신이다. 2. 현재 위치에서 가지고 있는 값과 이전 값에서 오는 값을 비교하여 갱신을 진행한다.일반 도로 이동 → dp[cur] = dp[cur-1] + 1    - 지름길을 사용하지 않고 이전 길에서 오는 것 : 이전 값에서 1km 더 온 것으로 "이전 값 + 1"현재 위치에서 최소값 → dp[cur]     - 지름길로 온 값 : 이미 출발점에서 온 값으로 갱신 되어 있는 값 3. 이후 현재 위치에서 갈 수 있는 지..

문제https://www.acmicpc.net/problem/1535 사용 알고리즘0/1 Knapsack 풀이고려사항1. 현재 부분 집합 기준에 인사 가능한 체력이 있는지2. 인사 가능하다면, 인사 할지에 대한 여부 확 후기1. 이 문제는 조건의 N이 20 이하이며, 체력은 100 미만이라는 작은 범위로 인해Brute Force, 백트레킹, 0/1 Knapsack 모두 사용이 가능하다.하지만, 가장 효율적인 방법으로 0/1 Knapsack을 적용하여 풀었다.Brute Force : $ O(2^{N}) $Knapsack : $ O(100 * N) $ 2. 이후, 코드느 기본 Knapsack 코드와 동일하다. 코드import sysinput = sys.stdin.readline# 총인원N = int(inpu..

문제https://www.acmicpc.net/problem/12865 사용 알고리즘0/1 Knapsack 풀이고려사항1. 현재 부분 집합 기준에 기준 물건이 들어갈 수 있는지2. 들어갈 수 있다면 현재 부분 집합에 기준 물건을 넣을지 여부 후기1. 이 문제는 배낭문제(0/1 Knapsack)의 가장 기본 틀이다.2. 물건을 하나씩 차례로 기준을 잡으며 그 때, 무게 별 부분 집합을 만들 때의 경우를 확인한다.이때, 먼저 해당 물건만 담을 때도 그 무게에 벗어나는지 여부를 확인한다.무게에 벗어나면 담지 못하고,무게에 벗어나지 않는다면 담을지 여부를 판단한다. 3. 배낭 문제의 가장 기초 문제이기 때문에 연습해보기 좋은 문제였다. 코드import sysinput = sys.stdin.readline# 물품..

문제https://www.acmicpc.net/problem/16493 사용 알고리즘0/1 Knapsack 풀이고려사항1. 현재 부분 집합 중 최대 페이지 수인지 후기1. 이 문제의 keypoint는 현재 부분 집합을 기준으로 해당 챕터를 넣을지 여부를 선택하는 것이다.챕터를 나눠 담을 수 없기 때문에 0/1 knapsack 알고리즘을 적용했다.조건이 작기 때문에 시간복잡도 상 브루트포스 알고리즘 적용해도 풀리지만, 효율적인 방식을 위해 0/1 knapsack 알고리즘을 적용했다. 2. 소요 시간을 늘려가며 부분집합을 만든 후해당 챕터를 기준으로 소요 시간이 초과되는 지 확인한다.이후, 초과 될 경우 넣지 않고,초과 되지 않을 경우 넣는 것과 넣지 않는 것 중에어떤 것이 더 많은 페이지 수를 가지게 될 ..