2022.07.11

p1~p50

지식을 진정 자신의 것으로 만들어 활용할 수 있기 위해서는 학문이 발전하는 과정에서 일어난 발견과 깨달음을 학생 자신이되짚어갈 수 있어야 한다. 프로그래밍 대회는 알고리즘들을 베껴 쓰기만 하면 해결할 수 있는 문제만 있는 것이 아니라 알고리즘에 사용된 원칙들을 이해하고 변형해야 풀 수 있는 문제들이 많이 출제되므로 이런 경험과 깨달음을 얻기 위한 좋은 통로임. 

 

많은 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력은 분야를 막론하고 좋은 프로그래머가 되기 위한 필수 조건

프로그래머가 사용하는 언어나 라이브러리, 알고리즘에 대한 지식들 = 퍼즐 조각, 문제 해결 능력 = 적재적소에 퍼즐을 배치하고 이들을 연결해서 큰 그림을 만드는 능력 

 

프로그래밍 대회는 다양한 알고리즘 설계 기법과 자료 구조를 직접 사용해 볼 수 있는 계기가 된다. 알고리즘에 사용된 원칙들을 이해하고 변형해야 풀 수 있는 문제들이 많이 출제되기 때문에. 

 

연습 문제들을 단순히 본문의 연장처럼 읽어 내려가지 말고, 멈춰서 가능한 한 직접 풀어보려고 시도하는 것이 좋다. 이 책의 문제들은 모두 알고스팟에서 채점 받을 수 있다. 

 

문제 해결 뒤 책에 실린 소스와 비교하기 

대회들 

ACM-ICPC(ACM 대학생 프로그래밍 경시대회)

탑코더 

구글 코드 잼 

 

대회 준비를 위한 조언 1. 가능한 한 많은 문제 풀기,(공부해야할 주제의 다양성에 압도되어서 교과서와 다른 자료들을 최대한 많이 읽으며 배경 지식을 느리리는 데 주력하는 실수를 하지 말자. 복잡한 알고리즘을 하나 더 아는 것 보다 중요한 것은 실제로 자신이 아는 것을 이용해 문제를 풀 수 있는 능력이다.) 2. 온라인 채점 사이트 이용하기, 3. 가능한 한 많은 프로그래밍 대회에 참가하기 (팀 단위 연습을 위한 조언: 종이 위에 답안 스케치하기, 치밀한 역할 분담, 페어 프로그래밍 연습, 디버거 없이 디버깅, 인쇄 대기 감소를 위한 두 화면 분할, 팀 노트북 준비)

 

프로그래밍 대회 준비하기 좋은 교과서들: Introduction to Algorithms, Programming Challenges, The Art of Computer Programming, 프로그래밍 콘테스트 챌린징

 

단순 반복으로는 문제 해결 능력을 기를 수 없음. 문제를 푸는 것이 아니라 문제를 푸는 기술을 연마해야 함. 자신이 문제를 어떤 방식으로 해결하는지를 의식하고 어느 부분이 부족한지, 어떤 부분을 개선해야 할지 파악해야 함. 

 

문제 해결 과정을 단계별로 나누기 

문제 해결을 위해 거쳐야 하는 과정들을 세분화함으로써 어디가 부족하고 어디를 개선해야 하는지를 판단할 수 있게 됨. 프로그래밍 대회를 위한 여섯 단계 문제 해결 알고리즘: 1. 문제를 읽고 이해한다. 2. 문제를 익숙한 용어로 재정의한다. 3. 어떻게 해결할지 계획을 세운다. 4. 계획을 검증한다. 5. 프로그램을 구현한다. 6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다. 

1.(조급한 마음에 그림과 입출력 예제만을 보고 문제가 원하는 것을 유추하지 말 것) 2. 문제의 추상화를 통해 자신이 다루기 쉬운 개념을 이용해서 문제를 자신의 언어로 풀어 쓰기 3. 사용할 알고리즘과 자료구조 선택하기, 문제를 어떻게 해결할지 계획 세우기 4. 계뢱 검증하기(구현 전에 해야 함) 5. 6. 장기적으로 가장 큰 영향을 미치는 단계, 자신이 문제를 해결한 과정을 돌이켜 보고 개선하는 과정. 문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배우지 못하는 경우가 더 많음. 다른 사람 코드 보기, 코드 남기기

 

문제 일정 시간이 지나도록 고민해도 모르겠을 때는 다른 사람 풀이 참조하기. 단 자신이 문제를 해결할 때 취했던 접근들을 되새겨 보고 자신이 왜 이 풀이를 떠올리지 못 했는지 살펴봐야 함. 

 

문제해결 전략 1. 직관과 체계적인 접근. 전체적인 얼개를 그릴 수 있어야 함. 체계적인 접근을 위한 질문들 -> 1. 비슷한 문제를 풀어본 적이 있던가? 2. 단순한 방법에서 시작할 수 있을까? = 무식하게 풀 수 있을까? 3. 내가 문제를 푸는 과정을 수식화할 수 있을까?(손으로 여러 간단한 입력을 직접 해결해 보면서 새로운 방향에서 접근해야 하는 영감이 필요한 문제 해결) 4. 문제를 단순화 할 순 없을까? 5. 그림으로 그려볼 수 있을까? 6. 수식으로 표현할 수 있을까?(평문으로 쓰여진 문제를 수식화하기) 7. 문제를 분해할 수 있을까?(더 다루기 쉬운 형태로 문제 변형하기) 8. 뒤에서부터 생각해서 문제를 풀 수 있을까?(문제에 내재된 순서 변형하기) 9. 순서를 강제할 수 있을까?(ex. 특정 순서대로 칸들을 눌러야 한다는 제약 문제에 추가하기) 10. 특정 형태의 답만을 고려할 수 있을까?(정규화 기법. 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법)

 

읽기 쉬운 코드를 작성해야 프로그래밍 대회 성적 올릴 수 잇음. 좋은 코드를 짜기 위한 원칙. 1. 간결한 코드 작성하기 2. 적극적으로 코드 재사용하기(코드 모듈화, 반복되는 코드는 함수나 클래스로 분리해 재사용한다.) 3. 표준 라이브러리 공부하기 4. 항상 같은 형태로 프로그램을 작성하기 5. 일관적이고 명료한 명명법 사용하기 6. 모든 자료를 정규화해서 저장하기(같은 자료를 두 가지 형태로 저장하지 않는다!) 7. 코드와 데이터를 분리하기 (코드의 논리와 상관 없는 데이터는 가능한 한 분리)