코딩테스트 준비 (35) 썸네일형 리스트형 C++ 백준 11066 (파일 합치기) 백준 11066 (파일 합치기) https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 전형적인 DP식 문제이다. 문제들을 풀면서 느낀 점인데 뭔가 문제를 보고 딱 떠오르는 알고리즘이 없으면 구현/DP인 것 같다. 설명 2차원 DP를 선언한다. dp[i][j]는 i부터 j파일까지 합쳤을 때 최소비용이다. 그렇게 되면 d[i][i] = 파일 i의 크기가 될 것이다. 아이디어는 다음과 같다. i~j까지의 파일을 합치는데 해당 파일들이 합쳐지기 전.. C++ 백준 11054 (가장 긴 바이토닉 부분수열) 백준 11054 (가장 긴 바이토닉 부분수열) https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net LIS를 이용하는 문제이다. 또한 LIS의 길이만 알면 된당. LIS의 길이에 대한 설명은 여기(링크)에 자세히 나와있으니 꼭 알고오자. LIS의 길이를 구하는 방법은 O(N^2)과 O(NlogN)로 구하는 두 가지의 방법이 있는데 본 글에서는 O(NlogN)방법을 이용한다. O(N^2)으로도 해봤는데 속도가 확실히 차이가 나는 것을 볼 수 있다. 밑에꺼가 O(N^2)이.. C++ 백준 20171 (Dessert Cafe) 백준 20171 (Dessert Cafe) https://www.acmicpc.net/problem/20171 20171번: Dessert Café Your program is to read from standard input. The input starts with a line containing two integers, n and k (3 ≤ n ≤ 100,000 , 1 ≤ k ≤ n), where n is the number of candidate sites and k is the number of apartment complexes. The candidate sites are n www.acmicpc.net 일단 N개의 노드에서 항상 N-1개의 간선이 주어지므로 스패닝트리로 볼 수 있다. 이 문제.. C++ 백준 2270 (하노이 탑) 백준 2270 (하노이 탑) https://www.acmicpc.net/problem/2270 2270번: 하노이 탑 첫째 줄에 정수 n(1≤n≤100,000)이 주어진다. 둘째 줄에는 세 정수 a, b, c가 주어진다. 이는 차례로 1, 2, 3번 막대기에 꽂혀 있는 디스크의 개수이다. 이는 0이상 n이하이며, a+b+c=n이다. 다음 3개의 줄 www.acmicpc.net 기본 하노이탑 문제 응용버전이다. 하노이탑 기본문제 (1~N까지 차례로 쌓인 탑을 다른 rod로 옮기는 문제)는 여기(링크)에 있다. 꼭 이해하고 오자. 1~N까지의 차례로 쌓인 탑을 옮길때는 2^N-1만큼의 횟수가 소요된다고 했다. 그렇다면 탑이 차례로 쌓여있지 않고 뒤죽박죽 섞여있을 때는 어떻게 될까? 이 문제가 바로 그것이다... C++ 백준 11729 (하노이 탑 이동순서) 백준 11729 (하노이 탑 이동순서) https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 하노이 탑은 유명한 문제지만 막상 구현 과정은 꽤 어렵다. 문제에서는 1~N까지 쌓여있는 하노이탑을 특정 rod로 옮기는 것이기 때문에 가장 기본적이 하노이 탑 문제라고 할 수 있다. 설명 1~N까지 차곡차곡 쌓여있는 탑을 어떻게 다른 탑으로 옮길까? 하노이 탑의 특성상 위에 놓일 탑은 아래에 있는 탑보다 항상 크기가 작아야 하기 때문에 꽤 복잡.. C++ 백준 1707 (이분 그래프) 백준 1707 (이분 그래프) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프(Bipartite Graph)에 대해 모른다면 구글링을 통해 알고오자! 그러나 문제에 자세한 설명이 쓰여져 있다. 설명 이분 그래프를 쉽게 설명하자면 인접한 노드끼리는 서로 다른 집합에 속해있어야 한다. 집합에 속해있다.. 유니온 파인드? 아니다. 집합의 개수가 두개밖에 없기때문에 유니온파인드를 쓸 필요는 없다. 그냥 DFS나 BFS를 돌면서 인접한 노드.. C++ 백준 5430 (AC) 백준 5430 (AC) https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net deque를 이용해 풀 수 있는 문제였다. deque에 대한 이해가 없다면 구글링을 해서 알아오도록 하자. 또한 입력이 [1,2,3]과 같이 숫자만 주어지는게 아니기 때문에 이를 처리하는 과정이 살짝 귀찮았다. 설명 수열을 저장 후 뒤집기와 pop을 반복하는 문제였다. 그러나 뒤집기를 할 때 algorithm헤더파일에 존재하는 reverse함수를 쓰게 될 경우 이 함수는 O(N)의 시간복잡도를 갖기 때문에 시간초과가 날것이라는 생.. C++ 백준 14003 (가장 긴 증가하는 부분수열5) 백준 14003 (가장 긴 증가하는 부분수열5) https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net LIS의 길이와 수열을 O(N*logN)안에 해결해야 하는 문제이다. LIS에 대한 기본이해와 O(N^2)의 시간으로 길이와 수열을 찾는 법, 그리고 O(N*logN)의 시간으로 LIS의 길이만을 찾는 방법은 아래에 있으니 반드시 모두 이해하고 이 글을 읽도록 한다. 1. LIS의 길이를 O(N^2)으로 구하는 방법 :.. 이전 1 2 3 4 5 다음
