Brute force, 분할정복, DP basic
1.Brute force
재귀호출 > 단순히 중첩문을 반복하는 것에 비해 코드 수정이 용이해서 재활용 가능성이 높다. > 재귀 함수의 종료를 위해 기저 사례를 선택해야한다. 재귀 함수가 가장 깊숙한 곳으로 들어간 경우, 재귀 함수의 목적을 달성한 경우, 반드시 지켜야 하는 특정 조건을 위배한 경우 더 이상 함수가 호출될 필요가 없기 때문에 함수가 반환되도록 해주는 것이다. >...
2.Brute force 문제3 - 시계 맞추기
image.png 문제 풀이 과정 > brute force를 통한 문제임을 알고 봤음에도 풀이 방법이 명확히 떠오르지 않았는데, 가장 큰 이유는 해결 가능한 문제로 바꿔주는 조건인 각 시계는 최대 세 번까지 밖에 조작하지 못한다는 조건을 깨닫지 못했기 때문이다. 시계는 세 시간씩 움직이므로 네 번 조작하게 되면 다시 처음의 시간으로 돌아가게 되고 이...
3.분할 정복 문제1- 쿼드 트리
문제 파악 >분할 정복 유형이라는 것을 알고 접근했는데도 어떤 식으로 문제를 나눌 수 있는지 전혀 감이 오지 않았다. 분할 정복과 이전에 배운 단순한 재귀 호출을 통한 분할과의 차이점을 아직 완벽히 파악하지 못한 상태에서 문제에 접근하게 된것 같다. 압축을 먼저 전부 풀고 다시 압축을 하는 방식으로 생각해 봤는데 어떤 식으로든 중간 과정이 너무 복잡해져...
4.분할 정복 문제2 - 울타리 잘라내기
image.png 문제 파악 > 이 문제가 분할 정복을 통해 해결될 수 있는 문제라는 느낌은 바로 들었다. 내가 생각한 방식은 높이 1부터 한 칸씩 올라가면서 가장 낮은 높이를 가진 판자를 만나면 분할시키는 방식이었다. 시간복잡도는 바로 생각하지 못하고 우선 구현했는데, 구현 과정에서는 가장 낮은 높이를 가진 판자가 여러 개 들어있거나, 붙어있는 경우의...
5.Brute force 문제2 - 게임판 덮기
image.png 2019-06-25 19:06 작성됨 문제 풀이 과정 문제 파악 > #과 .으로 이루어진 게임판에서 ㄱ자 모양의 블럭을 퍼즐처럼 채우는 경우의 수를 찾는 문제이다. 그래프와 기하 문제에 약해서 이런 문제는 보기보다 어렵게 느껴졌다. Brute force를 활용하는 문제이기 때문에 한 블록을 빈칸에 넣을 때마다 새로운 문제로 나뉘는건 명...
6.Brute force 문제1 PICNIC
image.png 문제 풀이 과정 문제 파악 정해진 조건에서 총 몇개의 경우의 수가 나올 수 있는지 구하는 문제이다. 문제의 입력도 크지 않아서 시간 제한은 고려할 필요가 없으며 한 쌍의 짝을 구하면 나머지 인원들에 대한 접근은 원래 문제의 부분 문제이므로 재귀함수를 통해 접근하는 문제임도 명확하다. 아마 가장 많은 고민을 필요로 하는 ...
7.동적 계획법(Dynamic Programming) - Memoization
동적 계획법을 사용하는 이유 > 동적 계획법은 부분 문제를 통해 큰 문제를 재귀적으로 해결하려고 할 때 중복되는 부분 문제들이 많이 발생하여 불필요하게 같은 계산이 반복될 때 사용된다. 이항 계수를 계산하는 공식은 아래와 같은 공식이 성립한다. bino(n, r) = bino(n-1, r-1) + bino(n, r-1) > 위 식에 대해 생각해보...
8.동적 계획법(Dynamic Programming) - 최적 부분 구조
최적 부분 구조란 > 앞서 살펴 보았던 동적 계획법 문제는 어떠한 값을 계산하거나, 경로가 존재하는 지에 대한 문제에 사용되었던 방식이다. 최적화 문제는 그러한 계산값이나 경로 중 어떤 것이 최적인지를 계산하는 문제인데, 이 때 설계하는 재귀 함수의 파라미터로 가장 필수적인 값만 넘겨주는 부분 문제의 구조가 최적 부분 구조이다. 이 때 불필요한 값까지 넘...
9.동적 계획법(Dynamic Programming) - 최적 부분 분석 문제1 - JLIS
문제 정의 > 지금까지 배워왔던 브루트 포스, 분할 정복, 일반 DP, 최적화 DP 모두 문제 해결 과정에서 가장 어려우면서 핵심적인 부분이 큰 문제를 적절한 부분 문제로 나누는 작업이다. 단순 LIS 문제는 수열이 한 개만 주어져서 부분 문제와 상위 문제들 사이의 관계가 비교적 명확하게 드러났는데, JLIS의 경우 수열이 두 개이기 때문에 그 과정이 ...
10.동적 계획법(Dynamic Programming) - 최적 부분 분석 문제2 - 원주율 외우기(PI)
image.png 문제 파악 > 나열된 숫자들에 대해 일정한 규칙을 가지고 적절하게 구간을 나누는 문제이다. 구간을 나눠가면서, 난이도의 최소값을 구하는 문제기 때문에 부분 문제로 나뉘는 문제임은 어렵지 않게 파악되었다. 끊을 수 있는 구간 역시 3,4,5 세 구간 밖에 없었기 때문에 복잡하게 느껴지지 않아서 대략적인 설계는 간단히 마칠 수 있었다. 구...
11.동적 계획법(Dynamic Programming) - 경우의 수와 확률
오버플로 > 문제를 푸는 과정, 또는 정답에서 경우의 수를 구해야 하는 경우 구하고자 하는 정수의 수가 너무 커져서 int형의 size 4바이트를 초과해서 오버헤드가 발생할 수 있다. 이 경우 재귀 함수의 반환값에 모듈로 연산을 처리해 주면, 수의 크기가 훨씬 줄어들어 오버헤드를 방지할 수 있다. 예제 - 삼각형 위의 최대 경로 수 > 이 전에 풀었던...
12.동적 계획법(Dynamic Programming) 경우의 수 문제 1 - 비대칭 타일링
문제 파악 > 원래 타일 개수에서 대칭되는 타일의 개수만 빼면 되는 것이므로, 대칭 타일의 수를 계산하는 DP알고리즘에 비대칭 타일의 개수만 계산해서 빼주면된다. > 비대칭 타일의 개수는 짝수일 경우 홀수일 경우를 나눠서 생각하면 원래 칸의 숫자 N을 2로 나눠서 간단히 계산할 수 있다. > 이 문제는 경우의 수가 매우 커서 모듈로 연산자가 반드시 필요...
13.동적 계획법(Dynamic Programming) 최적 부분 분석 문제3 - 양자화
문제 풀이 직관적인 접근 > 양자화란 넓은 범위로 이루어진 자료를 더 좁은 범위로 표현하는 것이다. 문제의 양자화는 수열의 수 종류를 요구하는 범위까지 좁히는 것이다. 이 때 좁히는 조건은 각 수의 오차 제곱의 합이 최소가 되어야한다. > 이 문제는 앞의 선택이 뒤의 선택에 계속해서 영향을 미치므로, 직관적으로 최적 부분 구조를 설계하는것이 쉽지 않다. 나...
14.동적 계획법 - 경우의 수 문제2 - 폴리오미노
image.png 문제 파악 > DP를 사용하기에 앞서 완전 탐색으로 접근하기 위해서 폴리오미노의 경우의 수를 따질 수 있는 방법을 생각해 보았다. 각 도형을 한 줄씩 나눠 개수를 더하는 방식을 생각해 보았는데, 이 과정에서 발생하는 중복과 개수별로 조합했을 때 발생하는 합친 도형의 개수가 달라져서 이 부분에서 처리를 어떻게 할지 생각해 낼 수가 없었다...
15.동적 계획법 경우의 수와 확률 문제 3 - 두니발 박사의 탈출
image.png 문제 파악 > 문제를 이해하고, 각 days에 노드들의 확률이 서로 어떤 연관이 있음을 명확히 알 수 있었다. 각 노드들의 해당 날짜의 확률은 그 전 날 인접 노드의 확률로부터 얻어질 수 있음을 느낄 수 있었다. > 따라서 이러한 직관을 바탕으로 days에 따른 노드들의 관계를 정의해 보았다. 해당 날짜에서 특정 노드의 확률은 그 전날 ...