[Algorithm] 알고리즘 공부 시작하기

 

 

알고리즘 공부는 따로 해본 적이 없지만, 프로그래밍의 기초라는 사실은 이미 익히 알고 있다.

하나의 소스를 짜도 논리적인 소스와 아닌 소스는 차이가 난다.

(초초초보인 내가 봐도 대충 느낄 수 있음)

사실 이제껏 파이썬 공부를 한 이유는 파이썬으로 알고리즘+자료구조 공부를 하기 위해서이다.

 

그래서 시작합니다.

 

(출처는 거의 나무위키, 리브레위키)

알고리즘(Algorithm)

 

1. 알고리즘 개요

알고리즘이라는 용어는 문제를 해결하기 위한 절차나 방법을 의미하는 단어로 넒은 범위에서 사용된다.

조금 더 정확한 의미를 따져보자면 알고리즘은 어떠한 행동을 하기 위해서 만들어진 명령어들의 유한 집합(finite set)이다.

컴퓨터 프로그램은 정교한 알고리즘들의 집합이라고 간주할 수 있다. 수학이나 컴퓨터 과학에서 말하는 알고리즘은, 보통 반복되는 문제를 풀기 위한 작은 프로시저(진행절차)를 의미한다. 컴퓨터 시대 이후로는 알고리즘이라고 하면 컴퓨터를 통해 실행되는 것이라고 여겨지는 경향이 있으나, 사실 알고리즘 자체는 컴퓨터가 등장하기 이전부터도 존재했다. 즉, 사람이 수동으로 종이를 사용해 일정한 절차로 문제를 풀더라도 알고리즘에 해당한다. 다만, 컴퓨터의 등장과 함께 알고리즘 역시 급속도로 발전하게 된 것은 사실이다.

 

즉, 소스를 짜고 프로그래밍으로 결과를 구현하는 것을 건축에 비유 한다면

알고리즘을 배운다는 것은 건축 설계하는 법을 배우는 것이고, 프로그래밍을 배운다는 것은 건물 짓는 법을 배우는 것이다.

 

다만, 건물을 짓는데 다양한 방법이 동원되는 것처럼 알고리즘도 다양하게 적용될 수 있다. 결과가 동일하더라도 사용하는 알고리즘에 따라 프로그램의 속도나 처리방식 등이 크게 차이나는 경우도 있다.

 

살 만한 책:

https://blog.naver.com/jhc9639/221564114901: 알고리즘 트레이닝- 프로그래밍대회 입문가이드를 읽다.

- 언어가 C++로 되어있다는 것이 ㅠ-ㅠ맘에 걸림

https://blog.naver.com/jingug1004/221829284871: *어려운 알고리즘을 쉽게 익히고 싶다면 모두의 알고리즘 with 파이썬 

- 파이썬을 배우기 시작했으니, 이 분 말처럼 손으로 쳐가면서 공부를 제대로 해보고 싶다고 생각함!

 

2. 시간복잡도

자주 등장하는 알고리즘의 시간 복잡도는 아래와 같다.

위의 알고리즘이 가장 시간 복잡도가 낮은, 즉 가장 빠른 알고리즘이라고 부르고,

아래의 알고리즘이 가장 시간 복잡도가 높은, 즉 가장 느린 알고리즘이라 부른다.

 

Big-O 표기법(Big O notation)

예를 들어 입력 자료의 크기 n에 대하여 O(n)의 시간복잡도를 가진 알고리즘은 대략 크기 n에 비례하는 수의 연산을 수행한다고 보면 된다.

시간	복잡도설명
O(1)	상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다.
O(log n)	로그 형태
O(n)	선형
O(n log n)	선형로그 형태
O(n² ),O(n³ ),⋯	다차 형태
O(2ⁿ )	지수 형태
O(n!)	팩토리얼 형태

 

3. 알고리즘의 조건

알고리즘은 이하의 요건을 만족해야만 한다.
입력 - 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재한다.
출력 - 알고리즘은 최소 1개 이상의 결과를 가진다.
명확성 - 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.
유한성 - 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다.

   알고리즘의 한 단계 이후 m의 값은 n 보다 작으며, m!=0이면 n의 값은 다음 번 단계에서 줄어든다.
효과성 - 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.

 

4. 자료구조

하나하나 세부적으로는 계속해서 공부 할 것임!

4.1 선형 자료구조
   4.1.1 랜덤 접근 가능
     4.1.1.1 배열
     4.1.1.2 해시
   4.1.2 랜덤 접근 불가능
      4.1.2.1 스택
      4.1.2.2 큐
      4.1.2.3 데크
      4.1.2.4 링크드 리스트
   4.1.3 선형구조 자료 탐색법
      4.1.3.1 순차 탐색
      4.1.3.2 이분 탐색
4.2 비선형 자료구조
   4.2.1 그래프
      4.2.1.1 그래프 관련 용어
      4.2.1.2 그래프의 종류
      4.2.1.3 그래프 순회 알고리즘
         4.2.1.3.1 깊이 우선 탐색
         4.2.1.3.2 너비 우선 탐색
   4.2.2 트리
      4.2.2.1 트리 관련 용어
      4.2.2.2 트리의 종류
      4.2.2.3 트리 순회 알고리즘
         4.2.2.3.1 전위 순회
         4.2.2.3.2 중위 순회
         4.2.2.3.3 후위 순회
         4.2.2.3.4 레벨 순서 순회
      4.2.2.4 이진 검색 트리
         4.2.2.4.1 이진 검색
4.3 문자열

 

5 기초 정렬 알고리즘
   5.1 거품(Bubble) 정렬
   5.2 선택(Selection) 정렬
   5.3 삽입(Insertion) 정렬

 

 

 

▶ 코딩테스트 연습 싸이트:

https://level.goorm.io/

구름LEVEL

https://programmers.co.kr/

프로그래머스