알고리즘

문제 해결을 위한 일련의 사고 방식, 절차. 어? 이왜진?..

코딩 테스트

코딩 테스트를 잘 보기 위해선 일단 문제를 봤을 때 이 문제는 어떤 자료구조를 이용해야 하고 어떤 알고리즘을 이용해야 할 지를 잘 파악해야 한다.
물론 문제를 많이 풀어 보는 것이 장땡이다.
기본적으로 네카라쿠배 코딩테스트에 합격하기 위해서는 프로그래머스에서 레벨 3 정도는 풀어야한다. 그 밑에 기업 같은 경우는 레벨 2 정도만 풀어도 충분하다. 가끔 어려우면 레벨 3정도.

알고리즘 종류

크게 알고리즘은 4가지로 분류된다. 완전 탐색 , 그리디 , 분할 정복, 동적 계획법
( NP문제를 위한 근사 알고리즘도 있지만 코딩 테스트에 나올 수 없다고 생각하기에 제외.)

우리가 일반적으로 알고리즘이라고 배우는 DFS, BFS, 다익스트라 , 플로이드와샬, 프림 , 크루스칼, 머지 소트, 이분 탐색 등등 모두 위 4가지의 알고리즘에서 특정 문제 상황을 해결 하기 위한 방법으로 탄생한 것이다.
다익스트라 같은 경우는 한 노드에서 다른 노드까지의 최단 경로를 구하는 상황에서 그리디 알고리즘을 이용한 것이라 볼 수 있다.
DFS, BFS도 완전 탐색을 위한 방식으로 탐색의 기준을 정해 놓은 것이라 볼 수 있다.

여기서 하고 싶은 말은 쨋든 4가지 알고리즘으로 귀결 된다는 것이다!

알고리즘 공부 방식

물론 완전 탐색 , 그리디 , 분할 정복, 동적 계획법 4가지만 공부 하라는 것은 아니다. 빠른 시간안에 문제를 해결해야 하는 코딩 테스트에서는 문제 상황에 바로 바로 적용해서 풀 수 있도록 최단 경로 구하는 방법, 최소 신장 트리 구하는 방법 등 다양한 알고리즘을 알고 있어야 하긴 한다.

하지만 당연히 코딩 테스트를 볼 때 딱 보고 "아 이 문제는 다익스트라 이용해야겠다" 이런 문제는 웬만하면 모든 사람들이 맞출 것이다. 어려운 문제는 문제를 봤을 때 그냥 아무 생각도 안나고 완전 탐색으로 풀면 시간 초과 날 게 뻔히 보인다. 이럴때 접근해야 하는 방식이 기본으로 돌아가는 것이다. 바로 완전 탐색 , 그리디 , 분할 정복, 동적 계획법 이 4가지 중 하나로 돌아가서 생각해보는 것이다.

다음 포스트에서는 어떤 문제를 완전 탐색 ,그리디 ,분할 정복 ,동적 계획법 중 무엇으로 풀어야 할 지에 대해 알아보자.

---

다양한 알고리즘을 먼저 공부하고 싶으면 백준 단계별 풀어보기를 추천 한다. 40단계까지 풀어보면 어지간한 알고리즘들은 맛보기로 풀어 보았다고 할 수 있을 것이다.