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 클래스의 객체를 넣을 수 있다. 이때 ..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 재귀를 이용한 백트래킹 알고리즘 문제다. Queen은 행, 열, 대각선을 공격할 수 있으므로 새 Queen을 놓을때 기존의 Queen의 공격범위와 겹치지 않는지 판단해야 한다. 행에 대해선 무조건 각자 다른 행에 놓도록 한다. i번째 퀸은 i행에 놓도록 함. 이를 통해서 2차원 배열이 아닌 '열'의 정보값만 저장하는 1차원 배열을 사용하여 문제를 해결할 수 있다. 열은 간단하게 배열의 앞부분을 탐색해주면 된다. ..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 재귀함수 호출을 이용한 백트래킹 알고리즘이다. 백트래킹은 모든 경우의 수를 탐색함과 동시에 가망이 없는 경우의 수에 대해선 탐색을 미리 끝내버리는 방법이다. N과 M 문제는 1~N 범위의 자연수 중 M개의 자연수를 중복없이 고르는 문제다. M개의 자연수를 고르기 위해선 중복 for문을 돌린 뒤, 중복되는 수가 없는지 판단하면 되겠지만 N과 M 범위가 커질수록 기하급수적인 연산을 요구하게 될 것이..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 그래프의 신장트리에서 최장거리를 구해야하는 내용이라 다익스트라라고 생각하기 어려웠다. 다익스트라 알고리즘은 분명 두 버텍스 사이의 최단거리를 구하는 알고리즘이지만. 알고리즘의 내용 자체는 특정 버텍스를 기준으로 연결된 모든 버텍스의 최단거리를 구하게 된다. 즉, 다익스트라 알고리즘을 사용한 뒤, 각 버텍스까지의 거리를 저장한 리스트를 선형탐색하면 탐색한 버텍스의 수와 가장 먼 버텍스까지의 거리도 도출..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 쉬운 동적 프로그래밍 기법인데 너무 빙빙 돌아서 생각했다; i번째 계단에 도착하는 방법은 2가지 1. i-2번째 계단에서 2계단을 한 번에 올라온다. 2. i-3번째 계단에서 2계단을 한 번에 올라와 i-1번째 계단으로 온 후 i번째 계단으로 한 칸 올라온다. 점화식으로 정리하면 이렇게 된다 DP[i] = max(DP[i-2] + Stair[i], DP[i-3] + DP[i-1] + Stair[i]) i-2번..