그냥 하는 노트와 메모장

* BOJ 1023 괄호 문자열[분류 : 다이나믹 프로그래밍] BOJ 17428 K번째 괄호 문자열을 먼저 푸는 것을 추천합니다. 사실상 거의 같은 문제입니다. [풀이] 올바른 괄호 문자열의 정의는 '('의 수와 ')'의 수가 같아야하며 왼쪽에서 오른쪽으로 순회할 때 ')'의 수가 '('의 수보다 많아지면 안된다. 반대로 괄호 ㄴㄴ 문자열이 되려면 위 정의 반대로 구성하면 된다. 즉, 1. '('의 수와 ')'의 수가 다르거나 2. 왼쪽에서 오른쪽으로 순회할 때 ')'의 수가 '('보다 많은 경우에 올바르지 않다고 판단해주면 된다. 위를 토대로 함수 프로토타입을 정의하면 아래와 같다.rec(v, p, r) v : validation ')'의 수가 '('의 수를 역전했던 적이 있는지 확인하는 플래그 변수p..

* BOJ 17428 K번째 괄호 문자열[분류 : 다이나믹 프로그래밍] [풀이] 올바른 괄호 문자열이 몇 개 있을 수 있는지 생각해보자. 당연히 이 문제를 풀어본 사람은 카탈란 수를 떠올릴 수 있을거고, 아니더라도 아래 점화식을 떠올릴 수 있다. 하지만 이런 방식은 사전순에 대한 처리를 할 수 없어진다. 보다 간단하게 생각해보자. 현재 위치에서 어떤 괄호를 쓸 것인지를 생각해보자. 단 지금까지 구성해온 문자열에서 모두 쓸 수 있는 것은 아니다. '('과 ')' 수가 똑같을뿐만 아니라 왼쪽에서 오른쪽으로 순회할 때 ')' 수가 '(' 수보다 많지 않도록 구성해야 한다. 따라서 정의해야 하는 함수는 현재 위치 p에서 '('가 ')'보다 r만큼 많을 때 나올 수 있는 올바른 괄호 문자열의 수를 반환하도록 한다..

* BOJ 3001 이상한 문제[분류 : 다이나믹 프로그래밍] [풀이]1. [각 자리수 합이 S인 개수] 구간이 정해져 있으므로 1부터 B까지 합이 S인 것의 개수에서 0부터 A-1까지 합이 S인 것의 개수를 빼준다. 이렇게하면 똑같은 함수를 두 번 호출하는 꼴이 나온다. rec(limit, position, summation, A)※ limit은 주어진 A보다 작은 경우만 세야하므로 제한을 두는 변수다. 기저영역은 A보다 작은 자리수에 대해 숫자를 채웠고 남은 summation이 0이 되는 경우에 1 더해주면 된다. 2. [A보다 크거나 같고 B보다 작은 수 중 자리수 합이 S가 되는 가장 작은 정수] 문제 조건에서 적어도 하나 이상의 수가 반드시 존재한다고 했으니 이 값은 A와 가장 가까운 정수를 출..

* BOJ 16876 재미있는 숫자 게임[분류 : 다이나믹 프로그래밍] [풀이] 턴 수의 홀짝 여부를 따져서 누가 게임을 끝내는지 쉽게 알 수 있다. 따라서 기저 조건에 게임이 종료될 때 누가 이기는지 결정한다. 서로 이기려고 최선을 다한다는 조건이 있기 때문에 어느 턴(p)에 어떤 수(d)로 주어지는 경우에 수행할 수 있는 행동은 1~10^3자리 숫자를 1 증가하는 4개밖에 없으므로 for문 한 번 구성해서 돌려주면 된다. 9에서 다시 0으로 간다는 조건만 잘 구현하면 어렵지 않게 AC를 받을 수 있는 문제다. #include #include int dp[101][10000], N, M, dx[] = { 1,10,100,1000 }; int rec(int p, int d) { if (p == M) re..

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