[알고리즘] 알고리즘 공부의 시작..

https://blog.yena.io/studynote/2018/11/14/Algorithm-Basic.html

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

1) 알고리즘 책

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

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

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

 

2) 온라인 사이트

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

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

• LibreWiki

 

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/

 

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

3줄 요약:

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

 

시간 복잡도

시간 복잡도를 나타낼 때에는 Big O 표기법을 이용한다

 

시간 복잡도 설명

 

O(1)	상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다.
O(logn)	로그 형태
O(n)	선형
O(nlogn)	선형로그 형태
O(n2),O(n3),⋯	다차 형태
O(2n)	지수 형태
O(n!)	팩토리얼 형태

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

 

자료구조

정렬

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

기타 공부하면 좋을 주제들

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