그냥 하는 노트와 메모장

* BOJ 1176 섞기[분류 - 다이나믹 프로그래밍] [요약] 인접한 사람들의 키 차이가 K초과가 되도록 N명을 배치하는 방법의 수를 구하자 [풀이]1. 이미 i명이 조건에 맞게 서있다고 가정해보자. 이 상태에서 한명을 뒤에 추가하려고 한다. 이때 i명은 조건에 충족하게 이미 서있기 때문에, i명 배치에서 가장 뒤에 있는 사람과 추가할 사람의 관계를 따져 K초과가 될 수 있는지 확인하면 된다.2. 먼저 몇명이 이미 서 있을 때, 맨 뒤에 설 사람을 정한다.3. 다음으로 그 뒤에 누굴 세울지를 정해서 조건에 맞다면 경우의 수를 셈해주면 간단하게 해결할 수 있다. #include #include using namespace std; const int MAX_N = 16; int main() { int N,..

* BOJ 1797 균형잡힌 줄서기 [분류 - 정렬, 그리디] 1. 브루트포스로 계산하기에는 O(N^2)은 시간적으로 부담이되기에 일단 x축을 기준으로 정렬한다. 2. x좌표가 작은 값에서 큰 값으로 순회를 시작하는데, 여자면 -1을 할당하고 남자면 1을 할당하여 누적합을 구한다. 이 때 순회하다가 이전에 나왔던 누적합(bef)이 존재한다면 현재와 bef를 비교하여 x좌표가 얼마나 차이가 있는지 계산한다. 이 값 중에 가장 큰 값을 출력해주면 된다.※ 이 때 누적합이 최초로 등장한 값만 저장해주면 된다. 문제에서 요구하는 것은 x 간격이 가장 큰 것을 원하므로 임의의 누적합이 어디서 최초로 등장했는지를 저장해두고 나중에 다시 이 누적합이 나오면 그것이 곧 최대 간격의 후보를 의미한다. #include #..

* BOJ 3032 승리[분류 - 다이나믹 프로그래밍] 원형 다이나믹을 많이 풀어봤다면 비교적 쉽게 느껴질 문제입니다. [풀이] 1. 1부터 N까지 각각을 첫 번째 수로 보고 진행한다. 2. 고를 수 있는 수가 최대 두 개가 되는데, 이 때 어떤 것을 골라야 필승인지를 검사하는 로직을 추가한다. 즉, 상대가 무조건 지는 경우가 있는지 탐색한다. 현재 골라야하는 플레이어는 골라야하는 수의 구간으로 알 수 있으며 그 때까지 선영이가 선택한 홀수의 개수를 저장해두었다가 모든 수를 다 사용했을 때, 누가 승리하는지 판단하도록 구성해주면 된다. dp[l][r][c] = 선영이가 c개의 홀수를 얻었고, 현재 플레이어는 l번째 수 또는 r번째 수를 선택할 수 있을 때의 승리 가능성 #include #include c..

* BOJ 12103 짝합 수열, 7976 수열 [분류 - 다이나믹 프로그래밍] 1. [패턴] 0또는 1을 요소로 길이 k를 갖는 패턴 배열을 생성해보자. 대신 합이 짝수이어야 한다. 패턴의 의미는 해당 위치가 1이면 홀수 0이면 짝수를 의미한다. 2. [규칙성] 임의의 배열을 생성했다면 마지막 요소 이후의 것을 생각해보자. 만약 길이 k를 가지는 패턴이 처음에 0으로 시작한다면 그 다음 인덱스부터 k길이가 합이 짝수이기 위해서는 다음 요소(k+1번째)는 0일 수밖에 없다. 마찬가지로 1로 시작해도 그 다음 요소는 1일 수 밖에 없다. 결국 길이 k마다 처음에 정했던 패턴이 계속 나올 수 밖에 없고, 이 패턴 중에 주어진 배열 a를 패턴에 적용했을 때 가장 적은 비용으로 바꾸는 것을 찾으면 된다. 예시)..

* BOJ 15807 *빛*영*우*[분류 : 다이나믹 프로그래밍] [풀이] 좌표 (X, Y)에 대한 2차원 다이나믹을 생각해보자.dp[x][y] = (x, y) 좌표에 대한 빛의 세기 1. 영향력 당연히 y좌표가 낮은 곳에 설치된 조명들은 상대적으로 y좌표가 높은 곳에 있는 부분에 영향을 미칠 수 있다. 2. 기울기 조명에 대해 존재할 수 있는 기울기는 두 개밖에 없다. y=x와 y=-x. 3. [조명] 현재 좌표에 조명이 설치 되어 있다면 그 조명 수만큼 추가해준다. [같은 직선 위] 현재 좌표 (x, y)에 해당하는 dp[x][y]를 구하기 위해서는 (x, y)를 포함하고 기울기가 1이거나 -1인 것을 생각해보자. y값이 현재보다 작은 모든 조명에 대해 같은 기울기를 가지며 같은 직선 상에 있는 것을..

* BOJ 3948 홍준이의 친위대[분류 - 다이나믹 프로그래밍] [풀이] 만족하는 나열은 두 종류가 존재한다. 작큰작큰 또는 큰작큰작. 1. 상태를 dp[작큰인지 큰작인지][수열을 구성하는 인원수]로 둔다. 2. 현재 인원수 i명 계산할 때 인원수 i-1명에서 가장 키가 큰 인원을 넣는다고 생각하자. 이 가장 큰 인원을 기준으로 왼쪽에 설 인원, 오른쪽에 설 인원을 정해보자. 왼쪽에 있을 인원들의 수가 짝수라면 시작을 큰작으로 시작할 수 밖에 없다. 반면 오른쪽에 있는 인원들은 무조건 작큰으로 시작하면 된다. 여기서 왼쪽에 배치할 인원을 골라보자. i-1명중 j를 고르게 될텐데, 중요한 점은 어느 j명을 골라도 무조건 j명 배치가 가능하다는 점이다(모두 서로 다른 키를 가지고 있음). 따라서 i-1명 ..

* BOJ 2112 두 부분 문자열, BOJ 3244 두 부분 문자열2[분류 : 다이나믹 프로그래밍] 1. B문자열에 대한 모든 가능한 문자 26개에 대해 위치를 오름차순으로 저장하자. 어떤 문자가 특정 위치 b를 포함한 이후에 존재하는지 안하는지 판단하기 위함이다. 2. 다이나믹 상태 최대 공통 부분 수열(LCS)을 찾는 것처럼 생각해보자. 현재 A의 위치 a, 현재 B의 위치 b로 상태 (a, b)에서 문제에서 요구하는 문자열의 길이를 찾아보자. 1. A[a] 문자를 정답 문자열에 사용하지 않는다. 이 때는 a위치를 한 칸 이동한다. b는 움직이지 않는다. 여기서 b를 움직여버리면 구조상 B 부분 문자열을 모두 확인할 수 없게 된다. 2. A[a] 문자를 정답 문자열에 사용한다. 2-1. A[a]에 ..

* BOJ 5580 빙고 게임[분류 : 다이나믹 프로그래밍] [풀이] 똑같은 빙고라는 의미는 어떤 수열을 나열하여 빙고에 체크할 때 의미가 같으면 안된다는 소리. 따라서 행과 열을 뒤집은 빙고판은 의미적으로 같게 된다. 결국 문제는 집합 {A| 1

* BOJ 3026 V[분류 : 다이나믹/ 가지치기] [풀이] 컷팅이 중요한 문제. 1. X가 10^5보다 크거나 같은 경우 A=1, B=10^11인 최악의 경우에서 X의 배수를 구할 때 10^6의 연산수가 필요해요. 이 경우엔 충분히 브루트포스로 계산이 가능합니다. 2. X가 10^5보다 작은 경우 최악의 경우를 생각해봅시다. X = 1, A = 1, B = 10^11이라면 브루트포스로 최대 10^11번을 계산해야하기 때문에 시간초과가 날 것임이 자명합니다. [다이나믹] 자리수로 생각해봅시다. 수가 최대 10^11이므로 12자리가 자리수 최대가 됩니다. 관찰포인트는 인접한 자리수 간의 관계입니다. X=151이고 현재 10^3의 자리수를 구해야한다고 해봅시다. 이 때 1의 자리, 10의 자리 그리고 10..