프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (1/2) #1

지음 : 구종만

교보문고 상세

1.3 입문자를 위한 커리큘럼

처음 문제 해결을 공부하는 사람은 모든 주제를 깊이 있게 공부하기 전에 가장 흔히 출현하는 낸용들을 포함하는 장들을 먼저 읽어 보기를 권장합니다.

장 번호	장 제목
2	문제 해결 전략
3	코딩과 디버깅
4	알고리즘의 시간 복잡도 분석
6	무식하게 풀기
7	분할 정복
8	동적 계획법
18	선형 자료 구조
19	큐와 스택, 데크
21	트리의 구현과 순회
22	이전 검색 트리
23	우선순위 큐와 힙
27	그래프의 표현과 정의
28	그래프의 깊이 우선 탐색
29	그래프의 너비 우선 탐색
30	최단 경로 알고리즘

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

1. 문제를 읽고 이해한다
2. 문제를 익숙한 용어로 재정의 한다
3. 어떻게 해결할지 계획을 세운다
4. 계획을 검증한다
5. 프로그램으로 구현한다
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다

참고로 파인만 알고리즘은 아래와 같다

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

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

• 비슷한 문제를 풀어본 적이 있던가
• 단순한 방법에서 시작할 수 있을까
• 내가 문제를 푸는 과정을 수식화할 수 있을까
• 문제를 단순화할 수 없을까
• 그림으로 그려볼 수 있을까
• 수식으로 표현할 수 있을까
• 문제를 분해할 수 있을까
• 뒤에서부터 생각해서 문제를 풀 수 있을까
• 순서를 강제할 수 있을까
• 특정 형태의 답만을 고려할 수 있을까