꾸준한 개발일기

문제를 요약하면, N개의 수로 이루어진 수열 A1, A2, ..., An 합이 n-1개인 정수 ex) 2 1 2 1 (차례대로 +, -, *, / 의 사용개수) => A1 + A2 + A3 - A4 * A5 * A6 / A7 A1 * A2 + A3 / A4 + A5 - A6 * A7 etc. 가장 큰 수와 작은 수는? 단, A1 ~ An 수의 순서는 고정. 연산자 우선순위 무시하고 앞에서부터 연산. 설계 변수정의 및 SST 설계 알고리즘 진행 시 필요한 변수를 파악하고 용도의 정의를 정확히 짚고 넘어가는 것이 굉장히 중요하다. State Space Tree를 생성하고 몇단계 진행해보면서 필요한 변수가 무엇인지 파악하고 변수들을 정리하자. 위의 그림처럼 SST에서 "방문"을 나타내고 연산순서를 저장하기 위..

Backtracking 문제는 설계 1. 문제를 어떻게 State Space Tree로 나타낼 것인가? 2. Promising Function은 어떻게 설정할 것인가? 구현 1. 재귀함수로 재귀적으로 트리를 탐색할 때 파라미터로 갱신해야하는 값은 있는가? 2. SST의 노드들의 방문과 되추적을 어떻게 코드로 나타낼 것인가? 3. 재귀함수의 basecase는 어떻게 설정해야 하는가? 설계상의 문제와 구현상의 문제를 모두 고려해야 한다. 설계 시도1 (실패) 설계 시도2 (성공) 설계1과 설계2의 차이는 "자식의 방문여부 기록"이다. N=3 M=3 이면 1~3까지의 숫자를 중복없이 M개를 고른 수열이므로 answer = 123, 132, 213, 231, 312, 321이 될 것이다. for (int i=1..

Backtracking 개념 주어진 문제를 트리(State Space Tree)로 어떻게 표현할지, 문제에 맞는 유망성검사(Promising function)는 어떻게 구성할지 설계상의 고민이 끝났다면 어떻게 코드로 나타내고 구현할지 코드상의 고민이 필요하다. 코드구현상의 고민 1. 트리의 묵시적 표현과 어떤 자료구조로 대체할 것인가? 트리는 우리가 구현할 알고리즘의 흐름을 파악하기 위한 용도이기 때문에 반드시 구현할 필요는 없다. 또한, 트리로 구현하지 않는다면 어떠한 자료구조로 대체하여 방문과 되추적을 표현할 것인가도 고민해줘야 한다. 예시 예를들어보자. 4-Queens Problem (4개의 Queen들을 서로 위협이 되지 않게 4 X 4 행렬에 배치하는 문제)의 SST는 다음과 같을 것이다. 어떤..