Problem Solving 썸네일형 리스트형 BOJ 16236 - 아기 상어 문제 링크(Link)https://www.acmicpc.net/problem/16236 문제 해결(Solution) 반복적인 BFS와 Sort를 이용해서 문제를 해결한다. 단, 구현이 까다롭다. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 생각해야하는 조건 : 이 문제는 생각해야하는 조건들이 많다. 그 중 가장 까다로운 것이 '어떤 물고기를 먹을 것인가?' 다. 이는 vector를 이용해서 쉽게 해결할 수 있다. vector를 해서 거리, row, col 순으로 저장하면 단순한 sort함수를 통해서 다음에 먹을 물고기를 쉽게 찾을 수 있다. 2. 시간 복잡도는? : 인접행렬로 구현했기 때문에 BFS는 N^2, sort() 함수를 사용했기 때문에 정렬은 NlgN. 그러므.. 더보기 BOJ 4792 - 레드 블루 스패닝 트리 문제 링크(Link)https://www.acmicpc.net/problem/4792 문제 해결(Solution) MST를 두 번 생성해서 문제를 해결할 수 있다. 1. min_blue : R 간선을 우선으로해서 MST를 만들었을 때, 포함되는 B 간선의 개수 2. max_blue : B 간선을 우선으로해서 MST를 만들었을 때, 포함되는 B 간선의 개수 3. Answer : min_blue 더보기 BOJ 9084 - 동전 문제 링크(Link)https://www.acmicpc.net/problem/9084 문제 해결(Solution) DP로 문제를 해결한다 1. DP[n][m] : n번 째로 입력받은 동전에서 금액이 m일 때의 방법의 수 (TOP-DOWN) 2. DP[m] : 금액이 m일 때의 방법의 수 (BOTTOM-UP) 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 왜 TOP-DOWN 방식과 BOTTOM-UP 방식일 때의 DP table의 차원 수가 다를까? : BOTTOM-UP 방식일 때는 이중 for loop을 사용해서 동전 조합의 중복을 막을 수 있지만, TOP-DOWN 방식은 동전 조합의 중복을 막기 위해선 입력받은 동전의 순서를 저장해야한다. 그러므로 TOP-DOWN의 DP.. 더보기 BOJ 14863 - 서울에서 경산까지 문제 링크(Link)https://www.acmicpc.net/problem/14863 문제 해결(Solution) DP로 문제를 해결한다(DP table에 따라서 달라지는 수행 시간 비교). 1. DP[n][flag][limit] : n번 째 지점 n+1번 째 지점으로 이동 중 flag(0 : 도보 이용 , 1 : 자전거 이용)면서 소요 시간은 limit일 때의 최대 모금액. 2. DP[limit] : 소요 시간이 limit일 때의 최대 모금액. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 어떻게 3차원 DP table을 1차원으로 줄일 수 있을까? : 항상 최종 목적지에 도착할 수 있는 조건과 1번 지점부터 N번 지점까지 차례로 이동한다는 점과 어느 교통 수단을 이.. 더보기 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) - ※ 정확하.. 더보기 BOJ 9322- 철벽 보안 알고리즘 문제 링크(Link)https://www.acmicpc.net/problem/9322 문제 해결(Solution) 1. 제 1 공개키와 제 2 공개키의 순서를 저장하고 처리하는 자료구조에 관한 문제. 2. ① 문자열을 인덱스로 저장하면서 동시에 자동 정렬이 되지 않는 자료구조인 'unordered_map'을 사용.② 제 1 공개키의 순서를 저장하는 배열(order)을 사용.③ 제 2 공개키가 주어지면, ②에서 사용한 배열의 값을 인덱스로 사용해서 답을 저장하는 배열(answer)을 사용. ex) 제 1 공개키 : "I AM HAPPY" 제 2 공개키 : "AM HAPPY I" 암호문 : "LOVES HER HE" - unordered_map(first==string, second==order) : { {.. 더보기 BOJ 1103 - 게임 문제 링크(Link)https://www.acmicpc.net/problem/1103 문제 해결(Solution) 1. DP를 이용해서 문제 해결한다. 2. 사이클이 존재 여부를 확인하는 bool 배열을 만들어서 확인한다. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. main함수 외에서 프로그램을 강제 종료할 수 있는 exit 함수를 사용. exit의 매개 인자에 0이면 정상 종료, 그 외의 값은 비정상 종료임을 알린다. 2. 사이클의 존재 여부를 확인하는 쉬운 방법. ① 처음 vertex에 방문했을 때, 방문했음을 체크(chk[row][col]=true)한다.② 상하좌우 이동한다. (이 행위는 다른 문제에선 다르게 응용될 수 있다) ③ 언체크(chk[row][col].. 더보기 BOJ 2206 - 벽 부수고 이동하기 문제 링크(Link)https://www.acmicpc.net/problem/2206 문제 해결(Solution) 1. BFS의 응용문제. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 만약 벽의 좌표를 모두 저장한 후, 하나씩 부수며 BFS를 하면 시간복잡도 O(NM(N+M))이 되므로 시간 초과를 받을 수 밖에 없다. 2. 보통은 2차원 배열을 이용해서 문제를 해결하지만, 이 문제는 3차원 배열을 이용하면 단 한번의 BFS를 통해서 답을 구할 수 있다. 3. dist[i][j][k] = (i, j)에서 k가 1이면 벽을 만나서 부수고 이동, k가 0이면 벽을 만나면 이동 불가. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 2 3 4 ··· 9 다음