Brute force Study

문자열과 시퀀스에 대한 동적 계획법이전 게시물에서 다룬 문제는 정수 시퀀스 계산 문제에 초점을 두었다.이번에는 동적 계획법이 많이 사용되는 분야 중의 하나인 데이터 시퀀스의 패턴 문제에 대해 알아본다.주로 문자열 검색, 비교, 문자열 재구성 등의 문제와 관련이 있다.EX) 버전 관리 시스템(VCS)Git과 같은 VCS에서 우리가 다룰 데이터 시퀀스의 패턴 문제가 적용된다VCS는 변경된 소스 코드 부분을 쉽게 찾아보기 위해 두 가지 버전의 소스 코드를 비교하여 사용자에게 차이점을 표시해주는 비교 기능을 제공한다두 버전에 공통적인 문자열 시퀀스가 연속적일 필요가 없다는 사실을 고려하여 두 소스 코드의 유사성을 판별해야 한다.문자열 일부가 제거되거나 새로운 문자열이 임의 위치에 추가될 수도 있다.이러한 작업은..

부분집합의 합 문제(브루트포스, 백트래킹, 메모이제이션, 타뷸레이션)금전등록기에 남아 있는 동전을 조합하여 필요한 거스름돈을 만들 수 있는지 확인해보자.필요한 잔돈이 73270원이고, 10000원권, 1000원권과 500원, 100원, 50원, 10원 동전들이 전체 100개가 들어있다면?가능한 모든 조합을 시도해보면서 거스름돈의 금액을 맞추는 것은 너무 복잡해지고 실제로 구현하는 것은 너무 복잡하고 비현실적이러한 문제를 부분집합의 합 문제(subset sum problem)이라고 한다"음수가 아닌 정수로 이루어진 집합 S와 임의의 정수 x가 주어질 때, S의 부분집합 중에서 그 원소의 합이 x와 같은 부분집합이 존재하는가?"ex) S = {13, 79, 45, 29}, x = 42 --> True원소의 ..

동적 계획법(Dynamic Programming)이란?분할 정복 패러다임 개념을 확장한 것앞서 다룬 분할정복 / 그리디 알고리즘으로 해결할 수 없는 문제 중에서 재귀적으로 표현할 수 있는 문제는 동적 계획법을 이용한 문제 해결 방법이 적합할 수 있다.ex)조합(특정 기준을 만족하는 시퀀스의 조합 또는 순열의 개수 구하기)문자열과 시퀀스(편집 거리, 최장 공통 부분 시퀀스, 최장 증가 부분 시퀀스 등)그래프(최단 경로 문제)머신 러닝(음성/얼굴 인식)Ex) 피보나치 수열 문제의 특성피보나치 수열은 F(n) = F(n - 1) + F(n - 2)의 재귀적인 관계를 가지고 있다.위 수식은 이 수열의 재귀 관계를 표현한다.이 수열의 처음 두 원소 F(0), F(1)은 기조 조건(base case)이라고 부르며,..