[알고리즘] 알고리즘이란 ? / 알고리즘의 종류

알고리즘이란?

; 제한된 공간과 시간 안에서 데이터를 어떻게 처리할 것인지를 정해놓은 로직

 

알고리즘 공부 방향

- 어떤 자료구조를 이용하여 알고리즘을 작성하는 것이 좋을 지

- 작은 공간 + 빠른 시간안에 효율적으로 처리하는 것이 목표

- 인풋 사이즈 커질수록 Big O가 어떻게 변화하는지

- 자동완성, 복붙 사용 최소화할 것

- 충분한 고민 & 문제에 대한 이해/풀이 아이디어, 어려웠던 점 및 해결책 생각할 것

 

알고리즘의 종류

재귀

• 피보나치 수열

int Fibo(int n){
	if(n==1 or n==2) return 1;
	else return Fibo(n-1)+Fibo(n-2);
}

• 최대공약수(GCD)

int gcd(int a,int b){
	if(a%b==0) return b;
	return gcd(b,a%b);
}

• 하노이의 탑

void hanoi(int n,int a,int b,int c){ // a에서 b를 거쳐 c로 이동 
	if(n==1) cout<<a<<" "<<c<<endl;
	else{
		hanoi(n-1,a,c,b);
		cout<<a<<" "<<c<<endl;
		hanoi(n-1,b,a,c);
	}
}

hanoi(n)=2**n-1

 

탐색

• 선형 탐색 ; 맨 앞이나, 맨 뒤부터 순서대로 하나하나 찾아보는 알고리즘

• 이진 탐색 ; 중간지점 선택 -> 중간지점을 기준으로 왼쪽 혹은 오른쪽만 남김 -> 남은 부분으로 반복

• 해시 탐색 ; 값과 index를 미리 연결해 둠으로써 짧은 시간에 탐색할 수 있는 알고리즘

# 해시 함수 ; 어떤 값이 주어졌을 때, 그 값을 대표하는 값을 계산하는 함수

# 해시값 ; 해시 함수의 계산으로 나온 값

 

정렬

https://peter-coding.tistory.com/58

[알고리즘] 정렬(삽입 정렬, 버블 정렬, 선택 정렬, 퀵 정렬)

 

완전 탐색

; 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법

• 브루트 포스 ; 가능한 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만 가져옴
• 비트 마스크 ; 비트를 활용한 테크닉

- and(%), or(|), xor(^), not(~)

- 시프트 연산(>>,<<) ; 왼쪽/오른쪽으로 비트를 옮김 ex) 00001010<<2=101000 

-  BIT|1<<n ; BIT의 n번째 비트를 1로 변경 / BIT&~1<<n ; BIT의 n번째 비트를 0으로 변경

• 백트래킹 ; 모든 경우의 수를 전부 고려하는 알고리즘

DFS와 BFS ; https://peter-coding.tistory.com/20?category=1278345

백트래킹 알고리즘

• 순열 ; 서로 다른 n개 중 r개를 골라 순서를 고려해 나열한 경우의 수

 

분할 정복

; 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘

 

동적 계획법(DP ; Dynamic Programming)

; 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용

ex) 피보나치 수열

 

그리디

; 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

https://peter-coding.tistory.com/17?category=1278345 

그리디 알고리즘

 

[비선형 구조]

트리

• 이진 검색 트리 ; 루트 노드의 키와 찾고자 하는 값을 비교 -> 찾고자 하는 값이 작다면 왼쪽 서브 트리 탐색 / 크다면 오른쪽 서브 트리 탐색 .. 찾을 때까지 반복

https://peter-coding.tistory.com/9?category=1279953 

트리(Tree)

 

그래프

• 위상 정렬 ; 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것

https://peter-coding.tistory.com/63

[알고리즘] 그래프

 

최단 경로

• Floyd-Warshall
• 다익스트라(Dijkstra)
• Beliman-Ford

 

그 외

• 비트 연산
• 진수 변환
• 재귀(Recursion)
• 유클리드 호제법(최대공약수, 최소공배수)
• 투포인터(슬라이딩 윈도우)
• 조합, 순열
• 파라메트릭 서치
• 최장 증가 수열(LIS)
• 최소 공통 조상(LCA)
• Matching Parenthesis problem
• Variables / Pointers manipulation
• reverse linked list(duplicates, removing duplicates)
• Custom data structures(Object oriented programming)