대회 준비용 책인데 그냥 프로그래밍 기초체력 자체가 좀 많이 모자란 거 같아서 자기전에 5~10분씩 잠깐 보는 걸로 공부하기로.
02 문제 해결 개관
20220418~19
2.1 도입
이 섹션이 메타-섹션임을 기술하고 계십니다. 꾸준한 연습만큼 그 방법도 중요하죠.
2.2 문제 해결 과정
책에서는 여섯가지 문제해결의 절차, 즉 일반적인 프레임워크를 제시합니다. (굵은 글씨는 제가 임의로 작성)
문제 풀이가 익숙하면 의식하지 않고도 자연스럽게 이런 단계를 거친다고 하네요.
- 읽고 이해: 문제를 읽고 이해한다 ("문제를 읽고 이해하기")
의사소통의 중요성. - 자신의 언어로: 문제를 익숙한 용어로 재정의한다 ("재정의와 추상화")
알고 있는 개념이나 자신이 이해한 바로 문제를 소화 - 설계 및 계획: 어떻게 해결할지 계획을 세운다 ("계획 세우기")
접근 방식, 알고리즘, 자료구조 선정 - 복잡한 문제면 차근차근 접근해야 - 구상 검증: 계획을 검증한다 ("계획 검증하기")
예외 케이스 확인, 성능 검증, 정당성 증명 등 - 구현: 프로그램으로 구현한다
하하 마법이다! - 회고: 어떻게 풀었는지 돌아보고 개선점 파악
메타인지 - 풀이 절차 확인, 기록, 타 솔루션 비교
못 풀었을 때
꼭 복기를 하래요. 풀이 절차를 되돌아보고 어느 포인트에서 왜 못 풀었나 원인을 파악하는 거죠. 메타인지 대다내...
2.3 문제 해결 전략
이 부분 읽다가 끊겼는데 다음 글에서 정리하는걸로
20220419~20
문제 풀이의 사고 도구들이 유용한 순서로 나열되어 있습니다. 각각에 대한 자세한 설명이 있는데 아직은 잘 모르겠네요. 이렇게까지 해야해? 랑 똑똑한 사람들은 이런 도구를 쓰는구나... 하는 두 가지 생각이 교차하네요.
- 직관, 직관이 안 되면 아래의 체계적인 접근들 (체계적인 접근을 위한 질문들 나열)
- Q. 비슷한 문제를 풀어본 적이 있던가?
: 풀이 방법을 재활용하려면 풀이 원리를 체득하고 있어야 함 - Q. 단순한 방법에서 시작할 수 있을까?
: 단순한 알고리즘은 기준선이 될 수도 있고, 효율적인 알고리즘의 기반이 될 수도 있음 (개선하고 또 개선하고)
- 완전 탐색 -> 너비 우선 탐색, 동적 계획법 - Q. 내가 문제를 푸는 과정을 수식화할 수 있을까? (* 수식이 중요한 게 아니라 내가 푸는 과정이 중요한 포인트)
: 영감이 필요한 문제 - 샘플을 입력해서 손으로 직접 풀어보기 - Q. 문제를 단순화할 수 없을까?
: 문제의 쉬운 변형판 풀어보기, 변형판의 해결방법이 원래 해결법의 연장선일 수 있음 - Q. 그림으로 그려볼 수 있을까?
: 인간은 시각적 동물, 직관 획득 가능 - Q. 수식으로 표현할 수 있을까? (수학적 조작)
: 수식 최적화가 도움될수도 - Q. 문제를 (여러개의 부분으로) 분해할 수 없을까?
: 예시: 제약조건을 분해 - 요구조건 1, 2로 분해한 뒤 요구조건 2를 1로 수식적으로 변환 - Q. 뒤에서부터 생각해서 문제를 풀 수 있을까?
: 정방향 탐색은 어려운데 역방향 탐색은 쉬운 경우 등 (사다리 위치 찾기) - Q. 순서를 강제할 수 있을까?
: 순서가 없으면 탐색 공간이 발산하는 경우, 순서를 강제해서 가능성을 제한할 수 있음, 순서를 제한해도 문제가 없는 경우 효과적 - Q. 특정 형태의 답안을 고려할 수 있을까?
: "정규화" (canonicalization) - 결과적으로 똑같은 것들로 묶은 뒤 대표만 고려 (원형을 감싸는 문제)
2.4 더 읽을거리 - 책 추천입니다. "어떻게 문제를 풀 것인가(How to Solve It)" - 책 내용을 보아하니 원서를 보는 편이 나을듯.
이 글은 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 조금씩 읽고 정리한 것입니다.
- 정리된 내용은 본문의 설명과는 다를 수 있습니다.
- 잘못된 내용에 대한 책임은 지지 않습니다.
- 이벤트 아니에요 그냥 공부하는 겁니다.