-
[Algorithm] 1. 알고리즘 공부 시작방법 및 순서Algorithm/Algorithm 포스팅 2019. 4. 5. 00:09
알고리즘?
알고리즘을 공부하는 이유는 코드의 효율성을 높이기 위해서 공부를 합니다.
기업 입사를 위한 코딩테스트 때문에 공부를 하기도 한다.
내가 알고리즘 공부를 하는 이유 :
문제를 훨씬 빠르고 간단하게 푸는 다른 사람들의 코드를 보면서 실력을 올리고 싶어서 알고리즘 공부를 합니다.
저 같은 경우에는 많은 언어들 중에서 절차지향 언어 1개와 객체지향 언어 1개를 사용합니다.
절차 지향 언어로는 C언어를 선택 했습니다.
C언어는 모든언어의 가장 기본 베이스가 되는 언어이기도 하면서 객체 지향과 달리 좀더 생각을 해서 만들어야 하는 코딩 실력을 필요로 하기 때문에 C언어를 공부합니다.
객체 지향 언어로는 python을 선택 했습니다.
python은 점차 떠오르고 있는 언어인데, 다양한 모듈의 지원이 잘되는 파이썬을 사용하고 있고, 모든 언어중 가장 짧으며 강력한 언어 이기 때문에 객체 지향 언어로 pyhton을 선택해서 공부하고 있습니다.
알고리즘 이란?
알고리즘의 사전적인 의미는 어떠한 문제를 해결 하기 위한 일련의 절차를 공식화 한 형태로 표현 한것입니다.
프로그래밍 에서 알고리즘은 결과값을 얻기 위한 과정이고 정확하고 효율적으로 결과값을 얻기 위해서는 알고리즘이 필요합니다.
공부 순서는?
사용할 프로그래밍 언어를 선택 했으므로 다음과 같은 순서로 공부를 합니다.
-
기본 개념 이해...
-
기본 알고리즘 코드 학습
-
쉬운 문제풀기
......
-
(어려운 개념 이해 & 문제 풀기)
알고리즘 공부하기
알고리즘을 공부 하기 위해서 책을 하나 정도는 구비할만 하다.
인터넷으로 일일히 찾기에는 내용이 너무 방대하며 시간 소모가 생각보다 크기 때문이다.
알고리즘 책 :
국내 판매량이 높은 책을 손꼽아 보자면
-
구종만의 알고리즘 문제 해결 전략 세트
-
이승찬의 모두의 알고리즘 with 파이썬
-
보요 시바타의 Do it! 자료구조와 함께 배우는 알고리즘 입문
정도가 있다.
저같은 경우에는 구종만의 알고리즘 문제 해결 전략 세트와 보요 시바타의 Do it! 자료구조와 함께 배우는 알고리즘 입문 이라는 책을 가지고 있는데 공부하기에 역시 판매량이 좋은 책이라 그런지 공부할때 도움이 많이 된다.
온라인 사이트 :
정렬, 트리 등의 원리를 이해하기 쉽게 시각화 하여 한단계 씩 나타낸 사이트 : https://visualgo.net/ko
영어로된 사이트 이지만, 알고리즘 예시와 함께 c++, java, python 코드로 작성된 예시를 볼수 있다 : https://www.geeksforgeeks.org/
인터넷 강의 :
알고리즘 관한 강의는 많다. 대부분유료이지만 '최백준'강사의 강의가 유명하다고 한다.
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/course/progtheory/DZ62
앱 :
앱으로는 완벽하게 공부를 할수는 없지만, 접근성이 좋은 것은 사실 입니다.
개인적으로 간단하고 쉬우면서 도움이 많이된 앱은 알고리즘 도감 입니다.
기본적인 자료는 무료이지만 난이도 있는 자료는 3900원을 지불해야 볼수 있습니다.
그리고 geeksforgeeks 라는 앱도 있는데 해당 앱은 영어로 되어 있다.
하지만 익숙해지면 도움이 많이 될것이다. 코드가 언어별로 상세히 나와있기 때문입니다.
알고리즘을 공부하기 위해서 필요한 개념이 크게 3가지가 있습니다.
-
시간 복잡도
-
자료구조
-
정렬
시간 복잡도 :
문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 시간복잡도 라고 이야기 하는데 이를 고려 하지 않으면 런타임에러를 계속해서 발생 시킬 것입니다.
시간 복잡도를 나타낼때는 Big O 표기 법을 이용한다.
1부터 N까지의 합을 구한다고 할때 2가지의 방식으로 코드를 작성할수 있습니다.
↑ 1번 코드
↑ 2번 코드
1번 코드는 for 문을 이용해서 n번의 연산을 하게 됩니다. 그래서 시간복잡도로 표현해 보면 O(n)입니다.
2번 코드는 for 문을 사용하지 않고 일반적인 수식으로 표현했기 때문에 n이 몇이든 1번의 연산밖에 하지 않기 때문에 시간복잡도는 O(1)입니다.
이처럼 같은 결과여도 어떻게 코드를 짜느냐에 따라 시간 복잡도가 다릅니다.
-
O(1) : 상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다.
-
O(logn) : 로그형태
-
O(n) : 선형
-
O(nlogn) : 선형 로그 형태
-
O(n2),O(n3),... : 다차 형태
-
O(2n) : 지수 형태
-
O(n!) : 팩토리얼 형태
맨위부터 시간복잡도가 낮고 빠르고, 아래로 갈수록 시간 복잡도가 높아지면서 느려집니다.
자료구조
많은 사람들은 자료구조에 대한 공부를 탄탄히 해두라고 이야기 합니다.
자료구조란?
데이터 사이의 관계를 반영한 저장도구 및 그 조작법을 찾는다는 뜻입니다.
메모리를 효율 적으로 사용하기 위해서 데이터에 맞는 특성의 자료구조를 사용하는 것이 중요합니다.
↑ 자료구조의 종류
이중에서 선형 구조와 비선형 구조의 개념과 종류가 알고리즘 문제로 출제가 자주 됩니다.
-
선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조
-
비선형 자료구조 : 선형 자료구조가 아닌 모든 자료 구조. i번째 값을 탐색한 뒤의 i+1이 정해지지 않는 구조
자세한 내용은 - LibreWiki
정렬
Tony님의 Medium에 그림과 함께 한글로 자세히 설명 되어 있다. - Tony Medium - 정렬 알고리즘
각 정렬마다 이해를 돕는 동영상이 첨부 되어있다. 나무위키 - 정렬 알고리즘
-
버블 정렬 - 가장 쉽지만, 시간 복잡도가 높아 효율적이지는 않다.
-
선택 정렬 - 버블 정렬과 알고리즘이 유사하다. 가장 큰 수를 찾아 배열의 마지막 위치과 교환한다.
-
삽입 정렬 - 인덱스를 설정하여 현재 위치의 값을 아래쪽으로 순회하며 알맞은 곳에 넣어준다.
-
병합 정렬 - 정렬한 리스트를 반으로 쪼개며 좌우 리스트를 분할해 정렬 후 병합한다. 가장 많이 쓰이는 정렬중 하나이다.
-
힙 정렬 - 힙이라는 자료구조를 통해 내림차순으로 숫자를 넣은후, 역순으로 꺼내어 정렬한다.
-
퀵 정렬 - pivot기준으로 좌측과 우측의 작은 값과 큰 값을 재배치하고 분할하여 정렬한다.
따로 공부하면 좋을 주제들
알고리즘 사이트에 가보면 문제를 선택할때 주제별로 필터링을 할 수 있다. 필기 보다는 실습을 통해서 문제의 패턴을 익히는 것이 중요하다.
-
다이나믹 프로그래밍(동적 계획법)
-
탐욕법
-
유클리드 호제법(최대 공약수, 최소 공배수)
-
비트 연산
-
진수 변환
....
HackerRank 사이트 우측 하단에서 주제 별로 문제를 선택 할수 있다. - HackerRank 사이트 ,algopost - 알고리즘 대회에 필요한 수학
기본 알고리즘 학습
기초 적인 원리를 이해 했다면, 코드로 어떻게 풀어 가는지 예제 알고리즘을 공부 해야하는데, 자기 자신보다 코드를 더 잘쓰는 사람의 코드를 보고 분석하고 내껏으로 흡수 하는 것도 최고의 방법 이라고 생각합니다.
코드로 작성하는 예시로는 geeksforgeeks에 예시가 상세하게 적혀 있습니다.
그 이후에는 직접 작성해 보는 것도 좋을 것 같습니다.
쉬운 문제 풀기
국내 사이트
해외 사이트
-