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)에 있는 로봇들의 출력값이다. 로봇의 저장값은 입력값들의 최댓값이고, 저장값에 자신들의 가중치를 더한 값이 출력값이다. 이제 배열들..

BitMasking 수학에서의 집합은 원소들의 포함 여부를 가진다. 이를 프로그래밍을 통해 표현하기 위해서는 Array 등의 메모리 공간을 이용해서 표현할 수 있다. 이 때, 각 원소의 존재 여부를 0 혹은 1로 표시하는 방법이나, 원소들을 일일이 Array, Vector에 저장하는 방법으로 집합을 포현할 수 있다. 하지만 Array, Vector 등의 여러 원소를 포함하는 Container 뿐만 아니라 다른 방법으로도 집합을 표현할 수 있는데, BitMasking이 그 방법이다.BitMasking은 정수의 이진수 표현을 이용하여 집합을 나타내는 방법으로, 위에서 설명한 Array로 집합을 표현하는 방식에서 각 원소의 존재 여부를 0 혹은 1로 표시하는 방법을 채택한다. 4 Byte의 Integer를 구..

경로 역추적 동적 계획법 문제에서는 단순히 문제의 해를 구하는 것 뿐만 아니라, 그 해를 구하기 위한 과정에서 선택해야 하는 요소들을 출력하는 문제도 존재한다. 이를 해결하기 위해선 동적계획법을 진행할 때, 메모이제이션을 통해 저장해놓은 값들을 활용하여 중간 단계에서 최종 단계까지 도달하기 위해 선택해야할 필수 요소들을 출력해야 한다. 예를 들어 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..

Longest Common Substring  LCS(Longest Common Substring)은 두 문자열이 있을 때, 두 문자열의 최장 공통 부분 수열(공통되는 문자열 중, 최대 길이의 문자열)을 구하는 문제이다. 예를 들어 두 문자열 ACAYKP와 CAPCAK의 LCS는 ACAYKP, CAPCAK => ACAK임을 알 수 있다.  이는 간단한 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), d..

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