https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 분리 집합(Disjoint Set): 교집합이 존재하지 않는 두 개 이상의 집합. 구분해야 하는 데이터 집합을 다룰때 사용함. 분리 집합은 보통 Union-Find 알고리즘을 사용하여 트리 구조로 구현한다. Union-Find 알고리즘 1. make_set(x) -> x원소를 유일하게 갖고있는 집합을 생성. 2. union(x, y) -> x가 속한 집합과..

1. P class 입력에 대한 다항시간(polynimial time)에 해결가능한 결정적인 알고리즘을 P class 문제라고 한다. 결정적인 알고리즘은 특정한 값에 대해 정해진 값이 나오는 알고리즘. 2. NP class 입력에 대한 다항시간에 해결가능한 비결정적인 알고리즘을 NP class 문제라고 한다. 비결정적 알고리즘은 동일한 입력이 주어지더라도 매번 다른 과정을 통해 다른 결과를 도출하는 알고리즘. 즉, 운에 따라 다항시간에 해결할 수도 있는 알고리즘들을 뜻한다. 보통 답에 대한 '힌트'가 주어질 때 해당 힌트를 사용하여 다항시간 내에 답을 검산할 수 있는 알고리즘을 NP class 문제라고 하기도 한다. {-2, 10, 6, -5, -3} 이라는 집합이 있을 때 이 집합의 부분집합 중 원소의..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 해밀턴 경로: 그래프의 모든 정점을 한 번씩만 방문하는 경로. 해밀턴 순환: 시작점과 끝점이 같은 해밀턴 경로, 해밀턴 순환을 구하는 문제는 NP문제에 속한다. 외판원 순회는 이러한 해밀턴 순환중 간선의 합이 최소가 되는 루트를 구하는 문제라고 볼 수 있다. 완전 탐색(브루트포스) 방법으로 값을 구할 수 있지만 그렇게 되면 n! 시간이 소요되므로(n개의 숫자에..

https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 이전에 풀었던 컵라면 문제와 맥락이 비슷한 그리디 문제다. https://djgameprogramming.tistory.com/47 1. 주유소들을 위치 기준으로 오름차순 정렬해준다. 2. 현재 연료로 갈 수 있는 주유소들의 연료의 양을 우선순위 큐(내림차순)에 전부 삽입한다. ->우선순위 큐의 top은 현재 갈 수 있는 주유소 중 가장 연료를 많이 주는 주유..

https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 입력받은 순서에서 최장 증가 부분 수열(LIS)를 찾으면 되는 문제다. LIS은 수열의 부분 수열 중 각 원소가 이전 원소보다 큰(오름차순) 수열 중 그 길이가 가장 긴 수열을 의미한다. 최장 증가 부분 수열에 속하는 숫자를 제외한 나머지를 이동하는 것이 문제의 해답이다. LIS은 다이나믹 프로그래밍 기법으로 찾을 수 있다. DP에 저장되어야 하는 정보는 그 지점까지의 LIS의 길이를 저장해주고 탐색할때..

https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 1. 배송 정보들을 받는 마을 기준으로 오름차순을 해준다.(받는 마을이 같다면 보내는 마을 기준) 2. 각 마을에서 박스를 얼마나 싣고있는지 저장할 리스트를 생성한다. 3. 2번의 리스트를 배송 정보의 시작지점~(끝지점-1)까지 탐색하여 얼마나 더 실을 수 있는지 탐색한다. 4. 더 실을 수 있다면 빈 공간과 비교하여 배송 정보의 박스값을 결과값에 추가한다. 5. 추가한 박스값..

1. 코드 영역 실행할 프로그램의 코드가 저장되는 영역. CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리함. 2. 데이터 영역 프로그램의 전역 변수와 정적(static) 변수가 저장되는 영역. 프로그램의 시작과 함께 할당되며 종료될때 같이 소멸함. 3. 스택 영역 함수가 호출될때 해당 함수의 지역 변수와 매개 변수가 저장되는 영역. 함수가 완료되면 같이 소멸함. 스택 영역은 메모리의 높은 주소(아래)에서 낮은 주소(위) 방향으로 할당되므로 후입선출(나중에 들어온 것이 먼저 나옴)의 방식으로 데이터를 관리함. CPU에서 관리하며 크기가 정해져있음. 코드 영역, 데이터 영역, 스택 영역은 컴파일 단계에서 메모리 공간을 할당받으므로 '정적 할당'에 해당한다. 하지만 스택 영역은 함수가 호출될때마다 ..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 무게 M과 가격 V인 보석과 허용 무게가 C인 배낭들이 여러개 주어진다. 이때 각 배낭에 보석을 한 개씩만 넣어서 넣은 보석들의 가치가 최대가 되도록 해야한다. 해당 문제는 각 상황마다 최대 가치를 지니는 보석을 최대한 적은 허용량을 갖는 배낭에 넣는 방법으로 그리디하게 풀 수 있다. 하지만 모든 보석에 대하여 모든 배낭을 선형탐색하게 ..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 왼쪽에서 오른쪽까지 연결되는 최대한 많은 경로를 구해야한다. 가는 방법은 오른쪽 윗방향 대각선, 오른쪽, 오른쪽 아래방향 대각선 세 가지 DFS를 사용하여 맨 끝에 도달한다면 탐색을 멈추어 나머지 가지에 대한 탐색을 하지 않도록 한다. 이차원 배열을 하나 더 사용하여(Visit) 이전에 탐색했던 부분은 추가로 탐색하지 않도록 해야한다. ↗→↘ 순으로 탐색하여 최대한 위쪽으로 경로를 찾도록 해야 함. 이렇게 하면 ..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 단순 DFS로만 알고리즘을 짜게되면 시간초과가 발생하게 된다 이전에 목표까지 도달했던 경로를 저장하여 추후 재도달시 바로 목표까지 도달한다고 판단하는 다이나믹 프로그래밍 기법을 사용해야 한다. #include #include using namespace std; int x, y; // input int Matrix[500][500] = { 0, }; // 경로를 가짓수로 저장(DP) int Ch..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 단순 2차원 다이나믹 프로그래밍 문제라고 생각할 수 있지만 메모리 제한이 4MB다. 2차원 다이나믹 프로그래밍을 사용하면 int형 2차원 배열만 해도 거의 4MB에 근접하므로 메모리 제한을 해결하기 위해선 1차원 배열을 사용한 다이나믹 프로그래밍 기법을 사용하여야 한다. 일단 2차원 배열을 사용하여 다이나믹 프로그래밍이 어떻게 돌아가는지 생각해보자. 0 1 2 3 4 5 6 7 8 9 10 0 1 ..

다음과 같이 두 클래스를 작성하였다. A클래스는 int형 변수 'number'가 존재하고 생성자에서 0으로 초기화한다. print 가상함수는 A라는 것을 보여주고 number를 출력한다. B클래스는 A클래스를 상속한다. 생성자에서 number를 5로 초기화한다. print 가상함수를 오버라이딩하여 B라는 것을 보여주고 number를 출력한다. 두 클래스에 대한 코드와 출력 결과는 이렇게 나타난다. a는 A클래스 객체다. number는 0으로 초기화됐고 A와 number(=0)를 출력하였다. b는 B클래스 객체다. number는 5로 초기화됐고 B와 number(=5)를 출력하였다. B클래스는 A의 자식 클래스이므로 B = A이다. A 클래스의 객체 AFromB에 B 클래스의 객체를 넣을 수 있다. 이때 ..