Problem Solving/문제풀이 (45) 썸네일형 리스트형 [BOJ] 13306 트리 문제: https://www.acmicpc.net/problem/13306 2016 KOI 중등부 3번 문제인 트리이다. 고등부 3번과 굉장히 비슷한 문제이기는 한데, 듣기로는 고등부 3번은 HLD라는 알고리즘을 써야 한다고 알고 있는데 이 문제는 상대적으로 깔끔하게 발상의 전환을 통해 문제를 해결할 수 있다. 실제로 대회장에 갔을 때도 모든 풀이는 다 생각해 놨는데 자료구조 구현을 못해서 실패했다. 웬만하면 풀이를 보기 전에 생각을 더 해봤으면 하는 좋은 문제. 내 해법은 Union-Find Tree로 알려져 있는 자료구조 (Disjoint Set)을 구현해서 문제를 역순으로 풀어 나가는 것이다. 어떤 정점과 그 정점의 부모 정점을 제거하면 그 두 트리는 분리되게 된다. 두 정점 사이에 경로가 존재하려.. [BOJ] 11052 붕어빵 판매하기 문제: https://www.acmicpc.net/problem/11052 너무 쉬워서 자세한 설명은 생략한다. 난이도는 그냥 1/5 123456789101112131415161718192021222324252627282930313233343536#include #include #include #define INF (987654321) using namespace std; int n;int cost[1005];int cache[1005][1005]; int dp(int b, int c){ if(b==0) return 0; if(c>n) return -INF; int &ret=cache[b][c]; if(ret!=-1) return ret; int ma=0; for(int i=c;i [BOJ] 9466 텀 프로젝트 문제: https://www.acmicpc.net/problem/9466 내가 사이클에 무지하게 약하다는 것을 깨닫게 해준 문제다. 문제 자체는 특별할 게 없음에도 불구하고 이렇게 헤메는 걸 보면 망한 것 같다... 처음에 시작한 정점을 따로 체크해두고 처리하면 되는 문제였는데 코드를 좀 더 깔끔하게 짜 보겠다고 괜히 엉뚱하게 푼 것 같다. 보니까 다른 사람들도 다 이런 비슷한 방식으로 푼 것 같다. 만약 이미 사이클이 처리된 정점에 도달했다면 (색깔이 다르면) 그냥 바로 0을 반환하는 것으로 시간 초과를 막았다. 나는 개인적으로 1.75/5정도는 주고 싶은데 다른 사람들은 훨씬 쉽게 푼듯. 123456789101112131415161718192021222324252627282930313233343536.. [BOJ] 1992 쿼드 트리 문제: https://www.acmicpc.net/problem/1992 매우 쉬운 분할 정복 문제이다. 그냥 전구간이 하얀색/검은색인지 체크해서 분할하고 재귀함수로 넘겨주면 된다.사실 재귀함수에 인자를 4개 줄 필요도 없고 (핵심) 모두가 검은색/하얀색인지의 판정도 $O(n^2)$으로 미리 전처리 해두면 $O(1)$로 찾을 수 있다. 그렇지만 귀찮기도 하고 굳이 그렇게 할 이유가 없기에 생략. 가장 좋은 알고리즘은 문제를 가까스로 풀 수 있는 알고리즘이다. 코드는 다음과 같다. 좀 더럽긴 하다. 난이도는 1.25/5 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #includ.. [BOJ] 1922 네트워크 연결 문제: https://www.acmicpc.net/problem/1922 MST(최소 비용 신장 트리, Minimum Spanning Tree)를 찾는 문제로 정말로 naive하게 MST를 찾는 알고리즘을 구현해주면 된다. 나는 이 문제를 풀기 위해서 크루스칼 알고리즘을 사용했다. 지금 생각해 보니 좀 많이 이상하지만 정보올림피아드를 이제까지 준비하면서 단 한번도 MST를 사용하는 문제를 풀거나 코딩해 본적이 없었다. Union-Find (코드에서 DisJointSet)을 좀 쉽게 구현할 수 있게 되니까 비로소 알고리즘을 이해할 수 있었다. 난이도는 1.5/5 정도인 것 같고 코드는 아래와 같다.1234567891011121314151617181920212223242526272829303132333435.. [BOJ] 1931 회의실배정 문제: https://www.acmicpc.net/problem/1931 그리디 알고리즘의 대표주자 회의실배정이다. 사실 다 아는 문제니까 그냥 넘어가도 되겠지 이러면서 이제까지 한번도 구현을 안해봤는데, 채점해보니까 처음에 틀렸다 ㅡㅡ 풀이 방법은 가장 끝나는 시간이 빠른 회의, 만약 같다면 시작을 더 빨리 하는 회의부터 그리디하게 선택하는 것이다. 끝나는 시간이 빠른 건 끝나는 시간이 빠를수록 더 많이 회의를 진행할 수 있으니까 그렇다고 쳐도 대체 왜 시작을 더 빨리 하는 회의부터 선택하는지는 잘 몰랐었는데 틀리고 나서 생각해 보니까 (7,8), (8,8) 등의 회의가 존재하면 두개를 다 먹을 수 있더라. 구현은 간단하게 STL sort를 이용해서 정렬했다. 아직도 sort를 사용자 정의 함수로 정렬.. [BOJ] 1005 ACM Craft 문제: https://www.acmicpc.net/problem/1005 위상 정렬의 대표격인 건설 순서 문제이다. 그런데 사실 난이도가 아주 없는 문제는 아니어서 이게 왜 1005번에 있나 조금 의심이 들기는 하는 부분이다. 사실 습격자 초라기에 비할 바는 못되지만... 하여튼 내 풀이를 설명하자면, DFS를 이용해 그래프를 순회하면서 함수가 종료할 때마다 저장하면 위상 정렬의 역순이 된다는 점을 이용해서 DP를 돌리는 방법으로 문제를 풀었다. 이를 위해서 순방향 간선과 역방향 간선의 인접 리스트를 별도로 만들었고, 역방향 간선의 인접 리스트의 크기가 0인 것들을 모두 DFS 돌리고 reverse해서 위상 정렬을 찾은 다음 그걸 역방향 간선 인접 리스트를 통해 바텀업 DP로 돌려서 결과값을 찾아냈다. .. [BOJ] 2439 탑 문제: https://www.acmicpc.net/problem/2493 2009년 초등부 지역본선 4번, 고등부 지역본선 2번 문제이다. 그만큼 난이도도 매우 쉬운 스택 문제기는 한데 처음 보면 스택 문제가 아니라고 생각할 수도 있을 거라 생각한다. 풀이는 다음과 같다. 이 문제를 푸는 가장 적절한 알고리즘은, 왼쪽부터 탑의 높이를 차례대로 보면서 스택의 맨 위와 비교해서, 스택의 수가 더 클 때까지 pop하고 그 때 숫자를 출력하는 것이다. 굉장히 단순하기 짝이 없지만 제대로 동작하는 알고리즘이다. 대략적으로라도 증명을 해보자. 1. 이 알고리즘을 썼을 때 원래 부딪혀야 하는 곳보다 왼쪽에서 부딪히는 경우는 없다.원래 부딪혀야 하는 것보다 왼쪽에서 부딪혔다고 가정해 보자. 스택에서 pop을 할 때 원.. 이전 1 2 3 4 5 6 다음