[ 알고리즘 ] 알고리즘에 필요한 기본 개념.
∇ 알고리즘에 필요한 기본 개념들.
목 차
1. 시간 복잡도
2. 자료 구조
3. 정렬
1. 시간 복잡도
- 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 말합니다.
- 프로그램을 작성할 때에 입력량의 크기에 따라서, 프로그램이 계산하는 횟수가 크게 달라집니다.
- 입력된 잘의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있는데
이것을 알고리즘의 시간 복잡도라고 합니다.
∂ 메모리 공간 차지량을 계산하는 공간 복잡도라는 개념도 있지만,
저장 기술의 발달로 인해서 현재는 "시간 복잡도"를 우선 고려합니다.
- 시간 복잡도를 나타낼 경우에는 "BIG O" 표기법을 활용합니다.
// 방법 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부터 N 까지의 합을 구한다고 할 때 위의 코드처럼 두가지 방법이 있습니다.
방법 1에서는 for문을 이용해 n번의 연산을 하기 때문에 O(n)의 시간복잡도를 가지고,
방법 2에서는 n의 크기와 상관 없이 1번의 연산 과정을 거치기 때문에 O(1)의 시간 복잡도를 가집니다.
- 맨 위에서부터 시간 복잡도가 낮고 빠르고,
아래로 갈 수록 시간 복잡도가 높고 느려집니다.
- 제한된시간(빠른 시간)안에 올바르게 output을 출력하려면 시간 복잡도를 낮춰야 합니다.
2. 자료 구조.
자료 구조란, "데이터 사이의 관계를 반영한 저장 구조 및 그 조작 방법"을 의미합니다.
프로덕트를 실행하면 CPU에서 메모리로 데이터를 이동시켜서 처리하는데,
이 때 메모리를 효율적으로 사용하기 위해 "데이터에 맞는 특성의 자료구조를 사용하는 것"이 중요합니다!
√ 자료구조의 종류
3. 정렬 알고리
정렬알고리즘(sorting algorithm) 정리
1.버블정렬(Bubble sort)
medium.com
√ 버블 정렬 : 가장 쉽지만, 시간 복잡도가 높아 효율적이지 않음.
√ 선택 정렬 : 버블 정렬과 알고리즘이 유사합니다. 가장 큰 수를 찾아 배열의 마지막 위치와 교환합니다
√ 삽입 정렬 : 인덱스를 설정하여, 현재 위치의 값을 아래쪽으로 순회하며 알맞은 곳에 넣어줍니다
√ 병합 정렬 : 정렬한 리스트를 반으로 쪼개며 좌우 리스트를 분할해 정렬 후 병합합니다.
가장 많이 쓰이는 정렬 중 하나입니다.
√ 힙 정렬 : 힙이라는 자료구조를 통해 내림차순으로 숫자를 넣은 후 , 역순으로 꺼내어 정렬합니다,
√ 퀵 정렬 : Pivot 기준으로 좌측과 우측으로 작은 값과 큰 값을 재배치하고 분할하여 정렬합니다.