프로그래밍 대회에서 배우는 알고리즘 문제해결 전략
코딩 테스트를 보거나 연습을 위해 문제를 풀게 되면 문제이해를 한 후 바로 코딩에 들어갔었는데, 코딩에 들어가기전 생각을 정리하거나 어떤 알고리즘/자료구조를 사용하여 문제를 해결할지 필기를 하거나 머리속으로 한번 정리를 한 후에 문제 해결에 임하는 것이 더 도움이 된 다는 것을 언급 하고 있다. 또한, 문제를 풀고 난 후에는 회고가 중요하고 풀지 못하는 문제 같은 경우에 답안을 봐도 복기가 정말 중요하다고 강조하고 있다.
문제를 시작하기전 입력예제를 보고 알고리즘을 선택하고 경우의 수를 계산해보며 해당 알고리즘으로 사용해도 되겠는가 한번 생각해보고 문제풀이 시작하기!!
문제 해결전략
비슷한 문제에 대해 앞전에 풀어본 문제 해결전략을 이용해본다.
문제의 경우의 수를 순차적으로 줄여나가 단순화 시켜본다.
문제 풀이 과정을 수식화 해본다.
그림으로 그려본다.
문제의 내제된 순서를 바꾸어 뒤에서부터 풀어본다.
순서가 없는 문제에 순서를 부여하여 강제해 풀어본다.
코딩에 관하여
테스트만을 통과하기 위한 코드(스파게티 코드)가 아닌 읽기 좋고 재사용이 가능한 그런 코드를 작성하자.
이 책에서도 클린 코드의 몇 장들은 코딩하는데 알아두면 도움이 되는 책이라고 소개를 하고 있다.
재귀 호출과 부분 문제
재귀호출을 통해 문제의 조건이 적합하는 지 판단후 경우의 수를 한개씩 줄여가는 문제는 DFS나 BFS를 통해 완전탐색으로 해결할 수 있으며, 순서를 강제하여 중복을 제거하는 방식으로 풀이
최적화 문제
문제의 답이 여러개이고 그 중 가장 좋은답을 찾아내는 문제들을 최적화 문제라고 하고 이도 완전 탐색이 가장 직관적인 방법이다. (입력에 따른 경우의 수를 생각해보고 시간을 계산해 적절하다면 가장 쉽게 풀이할 수 있다는 뜻) 문제의 답이 여러개이고 그 중 가장 좋은답을 찾아내는 문제들을 최적화 문제라고 하고 이도 완전 탐색이 가장 직관적인 방법이다. (입력에 따른 경우의 수를 생각해보고 시간을 계산해 적절하다면 가장 쉽게 풀이할 수 있다는 뜻)
동적 계획법 (DP)
구현 방법
문제를 완전탐색을 이용해 해결
중복된 문제를 한번만 계산하도록 메모이제이션 적용
Last updated