david의 CS Blog

1. 계산 로봇 https://www.acmicpc.net/problem/22342 22342번: 계산 로봇 M개의 행(가로줄)과 N개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다. 각 행에는 위에서부터 아래로 1부터 M까지의 번호가 붙어 있고, 각 열에는 왼쪽에서부터 오른쪽으로 1 부터 N까지의 www.acmicpc.net 각 칸에 있는 로봇이 입력값, 저장값, 출력값을 가지므로 이해를 위해 입력값, 저장값, 출력값을 저장하는 2차원 배열 3개를 만들어보자. 각 로봇들의 입력값은 로봇의 위치(x, y)를 기준으로 왼쪽에 있고, |i-a|≤j-b를 만족하는 (a, b)에 있는 로봇들의 출력값이다. 로봇의 저장값은 입력값들의 최댓값이고, 저장값에 자신들의 가중치를 더한 값이 출력값이다. 이제 배열들..

비트마스크(BitMask)란? 정수의 이진수 표현을 이용하여 집합의 요소들의 구성을 나타내는 테크닉이다. 비트는 0 또는 1의 값을 가질 수 있고, 1은 참(True), 거짓(False)을 나타낸다. 예를 들어 십진수 12를 이진수로 나타내보면 다음과 같이 나타나는데 12 = $2^{3}$ + $2^{2}$ 로 표현되기 때문에 1100이라고 나타낼 수 있다. 이 때 각 비트가 가지는 상태를 통해 집합으로 이용할 수 있다. 비트는 1(True)와 0(False)만을 나타내기 때문에 구성 요소의 존재 여부를 나타낼 수 있는 것이다. 아래의 예시를 보면 집합을 정수형 변수 하나로 나타낸 것이다. 값 $i$가 집합에 포함되어 있으면 $i$번 비트가 1이고, 없으면 0인 것이다. {0, 1, 2, 3, 4, 5}..

경로 역추적 동적 계획법 문제에서는 단순히 문제의 해를 구하는 것 뿐만 아니라, 그 해를 구하기 위한 과정에서 선택해야 하는 요소들을 출력하는 문제도 존재한다. 이를 해결하기 위해선 동적계획법을 진행할 때, 메모이제이션을 통해 저장해놓은 값들을 활용하여 중간 단계에서 최종 단계까지 도달하기 위해 선택해야할 필수 요소들을 출력해야 한다. 예를 들어 BOJ 12852 1로 만들기 2 와 같은 문제에서는 입력받은 자연수 N을 1로 만들기 위해 수행해야하는 연산의 순서를 출력하는 문제이다. 예를 들어 N이 10이라면 최소 횟수인 4 뿐만 아니라 10 -> 9 -> 3 -> 1의 순서를 출력해야한다. 이 문제의 해를 구하는 과정을 동적계획법으로 구현하면 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 1..

LCS란? 두 문자열이 있을 때 최장 공통 부분 수열(공통되는 문자열의 최대 길이)을 구하는 문제이다. 예를 들어 두 문자열 ACAYKP와 CAPCAK의 LCS는 ACAYKP, CAPCAK => ACAK이므로 4이다. 이는 간단한 dp로 풀 수 있는데, 두 문자열 a, b에 대하여 배열 $dp[i][j]$를 첫 번째 문자열 a의 구간 [ i, 끝 ], 두 번째 문자열 b의 구간 [ j, 끝 ]에 속하는 LCS 길이라고 정의하면 i) a[i]와 b[j]가 같을 때: $dp(i, j)=dp(i+1, j+1)+1$ ii) 같지 않을 때: $dp(i, j)=max( dp(i+1, j), dp(i, j+1) )$ 라고 할 수 있다. 탑다운으로 푼 코드 #include using namespace std; stri..

Dynamic Programming  프로그래밍을 통한 문제 해결은 결국 탐색 공간에서 원하는 해를 찾아내는 과정이다. 알고리즘의 측면에서 우리는 어떻게 하면 적은 연산을 통해 해를 도출할 수 있을지 고민하는 것이 중요하다. 동적 계획법 또한 해를 탐색하는 전략의 일종으로 해를 구하는 과정에서 불필요한 연산을 최소화하기 위해 고안된 기법이다. 동적 계획법은 문제를 여러 개의 부분 문제로 나누어 각 부분 문제에 대한 결과를 구한 다음, 그 결과들을 이용해 해결하고자 하는 원래의 문제를 푸는 최적화 기법의 일종이다. 즉, 큰 문제를 여러 부분 문제로 나눈 후, 부분 문제들의 답을 각각 구하고 그 결과값을 바탕으로 큰 문제의 결과값을 구하는 방법이다. 이렇게 말하면 쉽게 와닿지 않을 뿐더러 기법에 대한 정의가..