[Algorithm] 1~2장

알고리즘문제들을 풀면서 기초가 부족함을 점점 깨닫고,이론부터 천천히 다시 공부하려 구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제해결전략" 을 읽고 조금씩 정리해서 올리려 합니다!

알고리즘에 사용된 원칙들을 이해하고 변형해야 풀 수 있는 문제들이 많이 출제

대회를 위한 코드 → 간결하면서 우아한 프로그램 ☞ 좋은 코드!!

프로그래밍하기 전에 생각할 것

• 어떤 자료구조를 사용할 것인가?
• 각 함수의 이름과 역할
• 중요한 부분의 의사코드

class의 형태 → 코드의 블랙박스화

• 코드의 블랙박스화란?
  • 내부의 작동원리나 구조를 이해하지 않고도 외부에서 본 기능이나 사용법을 안다면 충분히 얻을 수 있는 결과를 제공할 수 있는 코드입니다
  • 타이핑이 길어지고 번거롭지만 팀 노트를 만드는 사람과 실제 사용하는 사람이 다르더라고 초기화나 기타 까다로운 점들에 신경을 쓰지 않아도 된다는 장점이 있습니다

파인만 알고리즘

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

• 문제 해결을 단계별로 나누었습니다
• 문제를 적는 단계가 존재
  → 문제를 읽고 이해한뒤, 자신의 언어로 재정의!

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

1. 문제를 읽고 이해한다

• 문제를 잘못읽는 실수, 사소한 제약조건을 잘못 이해하는 경우가 발생할 수도 있습니다.

2. 문제를 익숙한 용어로 재정의한다

• 자신이 다루기 쉬운 개념을 이용하여, 문제를 자신의 언어로 풀어쓰기
• 문제의 추상화
  - 추상화 과정 → 프로그램이 나아갈 방향

3. 어떻게 해결할지 계획을 세운다

• 사용할 알고리즘 과 자료구조 선택
• 가장 많은 고민을 하는 단계

4. 계획을 검증한다

• 설계한 알고리즘이 요구조건을 수행하는지 증명합니다
• 이 단계에서 수행시간과 메모리 제한 을 확인합니다

5. 프로그램으로 구현한다

• 설계한 알고리즘을 바탕으로 프로그램을 작성하는 단계입니다

6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다

• 장기적으로 가장 큰 영향을 끼칩니다
• 문제를 한번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배우지 못하는 경우가 많습니다
• 자신의 경험을 기록으로 남기기 → 저는 블로그에 포스팅하는 방법을 택했습니다!

🥲 문제를 풀지 못할 때

• 일정시간이 지나도록 고민해도 답을 찾지 못할 때에는 다른 사람의 소스코드나 풀이를 참조합니다
• 다른 사람의 소스 코드나 풀이를 참조할 때는 반드시 복기를 동반해야 합니다

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

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