알고리즘 문제해결 전략

문제 해결 능력:

언어의 특성, 하드웨어와 운영체제에 관한 지식,라이브러리들에 대한 유의사항, 메모리,시간제한, 재사용성 등

제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력

 

프로그래밍 대회에서 배울 수 있는 것

1.텍스트 기반의 문제이기 떄문에 문제를 해결하는 데이만 집중할 수 있음

2. 시간제한과 메모리 제한을 통해 적절한 알고리즘과 자료구조를 공부하는 데에 도움이 되고 더 나아가 원칙들을 이해    하고 변형하는 연습을 통해 주제들을 깊이 이해하는 데 큰 도움이 된다.

3. 테스트 케이스가 많아 정답과 오답이 명확하다. 오류의 존재를 모르고 넘어갈 가능성이 적다. 정답여부의 빠른  객관적인 피드백을 받을 수 있다. 

4.프로그램의 정보가 실시간으로 제공되기 때문에  프로그램의 효율성을 신경쓰게 되고 수행 성능을 예측하는 것에 익숙해진다. 

5. 대형 프로젝트에서 간과했던 프로그램의 작은 부분에 집중할 수 있는 계기가 된다.

6. 경쟁 상황에서 코드를 작성하기 때문에 실력을 늘리기 좋은 동기가 되며 전세계의 고수 프로그래머들이 짠 코드를 직     접 보고 비교해 볼 수 있는 기회가 된다.

 

문제 해결 방법론, 코딩과 디버깅에 대한 주의사항, 알고리즘의 정당성 증명과 효율성 분석에 대한 내용들을 잘 이해해야 이후의 주제들에 대해 피상적으로만 이해하지 않을 수 있다.

1.연습문제는 풀어보기

2. 본인의 코드와 책에 실린 풀이를 비교하기

 

국내 프로그래밍 대회

한국 정보 올림피아드

ACM-ICPC  :대학생 대상 ,3명이 한팀

탑코더

구글 코드 잼

기타 온라인 대회와 모의고사들 :탑코더,코드포스,바야돌리드 대학교 온라인 채점 사이트

팀 단위 연습을 위한 조언

종이 위에 스케치하기 :자료구조, 함수의 이름과 역할,의사 코드

역할 분담: ex) 코딩2명,한명은 문제보기

페어 프로그래밍 연습:

키보드 잡는 사람- 프로그램작성하면서 생각을 말하기 , 보는 사람 - 배열 크기등 실수할만한 지점 눈여겨 보기

디버거 없이디버깅하기

문제 해결 알고리즘

1. 문제를 읽고 이해한다.

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

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

4. 계획을 검증한다.

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

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

 문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배우지 못하는 경우가 더 많다. 두 번째로 문제를 풀 때는 더 효율적인 알고리즘을 찾거나 간결한 코드를 작성할 수도 있고 같은 알고리즘을 유도할 수 있는 더 직관적인 방법을 찾을 수도 있다.

효과적으로 회고를 수행하는 방법: 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남기는 것.

1문제의 간단한 해법

2.어떤 방식으로 접근했는지

3.문제의 해법을 찾는 데 결정적이었던 깨달음은 무엇이었는지.

오답원인 적기, 다른 사람의 코드 보기

문제를 풀지 못해 다른 사람의 코드 볼떄-> 복기 꼭 학기

: 자신이 문제를 해결할 때 취했던 접근들을 살펴보고 왜 이 풀이를 떠올리지 못했는지 살펴보기

문제 해결 전략

직관과 체계적인 접근

체계적인 접근

1.비슷한 문제를 풀어본 적이 있던가? 이전에 적용했던 방법 사용 (동작과 원리를 완벽하게 이해)

2.단순한 방법에서 시작할 수 있을까? 효율적인 알고리즘도 단순한 알고리즘을 기반으로 구성된 경우가 많다.                                                     ->효율적인 자료구조사용, 계산 과정에서 중복계산 없애기

3.내가 문제를 푸는 과정을 수식화 할 수 있을까?

4.문제를 단순화할 수 없을까? 문제의 좀 더 쉬운 변형판을 먼저 풀어보기 . 워 문제의 답은 부분 문제의 합과 같다.

5.그림으로 그려볼 수 있을까?

6.수식으로 표현할 수 있을까?

7.문제를 분해할 수 있을까?

8.뒤에서부터 생각해서 문제를 풀 수 있을까?

9.순서를 강제할 수 있을까?

10.특정 형태의 답만을 고려할 수 있을까?

출처: 알고리즘 문제해결전략1