[Algorithmic Problem Solving Strategies] 2. 문제해결과정

알고리즘 문제 해결 전략 세트 국내도서 저자 : 구종만 출판 : 인사이트 2012.11.23 상세보기

알고리즘 문제 해결 전략 세트구종만 상세보기

 

2.2 문제해결과정

===============

1단계: 문제를 읽고 이해하기

• 완전히 이해
  ———————-
• 2단계: 재정의와 추상화*
• 문제를 자신의 언어로 풀어 쓴다.(직관적 이해)
• 추상화
  ———————-
• 3단계: 계획세우기*
• 문제를 어떤 방식으로 해결할 것인가
• 사용할 알고리즘&자료구조 선택
  ———————-
• 4단계: 계획 검증하기*
• 설계한 알고리즘이 모든 경우에 요구 조건을 정확하게 수행하는 지 증명
• 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는 지 확인
  ———————-
• 5단계: 계획 수행하기*
• 프로그램 작성 단계
  ———————-
• 6단계: 회고하기*
• 더 효율적인 알고리즘 찾기
• 간결한 코드 작성
• 같은 알고리즘을 유도할 수 있는 더 직관적인 방법 찾음
• 방법1) 자신의 경험을 기록으로 남기기

  문제의 간단한 해법
  어떤 방식으로 접근했는지
  문제의 해법을 찾는 데 결정적이었던 깨달음
  한 번에 맞추지 못한 경우) 오답 원인 적기

• 방법2) 같은 문제를 해결한 다른 사람의 코드 보기

2.3 문제해결전략

===========
비슷한 문제를 풀어본 적이 있나?

• 문제 분류 방법 익히기(어떤 문제가 최적화 문제인지 / 경우의 수를 구하는 문제인지 / 검색 문제인지)
• 각 알고리즘들이 어느 경우에 사용될 수 있는지 체계적으로 공부
  ———————-
• 단순한 방법에서 시작할 수 있을까?*
• 일단 시간과 공간 제약을 생각하지 않고 문제를 해결할 수 있는 가장 단순한 알고리즘을 만들어 보는 것
• 목표) 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 예방
• 이유)
• 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많아서
• 알고리즘 효율성의 기준선을 정해주는 효과
• 예시)
• 사탕의 평균 무게가 작게
  ———————-
• 내가 문제를 푸는 과정을 수식화할 수 있을까?*
• 손으로 여러 간단한 입력(주어진 입력)을 직접 해결해 보기
  ———————-
• 문제를 단순화할 수 없을까?*
• 주어진 문제의 좀더 쉬운 변형판을 먼저 풀어본다.
  ———————-
• 그림으로 그려볼 수 있을까?*
  ———————-
• 수식으로 표현할 수 있을까?*
  ———————-
• 문제를 분해할 수 있을까?*
• 더 다루기 쉬운 형태로 문제를 변형
• 예)
  문제의 제약 조건을 분해
  ———————-
• 뒤에서부터 생각해서 문제를 풀 수 있을까?*
  ———————-
• 순서를 강제할 수 있을까?*
  ———————-
• 특정 형태의 답만을 고려할 수 있을까?*
• 정규화(canonicalization)