본문 바로가기

전체 글

배낭 문제(knapsack problem) 배낭 문제(knapsack problem) 12865번 - 평범한 배낭 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 1.. 더보기
세그먼트 트리 세그먼트 트리가 필요한 상황 세그먼트 트리는 [1,2,3,4,5,6,7,8,9]와 같은 수열이 있을 때, 주어진 수열의 부분 수열들에서 특정 값(ex. 최댓값, 최솟값, 총 합)을 빠르게 알고 싶을 때 사용하는 자료구조다. 예를 들어, [1,2,3,4,5,6,7,8,9] 수열의 두번째부터 다섯번째까지의 부분수열 총합을 구하면 2 + 3 + 4 + 5 = 14다. 이 값을 구하기 위해서는 두번째부터 다섯번째까지 모두 값을 하나하나 더해야 한다. 부분집합의 길이가 m이라고 한다면 시간복잡도는 O(m). 이러한 연산을 자주 하는 상황이 발생할 때 매번 부분집합의 길이만큼 연산을 하는것은 비효율적이다. 일반적으로 자주 발생하는 연산을 줄이는 방법은 자주 발생하는 연산의 결과를 저장해 놓는것이다. 하지만 n길이의.. 더보기
Quick Hull Quick Hull 볼록 껍질(Convex Hull) 볼록 껍질이란 주어진 점들을 모두 포함하는 가장 작은 볼록 집합이다. 위의 그림과 같이 주어진 점들 이어 볼록 집합을 만들 수 있다. '볼록'껍질인 이유는 위와 같이 움푹 들어간 모양이 나오지 않아야 하기 때문이다. 볼록 껍질의 내각은 항상 180도 보다 작아야 한다. 볼록함을 만족시키지 않는 점은 볼록 껍질을 만드는 점들의 집합에 포함시키지 않는다. Quick Hull Quick Hull은 볼록 껍질을 만드는 점들의 집합을 구하는 알고리즘 중 하나다. 위의 애니메이션이 Quick Hull Algorithm의 과정을 보여주고 있다. (출처: https://en.wikipedia.org/wiki/Quickhull) 우선 Quick Hull은 두 점을 이.. 더보기
투 포인터 투 포인터 1806번 - 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 수열의 첫번째 값을 두개의 포인터가 가르키고 있는 상태로 시작한다. 위의 예제에서는 5로 시작하고 5만 포함 된 부분 수열의 합은 5이다. 부.. 더보기
최소 스패닝 트리(MST)와 크루스칼 알고리즘 최소 스패닝 트리란? 최소 스패닝 트리를 요약하면 간선마다 비용이 정해져 있을 때, 최소 비용으로 모든 노드를 연결한 트리 라고 할 수 있다. 최소 스패닝 트리 예제 1647번 - 도시 분활계획 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결.. 더보기
Union-Find Union-Find 알고리즘 회고 글에서 나열해놓은 순서대로 글을 작성하려 했지만, 오늘 본 코딩테스트에서 Union-Find 문제가 나왔는데 사소한 실수를 끝까지 못찾아 시간을 낭비했다. 그래서 반성하는 의미로 Union-Find를 먼저 정리하려고 한다. Union-Find Union-Find 알고리즘을 사용하는 이유는 매우 간단하다. 요소들을 정해진 규칙에 따라 그룹을 나누었을 때, A 요소와 B 요소가 같은 그룹에 속하는지 쉽게 알기 위한 알고리즘이다. 조금 더 정확히는 그래프 구조에서 같은 그룹에 속하는 지 빠르게 알기위해 필요한 알고리즘이다. GROUP_A = [1,2,3] GROUP_B = [4,5,6] GROUP = { 1:'A', 2:'A', 3:'A', 4:'B', 5:'B', 6:'B'.. 더보기
위상정렬 위상정렬 알고리즘 내가 풀었던 위상정렬 알고리즘 문제들 2623번 - 음악 프로그램 2252번 - 줄 세우기 1766번 - 문제집 2623번 - 음악 프로그램 문제 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 &#39;뮤직 KOI&#39;에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다. 그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다. 1 4 3 6 2 5 4 2 3 첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서.. 더보기
외판원 순회 문제(Traveling Salesman problem) 외판원 순회 문제 2098번 - 외판원 순회(https://www.acmicpc.net/problem/2098) 다이나믹 프로그래밍 비트마스킹 비트필드를 이용한 다이나믹 프로그래밍 외판원 순회 문제 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. .. 더보기

티스토리툴바