그냥 하는 노트와 메모장

* BOJ 2543 초고속철도[분류: 다이나믹 프로그래밍] [풀이] 인접한 로봇끼리는 반드시 통신이 가능해야 한다는 점을 유심히 보자. 만약 어떤 로봇 a가 b, c, d, w와 겹치는 상황을 생각해보자. 1. [a에 설치하는 경우] 나머지 b,c,d,w,에 설치할 수도 있고 안할 수도 있다. 2. [a에 설치하지 않는 경우] b,c,d,w에 모두 통신을 설치해야만 한다. [순서도] 1. 먼저 구간 시작 좌표를 기준으로 로봇들을 정렬하자. 정렬하는 이유는 시작 좌표가 낮은 로봇을 기준으로 설치하느냐 마느냐를 결정하여 이후에 있는 로봇에 영향을 미치는 데에 있어 계산하기 용이하기 때문이다. 2. 오름차순으로 방문하며 현재 p번째 로봇에 대해 통신장비를 설치할지말지를 결정해야 한다. 3. 설치한다면 p번째 ..

* BOJ 2888 상범 게임[분류 : 다이나믹 프로그래밍, 구현] [풀이] 구현이 꽤 까다로운 문제. 간단하게 일차원부터 시작해보자. 1. [일차원 - 같은 문자가 딱 두 개] 그 인덱스 차이가 점수가 된다. 2. [일차원 - 같은 문자가 세 개 이상] 점수를 계산할 때 중복해서 셈하면 안된다. 즉, 인덱스 i와 인덱스 j가 같은 문자라면 i에서 j까지의 거리 또는 j에서 i까지의 거리 둘 중 하나만 계산하면 된다. 따라서 편의상 인덱스가 증가하는 순으로 방문하며 이전에 나왔던 같은 문자가 어디에 있었는지를 저장하여 진행하면 된다. 문제는 얼마나 먼 지를 계산할 때 인덱스 자체를 저장하기엔 부담스럽다. 따라서 누적합과 그때까지의 개수를 셈하여 진행한다.(예시) SMMMSSM 에서 S 점수를 구하는 경우..

* BOJ 4384 공평하게 팀 나누기[분류 : 다이나믹 프로그래밍] [풀이] N/2명을 배치하면 나머지 N/2+N%2명은 자동으로 배정된다. 따라서 N/2명이 가능한 점수를 모두 구한 뒤 이를 전체 총합에서 뺀 값과의 차이를 최소화하면 되시겠다. 동전 교환 문제처럼 생각해보자. i번째 사람을 추가하면서 1~N/2명팀을 구성할 때의 값을 구한다. N/2명의 점수 총합의 최대값은 최대 인원수 / 2 * 인원당 최대 점수로 계산 가능하다. 계산해보면 알겠지만, 수 자체가 배열에 담기에 충분히 작기 때문에, i번째 사람을 추가할 때 i-1번째 사람까지 1~N/2명을 팀을 이루도록 했을 때의 "가능한 모든 점수"에서 추가하는 방식으로 진행하면 된다.이렇게 N번째 사람까지 N/2명으로 구성했을 때의 가능한 점수를..

* BOJ 1410 패턴의 개수[분류 : 다이나믹 프로그래밍, 비트셋] 1. [같은 길이의 패턴] 길이가 다른 패턴은 절대 같은 단어를 포함할 수 없다. 같은 길이끼리만 모아서 생각해보자. 2. [비트 셋] 집합의 크기가 아무리 커봐야 15이므로 비트 셋을 쓰기에 충분히 작다. 또 2^15의 배열의 크기로도 충분히 작음을 알 수 있다. 3. [다이나믹 구성] 1.에 있는 조건을 가져와서 같은 길이를 가지는 패턴들만 생각해보자. dp[p][s]=p위치에 있는 문자를 결정해야하고, 현재 겹치는 패턴의 집합이 s일 때, 일치하는 패턴의 수가 정확히 K인 경우의 수 p이전에 선택한 문자들이 모두 일치하는, 또는 문자 ?로 대체할 수 있었던 패턴들이 s 비트 셋에 담겨있다. 현 위치 p에서 문자 a-z를 선택하며..

* BOJ 1742 레이싱 결과[분류 : 다이나믹 프로그래밍, DAG, 그래프 이론, 조합론] [풀이] 1. [그래프 구조] 먼저 구성되는 컴포넌트의 구조는 양방향 그래프가 아닌 DAG(Directed Acyclic Graph)이어야 한다. 즉, 사이클이 존재하면 모순이 발생하므로 경우의 수는 0이 돼야 한다. 2. [컴포넌트 집합] 하나의 컴포넌트에 여러 노드가 존재할 수 있다. 따라서 같은 컴포넌트에 있는 노드를 집합으로 둔다. 3. [진출 간선?] 나는 경기결과를 작성할 때 맨 뒤에서 시작해서 작성하는 걸 채택했다. 구성되는 dag 컴포넌트에서 진출 간선이 0인 것들부터 넣는 방식을 생각해보자. 진출 간선이 없다는 의미는 더 이상 자신이 반드시 이기는 상대가 존재하지 않는다는 뜻이다. 따라서 리프(..

* BOJ 1040 정수[분류 : 비트마스크, 다이나믹 프로그래밍] BOJ 3026 V(링크: https://www.acmicpc.net/problem/3026, 풀이 링크: https://coloredrabbit.tistory.com/110)을 먼저 풀 것을 권장합니다. [풀이] 1. [사용할 수 있는 숫자의 수는 K] 이것이 시사하는 바는 총 10개의 숫자 중 K개만을 선택하여 계산하겠단 소린데 경우의 수로 따지면 아무리 커봐야밖에 되지 않습니다. 2. [백트래킹이 안되는 이유] 뭐 당연하겠지만 K개 골라봤자, 수의 길이가 최대 18까지 올라갈 수 있고, 거기서 K^18 경우의 수가 나올 수 있으므로 시간이 모자랍니다. 3. [자리수 dp] 높은 자리에서 낮은 자리로 내려가며 N과 똑같은 자리수에 똑..

* 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..