알고리즘 공부법

                                                                                                                                                         

                                                                                                                                                                                                                   

                                                                                                                                                         

                                                                                                                                                                                                              

                                                                                                                                                                                                                   

 

알고리즘 공부법

• 알고리즘에 대한 기본적인 이해와 지식을 알고 있어야 한다.

  알고리즘 분류에 따라 문제가 있는 이 페이지를 활용한다. 푼 사람 수가 많고, 문제 정답률이 높은 순서대로 풀어보면서 본인이 확실하게 그 알고리즘을 제대로 이해했는지 테스트한다. 어떤 알고리즘을 사용해야 할 지 알고 문제를 풀어나가면 된다.

 

• 분류되지 않은 다양한 문제를 통해, 내 스스로 알고리즘을 구현하여 해결한다.

  어떤 문제가 주어졌을 때에 그 문제가 가진 고유한 특성과 조건들을 활용하여 본인이 직접 알고리즘을 고안해본다. 예를 들어 문제에서 주어진 상황을 직접 그래프로 모델링 한 결과, 최단거리를 구해야하고 따라서 Dijkstra 알고리즘을 사용하면 되겠다라고 생각할 수 있겠다. 수행시간을 더 줄이기 위해서 힙을 써야겠다는 생각을 할 수도 있겠다.

  이 연습을 위해서는 이 페이지에서 세부 항목으로 들어가 1번부터 순서대로 풀어본다. 4번까지 해결할 수 있다면 Professional에 해당하는 실력, 5번과 6번까지 해결하면 Expert의 실력. 풀이는 COCI 공식 홈페이지에서 출처를 따라들어가면 된다. 모범 해법, 코드, 데이터까지 모두 다 다운로드 받을 수 있다.

 

• 본인이 고안한 알고리즘을 1)정확하게, 2)수행시간이 짧게, 3)빠른 시간 내에 구현할 줄 알아야 한다.

  Professional과 Expert 두 시험에서는 모두 정확하게 코딩하는 것이 가장 우선시 된다. 시험 시간이 넉넉하기 때문. 알고리즘 고안에만 너무 시간을 할애하지 않는다면, 구현할 시간은 충분할 것이다.

  그 다음으로 본인의 코드 수행시간에 주의해야 한다. 입력의 크기가 매우 클 수 있음을 가정하지 않는다던가, 전처리를 하여 결과를 저장해두면 반복적으로 계산할 필요가 없음에도 이를 놓치는 경우 등이 있을 수 있겠다.

  하지만, 알고리즘 공부에서의 구현 능력은 실무에서의 구현 능력과는 거리가 있기 때문에 사내 문제해결 사이트 또는 백준온라인저지(acmicpc.net), koitp.org 등에서 많은 연습이 필요하다.

  구현에서 실수가 생겼는데 며칠을 고민해도 못 찾을 경우, 커뮤니티 등의 질문 게시판을 활용하거나, 다른 분들께 도움을 요청하여 꼭 확인하고 넘어간다.

 

• 알고리즘 시험을 잘 보는 법

  1. 문제를 꼼꼼하게 읽고 완전히 이해해야 한다. 조건들을 단 하나도 놓쳐서는 안 된다. 엉뚱한 문제를 시간 내내 푸는 경우도 있다.
  2. 할 수 있는 한 끝까지 최선을 다 한다.
     1. 어떻게 풀어야 할 지 잘 모를 때는, 문제의 크기를 작게 쪼개어, 손으로 이런저런 방법들을 직접 시도해 보면서 규칙을 유도해 보거나 패턴, 성질 등을 찾으려 노력해야 한다.
     2. 테스트 시에 시간이 남았더라도, 할 수 있는 한 큰 데이터를 손으로 직접 만들어서 넣어 본 후, 제한 시간을 초과하지 않는지 확인해 보아야 한다. 최대 데이터에 대해서 너무 느리게 나온다면, 이전까지 작성한 코드를 다른 곳에 안전히 보관해 둔 후, 시험이 끝나기 전까지 최적화 작업에 몰두한다.

 

• 실전 팁

  • 양보다는 질이다. 좋은 문제를 풀어야 실력이 는다.
  • 연습하는 단계라면 이미 검증된 문제를 푸는 것이 좋은 방법. koosaga의 내가 문제풀이를 연습하는 방법을 참고. 문제 퀄리티가 좋다. 기본적으로 난이도가 높다. 하지만 어느정도 실력이 된다면 bronze~silver 초반까지는 풀 수 있을 것. 조금씩 난이도를 높여가며 문제를 해결하는 것을 추천. 공식 페이지에 모든 solution이 공개되기 때문에 공부에 적합하다. 한국정보올림피아드 문제는 기본적으로 DP, 그래프 등 전형적인 알고리즘 문제 해결 능력을 키우는 데 도움이 됨. 처음 공부할 경우, 초등부 문제도 벅찰 수 있다. 하지만 하나씩 풀다보면 실력을 키울 수 있다.

  ---

  언어는 어느 정도 익숙한데, 코딩이 막히는 경우,

  • 내가 20분 내로 코딩할 수 있는 문제

  • 풀이를 알고, 구현만 남은 문제

    를 푼다.

    생활과 병행하기 위해 하루에 문제를 8문제 내외로 푼다.

  ---

  그 외에는 BOJ에서 @automata 님이 만든 문제집인 C++ 배우기(1~50) 에서 C++ 배우기(351~400) 를 추천. 때에 따라 문제집에 빌런이 있으니 이건 아니다 싶은 문제는 버린다. 1000명 이상이 해결한 문제는 랭작 수준의 난이도. 삼성 코딩테스트 문제+백준 강의 문제를 제외하고는 그렇다. 코딩테스트는 우선 기출을 푸는게 제일 좋다. 그렇기에 1000명이상이 푼 문제들은 북마크를 해서 모아둘 수도 있고, 500명 이상이 푼 문제 중에서 해답이 떠오르는 문제를 북마크해서 풀 수도 있다.

  ---

  한 문제를 오래 붙잡는 경우, 시간낭비. 붙잡는다는 것은 솔루션이 떠오르지 않아 아무 진척도 없는 단계 를 의미한다. 약 1시간 정도. 그 이상의 고민은 실력 향상에도 도움이 되지않고, 본인의 실력이 아직 충분하지 않다는 것. 이럴 때는 해답을 보는 것을 추천. 그렇다고 solution을 그대로 내는 것, 보고 받아쓰기 하는 것은 절대 안된다. 그렇게 하는 순간, 그 문제는 앞으로 안볼것이고 그 문제에서 얻을 수 있는 지식은 내 것이 아니다. 솔루션을 보고도 이해하지 못한다면, 이를 위한 내용을 공부하거나 문제를 보류하는 것을 추천. 결론적으로, 솔루션을 보고 코드를 본다면, 자신이 안보고 코드를 작성해서 제출할 수 있어야 한다. 솔루션이 제공되는 문제들은 많다.

  ---

  주변에 도움을 받을 사람이 없다면, 백준 슬랙을 추천. 백준 슬랙을 포함해 QnA에서 질문에는 룰과 도덕이 있으니 이와 관련해서는 꼭 공지를 읽고, 질문하는 것을 추천.