문제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. 소요 시간을 늘려가며 부분집합을 만든 후해당 챕터를 기준으로 소요 시간이 초과되는 지 확인한다.이후, 초과 될 경우 넣지 않고,초과 되지 않을 경우 넣는 것과 넣지 않는 것 중에어떤 것이 더 많은 페이지 수를 가지게 될 ..

문제https://www.softeer.ai/practice/6275  사용 알고리즘구현, 시뮬레이션 풀이고려사항1. 출발점, 출발방향 찾기 - 연결된 곳이 1개인지2. 다음 방향 설정 후기1.이 문제에서는 출발점 탐색과 경로 이동 두 로직으로 나뉜다.2. 우선, 출발점은 현재 위치에서 상하좌우를 살피며 이어진 곳이 1곳인지, 2곳인지 확인하여 찾는다.이어진 곳이 1곳인 경우 출발점으로 시작한다.이때, 이어진 곳의 방향을 함께 확인하여 출력한다.3. 이후 경로 이동을 진행하는데 앞으로 전진 시 2칸씩 이동한다.이때, 2칸씩 이동하더라도 다음 방향 탐색은 1칸을 기준으로 진행해야한다.#.#과 같이 앞으로 진행은 안되지만 돌아서 2칸 앞에 놓인 곳을 지나가게 되는 경우가 존재하기 때문이다.처음에는 2칸을 기..

문제N과 M(9) : https://www.acmicpc.net/problem/15663N과 M(10) : https://www.acmicpc.net/problem/15664N과 M(11) : https://www.acmicpc.net/problem/15665N과 M(12) : https://www.acmicpc.net/problem/15666 사용 알고리즘Backtracking 풀이후기1. 이번 시리즈의 keypoint는 중복되는 숫자 처리이다. N과 M 시리즈 1(1 ~ 4)와 로직이 비슷하나 동일 숫자의 중복 처리가 더해져 조금 더 까다로웠다.2. 백트레킹 유형을 통해 중복 수를 활용한 순열과 조합 등의 방식을 직접 구현 할 수 있었다. 15663. N과 M (9) 1. 이 문제가 이후 문제 풀이에..