시간복잡도

시간 복잡도

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

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) 의 시간 복잡도를 가진다.

시간 복잡도설명

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

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

 

자료구조

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

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

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

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

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

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

자세한 내용은 출처 - LibreWiki

 

정렬

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

 

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

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

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