알고리즘

문제를 읽어보면 상당히 식이 복잡하다. 어떻게 흘러갈지가 한눈에 보이지 않는다. Branch Depth가 깊어질 가능성이 크다. 이 경우에는 Branch의 결과값을 저장해두고 재귀 호출시 이전에 계산했던 값이 있을경우에는 Branch하는 대신 이미 구해진 값을 연산에 이용하면 속도 최적화에서 이득을 볼 수 있다. #define _CRT_SECURE_NO_WARNINGS #include #include int Ans[101][101][101] = { 0 , }; int RecursiveCall(int A, int B, int C) { if (A 70) { if (0 == Ans[70][70][70]) Ans[70][70][70] = RecursiveCall(70, 70, 70); return Ans[70]..

매우 평범하고도 쉬운 Back Tracking 문제이다. 기존의 Back Tracking 과 똑같이 Branch 의 Return 을 받고, 상태 초기화 후 반복문 돌리니 쉽게 풀어 낼 수 있었다. 연산자 우선순위는 무시한다고 했으므로 단순하게 이전 선택지에 대한 누적 결과를 Param으로 주는 Branch를 진행한다. Branch Depth 의 끝에 도달했을때가 식을 모두 진행한 결과이므로 이때에 최소값과 최대값을 갱신한다. 진입점에서 맨 처음에 오는 숫자는 이전의 결과가 없으므로 자기 자신을 넣어준다. #define _CRT_SECURE_NO_WARNINGS #include #include #include int Operators [4]; int Numbers [100]; int Max = 0X8000..

스도쿠 퍼즐은 다음과 같은 규칙을 가진다. 한칸에 1부터 9의 숫자를 넣을수 있다. 가로 줄에 같은 숫자가 존재 하면 안된다. 세로 줄에 같은 숫자가 존재 하면 안된다. 가로 세로 크기가 3인 큰 정사각형으로 잘랐을때, 하나의 큰 정사각형 내에 1부터 9의 숫자가 하나씩 존재해야 한다. 그렇다면, 어떠한 Row에 숫자가 존재하는지 간단하게 검사할 수 있다. 또, 어떠한 Col에 해당 숫자가 존재하는지 간단하게 검사할 수 있다. 가로세로 크기 3인 큰 정사각형 내에 숫자가 존재하는지 간단하게 검사할 수 있다. 퍼즐의 빈칸에 대해, 이 3가지 배열 조건을 검사하고, 만족하는 경우 숫자를 기입하며 Back Tracking 하면 쉽게 답을 찾을 수 있다. 코드를 구현하면 다음과 같다. #define _CRT_S..

NQueen 알고리즘은 Back Tracking 알고리즘의 대표적인 예이다. 간단하게 N개의 퀸을 크기가 N인 체스보드에 서로 공격할수 없게 배치 하려면 어떻게 해야 하느냐? 이다. 퀸의 경우 다음과 같은 공격범위를 가진다. 따라서, 내가 N개의 Row를 탐색하려고 한다면, 이전에 어떠한 열에 두었는가?를 기억하면 그 다음 열에서는 탐색을 할 필요가 없다. (퀸이 Y축으로 쭉 공격이 가능한것임을 기억.) 예를 들어보자. 8A에 퀸을 두었다. 8A에 퀸을 두었으니 해당 Row 8은 더이상 둘수 없다. Col A 에도 더 이상 둘 수 없다. 이 정보를 기록해둔다. 헌데, 한 Row에 퀸을 두면 어짜피 다음 라인을 서치 할것이 아닌가? 따라서 Col A에 퀸이 놓여있다는 것만 기억하면 된다. Row를 8부터 ..