프로그래밍 대회를 위한 여섯 단계 문제 해결 알고리즘

박정훈·2021년 1월 27일
0

Algorithm

목록 보기
1/7

파인만 알고리즘

  1. 칠판에 문제를 적는다.
  2. 골똘히 생각한다
  3. 칠판에 답안을 적는다

문제 해결 과정을 단계별로 나누었다.(아주 중요하다)
문제를 적어보는 단계가 있다. 문제를 읽고 이해한 뒤 자신의 언어를 이용해 재정의 해야 하기 때문에 이 단계는 매우 중요하다.

문제 해결 과정(How to Solve It에서의 문제 해결 과정)

  1. 문제를 이해한다.
  2. 어떻게 풀지 계획을 세운다.
  3. 계획을 수행해서 문제를 해결한다
  4. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

결론

  1. 문제를 읽고 이해한다.
  • 사소한 제약 조건도 놓치거나 잘못 이해하면 안된다.
  1. 문제를 익숙한 용어로 재정의한다.
  • 문제가 요구하는 바를 직관적으로 이해하기 위해 필요하다.
  • 어떤 부분을 추상화할 것인지를 선택하는 작업과 문제를 재정의하는 방법들에 대한 고찰은 좋은 프로그래머가 되기 위해 필수적인 과정이다.
  1. 어떻게 해결할지 계획을 세운다.
  • 문제를 어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택한다.
  • 문제 해결에서 가장 중요한 단계이다.
  1. 계획을 검증한다.
  • 구현을 시작하기 전에 계획을 검증한다.
  • 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하는지를 증명하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인한다.
  1. 프로그램으로 구현한다.
  • 프로그램을 작성한다.
  • 아무리 천재적인 알고리즘을 고안했더라도 구현이 부정확하거나 비효율적이면 프로그램은 정확히 동작할 수 없다.
  1. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
  • 자신이 문제를 해결한 과정을 돌이켜 보고 개선한다.
  • 문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배우지 못하는 경우가 많다.
  • 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남길 것
  • 문제의 간단한 해법과 함께 어떤 방식으로 접근했는지, 그리고 문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지를 기록하면 좋다.
  • 한 번에 맞추지 못한 경우에는 오답 원인도 꼭 적을 것
  • 같은 문제를 해결한 다른 사람의 코드를 보는 것도 좋다.

문제를 풀지 못할 때

  • 초보 시절에는 한 문제에 너무 매달려 있는 것도 좋지 않다.
  • 일정 시간이 지나도록 고민해도 답을 찾지 못할 때는 다른 사람의 소스 코드나 풀이를 참조한다는 원칙을 세우고 이를 지키는 것이 좋다.
  • 단, 다른 사람의 소스 코드나 풀이를 참조할 때는 반드시 복기를 동반해야 한다.
  • 자신이 문제를 해결할 때 취했던 접근들을 되새겨 보고 자신이 왜 이 풀이를 떠올리지 못했는지를 살펴봐야 한다.

문제 해결 전략

직관과 체계적인 접근

  • 직관은 해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지를 짐작할 수 있게 해준다.
  • 체계적인 방법은 백지에서부터 시작해 문제를 해결하기 위한 기반을 차근차근 쌓아올리면서 점진적으로 전진하는 것을 의미한다.

체계적인 접근을 위한 질문들

  1. 비슷한 문제를 풀어본 적이 있던가?

  2. 단순한 방법에서 시작할 수 없을까?

    • 무식하게 풀 수 있을까? 라는 질문으로 시작
    • 즉, 시간과 공간 제약을 생각하지 않고 문제를 해결할 수 있는 가장 단순한 알고리즘을 만들어 보는 것이다.
    • 이 전략의 일차적 목표는 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 예방한다.
    • 컴퓨터는 사람보다 훨씬 빠르므로, 언뜻 우리가 느끼기에는 엄청나게 오래 걸릴 것 같은 일도 시간 안에 수행할 수 있는 경우가 많다.
    • 이 방법이 유용한 진짜 이유는 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문이다.
    • 효율적인 자료 구조를 사용하거나, 최적화를 적용해서 충분히 빨라질 때까지 알고리즘을 개선하는 식으로 문제를 해결할 수 있다.
    • 단순한 방법은 알고리즘 효율성의 기준선을 정해주는 효과도 있다.
  3. 내가 문제를 푸는 과정을 수식화할 수 있을까?

    • 손으로 여러 간단한 입력, 예를 들어 문제에 주어진 예제 입력을 직접 해결해 보면 좋다.
  4. 문제를 단순화할 수 없을까?

    • 문제의 좀 더 쉬운 변형판을 먼저 풀어 보는 것이다.
    • 문제를 쉽게 변형하는 방법은 여러 가지이다.
    • 문제의 제약 조건을 없앨 수도 있고, 계산해야 하는 변수의 수를 줄일 수도 있으며, 다차원의 문제를 1차원으로 줄여서 표현할 수도 있다.
    • 이때 단순화된 문제의 해법이 원래 문제의 해법에 대한 직관을 제공할 수도 있고, 이것을 직접적으로 이용해 원래 문제를 풀어낼 수도 있다.
  5. 그림으로 그려볼 수 있을까?

    • 많은 사람들의 사고 체계는 숫자의 나열보다 기하학적 도형을 더 직관적으로 받아들이기 때문이다.
    • 예를 들어 두 개의 정수 쌍들을 다루는 문제가 있다면, 이 정수 쌍을 2차원 평면 상의 좌표로 그려 볼 수도 있고, 직선 상의 구간들로 그려 볼수도 있다.
  6. 수식으로 표현할 수 있을까?

    • 문장으로 쓰여 있는 문제를 수식으로 표현하는 것도 도움이 되는 경우가 있다.
  7. 문제를 분해할 수 있을까?

    • 더 다루기 쉬운 형태로 문제를 변형하는 것
    • 한 개의 복잡한 조건보다 여러 개의 단순한 조건이 다루기 쉽다.
  8. 뒤에서부터 생각해서 문제를 풀 수 있을까?

    • 문제에 내재된 순서를 바꿔 보는 것
  9. 순서를 강제할 수 있을까?

    • 순서가 없는 문제에 순서를 강제해서 문제를 푸는 방법
  10. 특정 형태의 답만을 고려할 수 있을까?

  • 정규화(canonicalization) 기법
  • 정규화란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법이다.

출처

  • 프로그래밍 대회에서 배우는 알고리즘 문제해결전략
profile
정팔입니다.

0개의 댓글