문제https://www.acmicpc.net/problem/9465 사용 알고리즘DP 풀이고려사항이전 열(다른 행)의 스티커 가중치가 현재 가질 수 있는 스티커 가중치의 최대인지 후기이 문제의 keypoint는 행이 2개로 고정되어 있으며 점수는 음수가 아닌 것이다.점수가 음수가 아닌 이상 이전 2칸 이상을 고려하지 않아도 된다.처음에는 현재 열이 j이면 0 ~ j-2까지의 리스트 전체에서 max값과 이전 열의 다른 행을 비교했다.하지만 이건 불필요한 작업이였고 다른 행의 이전 2개만 비교하면 된다.그 이전은 이후에 가중치가 음수가 아니기 때문에 하나라도 더 선택하는 것이 큰 값이 되기 때문이다. 코드import sysinput = sys.stdin.readlineT = int(input())for t..

문제https://www.acmicpc.net/problem/2638 사용 알고리즘BFS 풀이고려사항1. 치즈와 맞닿은 공기가 외부 공기인지2. 외부공기와 2면 이상 닿아있는지 후기1. 이 문제의 keypoint는 초점을 치즈가 아닌 외부공기로 두어야한다는 것이다.처음 치즈에 초점을 두고 푸니 맞닿은 공기가 외부인지 내부인지 확인하는 것이 어려웠다.처음에 행을 기준으로 처음과 마지막 치즈 사이에 있는 공기를 내부라고 체크하려 했으나아래 그림과 같이 에서는 가능하지만 과 같은 상황에서 문제가 발생하였다.2. 또한, bfs 알고리즘을 활용하여 코드를 작성 할 때 visited를 사용하여 이미 온 곳을 관리하는데visited에 방문한 적이 있다고 무조건 가지 않는 것이 아닌 점 역시 고려해야 한다.처음에는 방..

문제https://www.acmicpc.net/problem/14226 사용 알고리즘BFS 풀이1. visited 관리- 현재 스티커의 갯수 뿐만 아니라 클립보드에 있는 스티커 수 별로도 시간이 달라지기 때문에 2차원 배열로 관리- 이미 방문한 곳을 계속 방문하지 않기 위해 사용2. bfs- 동일한 가중치를 가지는 그래프에서 최단 경로를 찾는 데 유리- BFS는 보통 모든 경우를 탐색하기 때문에, 경우의 수가 많을 때는 비효율적일 수 있지만, S의 최대값이 1000이므로, BFS로 충분히 해결 가능하다고 판단+ heapq 를 사용한 다익스트라 알고리즘은 가중치가 다른 경로에서 최단 경로를 찾을 때 사용+ 이 문제에서 각 연산은 동일한 비용(1초)을 가지므로, 다익스트라보다 BFS가 더 간단하고 효율적이라..