그리디
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.
- ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준 제시해주면 그리디
- 정렬 알고리즘과 자주 짝을 이뤄 출시
구현
- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제들
- 변수의 표현 범위를 고려해야 함.
완전탐색
- 모든 경우의 수를 다 계산
시뮬레이션
- 문제에서 제시한 알고리즘을 한 단계씩 차례로 수행
탐색 알고리즘
DFS
- 깊이 우선 탐색. 스택을 이용.
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
3. 2번 과정을 더 이상 수행할 수 없을 때 까지 반복
BFS
- 너비 우선 탐색. 가까운 노드부터 탐색. 큐 이용
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번 과정을 더 이상 수행할 수 없을 때 까지 반복
정렬
선택 정렬
- 매 번 가장 작은 것을 선택.
- 시간 복잡도 : O(N^2)
- 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복
삽입 정렬
- 특정한 데이터를 적정한 위치에 삽입
- 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정.
- 시간 복잡도 : O(N^2)
- 두 번째 데이터부터 시작함(첫 번째 데이터는 그 자체로 정렬되어 있다고 판단).
퀵 정렬
- 기준 데이터(피벗)를 설정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식.
- 시간 복잡도 : 평균 O(NlogN)
1. 피벗을 설정한 후에 왼쪽에서 피벗보다 큰 데이터를 찾고, 오른쪽에서 피벗보다 작은 데이터를 찾는다.
2. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
계수 정렬
- 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음.
- 시간 복잡도 : O(N+K)
1. 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성해 0으로 초기화 한다.
2. 그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. - 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘.
- 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능.
- 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1000000을 넘지 않을 때 효과적으로 사용.
이진 탐색(*암기)
- 숫자 범위가 엄청 크면 이진 탐색
- 원하는 조건을 만족하는 가장 큰 값을 찾는 문제
- 재귀 or 반복문
순차탐색
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법. 보통정렬되지 않은 데이터 찾아야 할 때 사용
이진탐색
- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것. 정렬된 데이터에만 사용 가능
DP
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
재귀함수 : top-down
반복문 : bot tom-up
재귀함수 보다 반복문이 더 성능이 좋다.
최단경로(*암기)
다익스트라 알고리즘
- 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로 구하는 알고리즘
=> 그리디 알고리즘으로 분류
플로이드 워셜 알고리즘
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘
=> DP - 문제의 범위가 작은 경우 구현이 간단한 다익스트라 알고리즘보다 플로이드 워셜 알고리즘을 이용하는 것이 유리하다.
그래프(*암기)
- 연결되어 있다. -> 그래프 알고리즘
프로그래밍에서 그래프는 크게 2가지 방식으로 표현
1. 인접행렬 : 2차원 배열로 그래프 연결 관계 표현 ex)다익스트라
2. 인접리스트 : 리스트로 그래프 연결 관계 표현 ex)플로이드 워셜
서로소 집합 자료구조
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조. union-find자료구조라고 불리기도 함.
find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
union : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
-
트리 자료구조를 이용해 집합을 표현하는 서로소 집합 계산 알고리즘
1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
- A와 B의 루트 노드를 각각 찾는다.
- A의 루트 노드를 B의 부모 노드로 설정한다.(B의 루트 노드가 A의 루트 노드를 가리키도록 한다.)(더 번호가 작은 원소가 부모가 되도록 구현하는 것이 일반적)
2. 모든 union 연산을 처리할 때 까지 1번 과정을 반복한다.
=> 처음에 모든 원소가 자기 자신을 부모로 가지도록 설정해야 한다. -
서로소 집합을 활용한 사이클 판별
1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
- 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
- 루트 노드가 서로 같다면 사이클이 발생한 것이다.
2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.
크루스칼 알고리즘
- 대표적인 최소 신장 트리 알고리즘.
- 신장 트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
- 최소 신장 트리 알고리즘 : 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘.
- 시간 복잡도 : 간선의 개수가 E개일 때, O(ElogE)
1. 간선 데이터를 비용에 따라 오름차순으로 정리한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대하여 2번의 과정을 반복한다. - 가장 거리가 짧은 간선부터 차례대로 집합에 추가(사이클 발생시키는 간선 제외)
위상 정렬
- 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것.
- 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용.
- 시간 복잡도 : O(V+E)
1. 진입차수(특정한 노드로 들어오는 간선의 개수)가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
기타
vector
- vector 입력시 크기 지정 X
vector<int> v;
for(int i=0;i<n;i++) {
int a;
cin >> a;
v.push_back(a);
}- vector 입력시 크기 지정 O
int n;
cin >> n;
vector<int> v(n);
for(int i=0;i<n;i++) {
cin >> v[i];
}출처 : 이것이 코딩 테스트다 - 나동빈
log.info("공부 기록 블로9")