본문 바로가기

전체 글

 (78)
[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..
[알고리즘] 최소 스패닝 트리 최소 스패닝 트리 (Minimum Spanning Tree, MST)는 모든 정점을 연결하면서 가장 작은 가중치를 가지는 트리를 만드는 알고리즘이다. 트리를 만드는 알고리즘이므로 이 그래프는 사이클이 없는 DAG 형태여야 한다. 이 문제를 해결하는 데에는 두 가지 알고리즘이 대표적으로 사용되는데, 바로 크루스칼 알고리즘과 프림 알고리즘이다. 일단은 크루스칼 알고리즘을 설명한 뒤에 프림 알고리즘을 구현할 때가 되면 그때 와서 추가해 놓겠다.크루스칼 알고리즘 크루스칼 알고리즘은 모든 간선 중 가장 가중치가 작은 간선부터 차례로 연결시키는데, 만약 새로 연결하는 간선 때문에 사이클이 생긴다면 그 간선을 포기한다. 원리도 굉장히 간단하고 구현도 굉장히 간단하다. 근데 Greedy한 알고리즘 답게 증명은 간단하지..
[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을 할 때 원..
[BOJ] 1011 Fly me to the Alpha Centauri 문제: https://www.acmicpc.net/problem/1011 그냥 노가다로 규칙 찾는게 증명하는 것보다 빠르다.결국은 수열 길이가 있을때 하나씩 증가/감소/유지되는 수열의 길이가 n이 되는 경우가 있느냐... 찾는 문제인데예를 들어서 수열 길이가 7이라고 하면 1 2 3 4 3 2 1 이런 식으로 이동하는 것이 최대라는 것은 자명하다.그런데 만약에 이렇게 7번의 이동으로 16의 거리를 이동했으면 그 이하의 거리는 모두 이동할 수 있을까? 당연하다.항상 수열에서 가장 큰 원소를 하나 줄이면 그 원소는 절대로 다른 원소와 2 이상 차이가 나지 않게 만들수 있는 것을 너무 간단히 증명할 수 있다.수열 $a_1, a_2, a_3, ... , a_n$ 이 있다고 하자. 만약 $a_k$가 최대 원소라고..

티스토리툴바