알고리즘 [BruteForce]

Brute Force 관련 정리

BF관련 알고리즘 정리로 알고리즘 문제 해결 전략책을 읽고 해당 내용을 토대로 문제 풀이, 내용 정리

무식하게 풀기 정리 내용

알고리즘을 순차적으로 공부해야겠다고 마음을 먹고 책을 구매하여 진행..

단순 문제풀이보단 개념에 대한 명확한 이해 후 활용을 통한 학습이 더 값지고 오래갈 것 같다고 생각해서 책에서 추천하는 초심자 커리큘럼으로 진행했다.

책 내용 총 정리

최근에 6장을 마무리하게 되어서 한번 BF 내용을 되짚어보며 글을 작성한다.

추가로 실제 작업중인 프로젝트에 적용된 내용이 있어 리뷰한다.

BF에 관한 자세한 내용은 위 정리 내용을 참고하는게 좋을 것 같고 핵심적인 부분을 다시 짚어본다.

• 무식하게 푼다고 해서 좋지 못한 알고리즘이 아니다. 어떤 때에는 가장 빠르다.
• 재귀 호출에는 기저 사례를 잘 처리해야 한다. (‘더이상 쪼개지지 않는’ 최소한의 작업)
• 풀이하기 위해 문제를 분할하고 기저사례를 선택하여 구조를 만든다.
  • 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다.
    • 최대 크기의 입력을 가정했을 때 갑의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있는지 가늠한다. (적용할 수 없으면 동적 계획법을 사용한다.)
  • 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.
    • 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
  • 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
  • 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리한다
• 풀이할 때 중요한 점은 손으로 경우의 수를 계산하여 실제 답의 수의 상한을 예측해보는 것이다.
• 중복을 세는 문제를 조심해라

풀이한 문제는 총 4개로 BOGGLE, PICNIC, BOARDCOVER ,CLOCKSYNC이다.

모든 문제는 C#으로 풀이했으며 책의 수도코드와 다른 형태를 가진다.

BOGGLE

• 풀이 설명 링크

PICNIC

• 풀이 설명 링크

BOARDCOVER

• 풀이 설명 링크

CLOCKSYNC

• 풀이 설명 링크

3MatchPuzzle

• 풀이 설명 링크

책에는 없는 문제로 프로젝트에 적용된 코드이다.

혹시 수정되면 좋은 부분이 있다면 알려주시면 감사합니다.