BOJ 12841 - 정보대 등산 문제 링크(Link)https://www.acmicpc.net/problem/12841 문제 해결(Solution) DP로 문제를 해결한다. 1. DP[n][chk] : n번 째 지점에서 chk(0 : 횡단 보도를 건너지 않았다 , 1 : 횡단 보도를 건넜다)일 때, 최소 이동거리. 시간 복잡도는 O(N)이 된다. 3. DP를 구하는 과정이 전체 시간을 결정하므로, 전체 시간 복잡도는 O(N)이 된다. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 횡단 보도는 한 번만 건널 수 있다. 그 때, 어디를 건너야하는 지도 구해야하는 게 조금 까다로울 수 있다. 전역 변수로 vector를 선언한 후, i번 째 횡단 보도를 건널 때가 건너지 않을 때보다 거리가 작거나 같으면 ve.. 더보기 BOJ 1949 - 우수 마을 문제 링크(Link)https://www.acmicpc.net/problem/1949 문제 해결(Solution) Tree를 구현한 후, DP로 문제를 해결. 1. 주어지는 그래프 관계를 트리로 구현한다. 시간복잡도 O(N)이 소요된다. 2. DP[N][Q] : 마을 N에서 Q(0 : 우수 마을로 선정하지 않음, 1 : 우수 마을로 선정)일 때, 우수마을의 인원의 최대 합. 시간복잡도 O(N)이 소요된다. 3. 전체 시간 복잡도는 O(N)이 된다. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. DP의 시간복잡도를 계산하는 것은 생각보다 어렵다. O(N)이라고 적었으나, 사실 그 보단 더욱 많은 시간이 소요된다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언.. 더보기 BOJ 4179 - 불! 문제 링크(Link)https://www.acmicpc.net/problem/4179 문제 해결(Solution) BFS를 응용한 문제. 지훈이가 아무리 돌아다녀도 미로를 넘어서는 계속해서 이동할 수 없으므로, 시간복잡도는 O(R*C)이다. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 사람과 불의 이동에 대해서 잘 생각해야한다. 같은 시간에 불과 사람이 같은 곳에 도착한다면, 사람이 그 곳을 지나갈 수 없다고 생각해야햔다. 즉, 불의 우선순위가 사람의 우선순위보다 높다고 생각해야한다. 2. 불의 좌표를 다루는 queue와 사람의 좌표를 다루는 queue를 별개로 관리한다. 그 과정에서 우선순위를 생각해 불의 이동을 우선으로 한다. 참고(Reference) - ※ 정확하.. 더보기 이전 1 2 3 4 5 6 7 8 ··· 32 다음