[Algorithm] 알고리즘 공부 시작 방법 및 순서

초보자 입장에서 알고리즘 공부를 시작하고 싶어서 뭐부터 해야 좋을지 조사하다가, 자료가 좀 모여서 포스트를 작성하게 됐다. 완전 심도 있게 학습한다기보단 공부할 것 체크리스트 정도가 되겠다.

알고리즘?

주위의 개발자들을 둘러보면, 막 입사한 주니어 개발자부터 연차가 살짝 쌓인 개발자까지 이 말버릇을 가지고 있다.

“아 알고리즘 공부 해야되는데.”

그들은 당장 회사의 실무를 처리해야 하는 입장이니, 알고리즘처럼 코드의 효율성을 높이는 공부는 자연스레 순위가 밀려나는 것처럼 보인다. 반면, 개발 분야 취직을 준비하는 사람들은 기업 입사를 위한 코딩 테스트 때문에 준비하는 경우가 많은 것 같다. 나의 경우엔 같은 문제를 훨씬 빠르고 간단하게 푸는 다른 사람들의 코드를 구경하고 싶어서 알고리즘 공부를 시작하려고 한다.

물론 주로 사용하는 언어의 기본 문법을 알고 있으면, 굳이 이론 공부를 하지 않아도 제법 많은 문제를 풀 수 있을 것이다. 하지만 우리의 목표는 ‘일단 정답 나와라!’가 아니라, ‘문제를 쉽게 파악하고, 효율적인 방법이 딱 떠오르고, 큰 수나 많은 수를 넣어도 안정적인’ 코딩을 하는 것이라 믿는다. 그러기 위해 많은 사람들이 필요하다고 하는 개념을 얕고 빠르게 정리해보았다.

알고리즘이란?

시작하기에 앞서 간단히 기초를 짚고 넘어가자.

알고리즘은 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것이다. 예를 들어 일상 속에서는 다음과 같은 알고리즘을 찾을 수 있다.

• 집에서 학교로 가는 길 찾기
• 샌드위치 만드는 방법
• 매점에 가서 물건 구매하기

최단 거리 혹은 최단 시간 내에 학교에 가는 길을 찾는 것, 샌드위치를 만들기 위한 재료를 준비하고 조리 순서를 진행하는 것, 매점에서 물건을 집고 계산하는 것까지 모두 알고리즘이라 할 수 있다.

프로그래밍에서 알고리즘은 input 값을 통해 output 값을 얻기 위한 계산 과정을 의미한다. 이러한 문제를 해결할 때, 정확하고 효율적으로 결과값을 얻기 위해서 알고리즘이 필요하다.

알고리즘의 조건

좋은 알고리즘을 만들기 위해서는 다음과 같은 조건을 충족시켜야 한다.

• 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.
• 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다. 즉 모든 입력에 하나의 출력- 이 나오면 안 된다.
• 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
• 유한성 : 유한 번의 명령어를 수행 후 유한 시간 내에 종료한다.
• 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다

공부 순서

나는 사용할 프로그래밍 언어를 정했고, 문법과 클래스를 어느 정도 알고 있는 상태이기 때문에 아래와 같은 순서로 공부를 진행하기로 했다.

1. 기본 개념 이해
2. 기본 알고리즘 코드 학습

3. 쉬운 문제 풀기
   …

4. (어려운 개념 이해 & 문제 풀기)

이 중 1~3번의 과정을 아래에 서술해두었다.

알고리즘 공부 시작하기

1. 기본 개념 이해

알고리즘에 흔히 쓰이는 개념에 대한 이해를 하기 위해 책이나 인터넷을 찾아보았다.

1) 알고리즘 책

사실 어느 한 분야를 깊게 공부하기 위해서는 책 한 권 사고 시작하는 게 진리이다. 그런데 책을 이미 샀다면, 이 글을 읽고 있지 않을 것 같다.

2018년 11월 국내에서 판매량 높은 알고리즘 입문서는 아래와 같다. (book.naver.com 기준)

• 구종만, 『알고리즘 문제 해결 전략세트』, 인사이트
• 이승찬, 『모두의 알고리즘 with 파이썬』, 길벗
• 보요 시바타, 『Do it! 자료구조와 함께 배우는 알고리즘 입문』, 이지스퍼블리싱

2) 온라인 사이트

공부할 내용이 워낙 방대하기 때문에, 알고리즘의 A-Z의 모든 내용을 담은 무료/한글 사이트는 찾기 힘들었다. 온라인으로만 공부하려면 여러 곳을 돌아다니며 공부해야 할 것이다. 그렇기 때문에 책을 사는 것이 덜 성가신 방법이 될 수 있다.

그 와중에 LibreWiki 라고, 한 페이지에 보기 좋게 정리한 사이트를 찾았기 떄문에 공유해본다.

• LibreWiki

이외에 소개해주고 싶은 사이트는 개념 이해에 참고가 될만한 사이트들이다.

visualgo 는 정렬, 트리 등의 원리를 이해하기 쉽게 시각화하여 한 단계씩 나타낸 사이트이다.. 그림과 코드가 한 화면에 나오고, 재생 버튼을 누르면 순차적으로 for 반복문을 따라 알고리즘 진행 과정을 보여준다.

• visualgo

  

Geeksforgeeks 사이트는 영어로 되어있긴 하지만, 알고리즘 예시와 함께 C++, 자바, 파이썬 코드로 작성된 예시를 함께 볼 수 있어서 도움이 되었다.

• geeksforgeeks

3) 인터넷 강의

알고리즘에 관한 강의는 많다. 슬프지만 대부분 유료이다. 개발 분야 커뮤니티나 지인의 얘기를 들어보면 ‘최백준’ 강의가 유명한 것 같다. 구글 검색결과와 유튜브를 잘 뒤지면 무료 기초 강의도 찾을 수 있다.

• https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/
• https://educast.com/11.410/

4) 앱

앱으로 완벽히 공부할 수는 없지만, 접근성이 좋은 것은 사실이다. 개인적으로 간단하고 쉬워서 도움이 많이 된 앱은 알고리즘 도감 이라는 앱이다. 위에 설명한 visualgo와 비슷하게 한 단계씩 천천히 알고리즘을 설명해주고, 간단한 예제도 지원해서 입문자에게 추천하고 싶은 앱이다.

• 알고리즘 도감 AppStore PlayStore
  

그리고 geeksforgeeks 역시 앱이 있는데, 안타깝게도 영어로 된 앱이다. 하지만 코드가 언어별로 상세히 나와있어서 익숙해지면 큰 도움이 될 것 같다.

• geeksforgeeks AppStore PlayStore

* 알고리즘에 필요한 기본 개념

이 포스트에서 모든 기본 개념을 상세히 설명하지는 않을 것이다. 나도 아직 학습하는 입장이기도 하고, 한 번에 설명하기엔 내용이 너무나 많기 때문이다. 기초적인 개념과, 어떤 것들이 있는 지 짚고 넘어가는 정도로만 작성할 것이다.

3줄 요약:

• 시간 복잡도
• 자료구조
• 정렬

시간 복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계 프로그램을 작성할 때에 입력의 크기에 따라서 프로그램이 계산하는 횟수가 크게 달라진다. 입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있다. 이것을 알고리즘의 시간 복잡도라 한다.

cf. 메모리 공간을 얼마나 차지하느냐를 계산하는 공간 복잡도라는 개념도 있지만, 저장 기술의 발달로 인해 현재는 시간 복잡도를 우선 고려하는 경우가 많다.

시간 복잡도를 나타낼 때에는 Big O 표기법을 이용한다. 예를 들어서, 1부터 n까지의 합을 구한다고 할 때, 다음과 같은 두 가지 방법이 있다.

// 방법 1
int n, res = 0;
for (int i = 1; i <= n;, i++) {
    res += i;
}
System.out.println(res);

// 방법 2
int n, res = 0;
res = n*(n+1)/2;
System.out.println(res);

코드를 살펴보면 방법1에서는 for를 이용해 n번의 연산을 하기 때문에 O(n) 의 시간 복잡도를 가진다. 반면 방법2에서는 n의 크기와 상관 없이 1번의 연산을 하기 때문에 O(1) 의 시간 복잡도를 가진다.

맨 위에서부터 시간 복잡도가 낮고 빠르고, 아래로 갈 수록 시간 복잡도가 높고 느려진다. 제한된 시간 안에 올바르게 output을 출력하려면 시간 복잡도를 낮춰야 할 것임을 알 수 있다.

자료구조

국내, 국외, 재직자, 면접관 등등 알고리즘 관한 포스트를 읽으면서 모든 사람이 강조하는 것이 자료구조에 대한 공부를 탄탄히 하라는 것이었다. 대기업 코딩테스트나 어려운 알고리즘 문제에서는 자료구조를 모르면 풀지 못 하는 문제도 많다. 흔히 말하는 ‘프로그래밍 잘 하는 법’에서도 빠지지 않는다.

자료구조란, 데이터 사이의 관계를 반영한 저장구조 및 그 조작 방법을 뜻한다. 컴퓨터의 프로그램을 실행하면 CPU에서 메모리로 데이터를 이동해서 처리하는데, 이 때 메모리를 효율적으로 사용하기 위해 데이터에 맞는 특성의 자료구조를 사용하는 것이 중요하다.

자료구조를 모두 나열하자면 아래 표와 같이 다양한 종류가 있다.

출처 - 초보몽키의 개발공부로그

이 중에 선형 구조와 비선형 구조의 개념과 종류가 알고리즘 문제에 출제되는 것 같다.

• 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조.
• 비선형 자료구조 : 선형 자료구조가 아닌 모든 자료구조. i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조.

자세한 내용은 출처 - LibreWiki

정렬

Tony 님의 Medium에 그림과 함께 친절하게 한글로 설명되어있다. Tony Medium - 정렬 알고리즘

그리고 언제나 나무위키는 공식적으로 참조하기 망설여지지만, 이 페이지는 정리가 잘 되어있다. 각 정렬마다 이해를 돕는 동영상이 첨부되어있다. 나무위키 - 정렬 알고리즘

• 버블 정렬 - 가장 쉽지만, 시간 복잡도가 높아 효율적이진 않다.
• 선택 정렬 - 버블 정렬과 알고리즘이 유사하다. 가장 큰 수를 찾아 배열의 마지막 위치와 교환한다.
• 삽입 정렬 - 인덱스를 설정하여 현재 위치의 값을 아래쪽으로 순회하며 알맞은 곳에 넣어준다.
• 병합 정렬 - 정렬한 리스트를 반으로 쪼개며 좌우 리스트를 분할해 정렬 후 병합한다. 가장 많이 쓰이는 정렬 중 하나이다.
• 힙 정렬 - 힙이라는 자료구조를 통해 내림차순으로 숫자를 넣은 후, 역순으로 꺼내어 정렬한다.
• 퀵 정렬 - pivot 기준으로 좌측과 우측으로 작은 값과 큰 값을 재배치하고 분할하여 정렬한다.

기타 공부하면 좋을 주제들

위에서 언급된 것 말고도 다양한 주제들이 있다. 알고리즘 사이트에 가 보면 문제를 선택할 때 주제 별로 필터링을 할 수 있다. 모두 당장 암기가 필요하다기보단, 알고리즘을 풀다가 한 문제씩 튀어나올 때에 ‘이런 풀이법으로 풀면 되는구나’ 하고 자연스럽게 패턴으로 익히는 것이 좋아보인다.

• 다이나믹 프로그래밍(동적 계획법)
• 탐욕법
• 유클리드 호제법 (최대공약수, 최소공배수)
• 비트 연산
• 진수 변환
  …

HackerRank 사이트 우측 하단에서 주제 별로 문제를 선택할 수 있는 모습.

참고: algopost - 알고리즘 대회에 필요한 수학

2. 기본 알고리즘 코드 학습

기초적인 원리를 이해했다면, 코드로 어떻게 풀어 나가는지 예제 알고리즘을 공부한다. (정형화된 풀이 공식)

만약 자료구조 중 배열에 대해 공부했다면 List와 Array가 어떻게 다른지, 코드로 어떻게 작성하고 어떤 클래스와 함수를 쓸 수 있는지 파악한다. 여기서 헷갈린다면 언어에 대한 문법을 다시 복습할 필요가 있다.

코드로 작성하는 것에 대해서는 geeksforgeeks에 예시가 상세하게 잘 나와있다. 아래는 위상 정렬(DFS)에 대한 그림과 C++, JAVA, Python 코드 예시이다. 구글 번역기와 함께라면…!

Geeks for Geeks 풀이 샘플

그 후에는 직접 작성해보는 것도 좋을 것 같다. main 함수가 어떻게 생겼는지 다시 한 번 살펴보기도 하고, IDE의 자동 완성이나 Import에 익숙해지지 않게 직접 코드를 쳐 가면서 연습해 둔다. 그러면 실전이나 핸드코딩에서 머릿속이 하얘지는 건 막을 수 있지 않을까.

3. 쉬운 문제 풀기

다양한 레벨이 존재하기 때문에 쉬운 레벨부터 풀어본다. 보통 언어, 난이도, 주제(검색, 정렬 등) 에 따라 필터링하여 문제 검색이 가능하다.

(내가 아는)

국내 사이트

• 백준(BOJ)
• 프로그래머스
• 알고스팟
• 코딩도장

(내가 아는)

해외 사이트

• Hackerearth
• Hackerrank
• Codeforces

주워 들은 팁

많은 사람들이 공통적으로 얘기하는 사실들이 있다.

• 처음부터 어려운 걸 하려고 하지 말고, 간단한 것부터 시작하자.
• 선택한 언어의 문법과 클래스를 잘 파악하자.
• 풀고 난 후 다른 사람의 풀이 참고하자.
• 경험이 쌓이면 익숙해진다. 조급해하지 말자.
  

References

• https://code.plus/
• http://baactree.tistory.com/52
• https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://ko.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/v/what-are-algorithms
• https://opentutorials.org/course/2471/13912
• https://librewiki.net/wiki/%EC%8B%9C%EB%A6%AC%EC%A6%88:%EC%88%98%ED%95%99%EC%9D%B8%EB%93%AF_%EA%B3%BC%ED%95%99%EC%95%84%EB%8B%8C_%EA%B3%B5%ED%95%99%EA%B0%99%EC%9D%80%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B3%BC%ED%95%99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B8%B0%EC%B4%88
• https://medium.com/@fiv3star/%EC%A0%95%EB%A0%AC%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-sorting-algorithm-%EC%A0%95%EB%A6%AC-8ca307269dc7
• https://wayhome25.github.io/cs/2017/04/17/cs-18/