[Algorithm] 풀이 단계 remind

나만의 알고리즘 풀이 단계 remind

• 문제를 명확히 이해한다. 문제에서 요구하는 것이 무엇이고, 그 사이사이에 어떤 제한 조건 등이 있는지를 디테일하게 파악해둔다.
• 이해한 문제를 바탕으로 설계를 한다. 이 때, 문제에 대한 명확한 이해가 돼있어야 이 문제의 풀이 로직도 제대로 짤 수 있다. 가장 먼저 생각해봐야할 것은(해결책 이전에) '탐색 공간'이다. 이 문제를 해결하기 위해 탐색해봐야할 탐색 공간이 얼마나 되는지를 파악하는 것이다. 그리고 그러한 탐색 공간을 전체 탐색(완전 탐색)했을 때 걸리는 시간복잡도와 해결방법을 먼저 생각해본다. 즉, 해결책 탐색의 제 1순위는 완전탐색법이다. 탐색공간을 전부다 탐색했을 때 이문제를 해결할 수 있다면, 완전탐색법으로 풀면된다. 그러나, 완전탐색법으로 풀었을 때 시간복잡도 제한에 걸리게 된다면, 다른 해결방법을 찾아야한다. 이 때 생각해볼 수 있는 방법들이 분할정복법, 동적계획법, 그리디 알고리즘, 그래프(자료구조)를 이용한 풀이이다. 그리고 그러한 해결책을 찾았다면, 이것이 왜 맞는지 스스로 증명할 수 있어야하고, 시간복잡도도 통과되는지 생각해야한다.
• 그 다음은 생각해낸 해결법을 통해 어떻게 구현할지를 설계하는 단계이다. 이 단계를 거치지 않고 바로 코딩을 하면 분명히 구현 단계에서 헤매고 시간을 더 끌게 되니까 설계 단계에서 충분히 숙고를 하자.
• 실제 코딩 단계로 설계한 것을 코드로 옮긴다는 생각으로 작성한다. 하지만 이때도 수도코드를 작성하면서 코드를 치는 것이 좋다. 설계한 것을 옮긴다 하더라도 실제 코드를 칠 때는 헷갈릴 수 있다.