CheerUp_Cheers
알고리즘 심화 본문
- 브루트포스
- 그리디
- 자료구조 - 선형(배열,연결리스트,스택,큐,덱)
- 자료구조 - 비선형(그래프,트리)
- 자료구조 - 힙
- Collection - Map, Set , List
- 정렬
- DP - knapsack, LCS, 부분집합의 합
- 그래프 - BFS, DFS(백트래킹)
- Disjoint - makeSet, FindSet, UnionSet
- 최소 신장 트리(MST) - Prim, Kruskal
- 최소거리 갱신 - 다익스트라, 벨만포드, 플로이드 와샬
- 문자열 알고리즘 - KMP, 라빈카프, 보이어 무어
- 위상 정렬
- 세그먼트 트리
- 이분 탐색
- 비트 마스크
-
브루트포스(전체탐색)
정의 : 매우 단순무식한 알고리즘, 가능한 모든 경우에 대해 모두 직접 해보는 방법.
#장점
- 만들기가 아주 쉬운편.(다해보면되니까)
- 알고리즘을 만드는 출발점.
#단점
- 숫자(자릿수 등)이 커지면서 직접 해보야할 경우의 수가 기하급수적으로 커짐.
- 시간 측면에서 매우 비효율적
-
그리디(탐욕법, 탐욕 알고리즘)
정의 : 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식.
#조건
- 탐욕스러운 선택 조건 : 앞의 선택이 이후의 선택에 영향을 주지 않는 조건.
- 최적 부분 구조 조건 : 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결방법이다.
#장점
- 계산속도가 빠르다.
#단점
- 순간마다 매번 최선의 결정을 하게 하더라도, 언제나 최적이 아니다.
-
자료구조 - 선형(배열,연결리스트,스택,큐)
선형자료구조 : 자료를 구성하는 데이터를 순차적으로 나열시킨 형태를 의미.
ex)배열, 연결리스트, 스택, 큐
비선형 자료구조 : 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것을 의미.
ex) 트리, 그래프
[1] 배열(순차리스트)
정의 : 같은 타입의 변수들로 이루어진 유한 집합으로 정의됩니다.
#장점
- 쉽게 구현이 가능
- 배열은 내부 인덱스를 가지고 데이터 접근, 인덱스를 가지고 직접 접근 빠름. (무작위 접근가능, 검색 효율)
- 항상 인덱스 0부터 시작 하니, 저장된 데이터의 수만 따로 관리하면 마지막 데이터 찾기 쉬움.
- 참조를 위한 추가적인 메모리 할당 필요없음.
#단점
- 지정한 크기를 바꿀수 없음
-> 너무 큰 크기로 생성했을 경우, 불필요한 메모리 낭비.
- 데이터 삽입하거나 삭제했을 경우 뒤의 데이터들을 모두 한칸씩 밀거나 당겨줘야함.
-> 평균적 데이터수/2 만큼의 연산.
- 메모리 의 재사용이 불가
-> 초기 사이즈만큼 메모리를 할당받아 사용하기에 데이터를 유무에 상관없이 메모리 점유.
-> 배열자체를 메모리에서 제거해야함.
[2] 연결리스트
정의 : 배열의 단점을 해결하기 위해 준비된 객체
이전 데이터나 다음 데이터에 대한 참조만 가지고 있음
#장점
- 비순차적 접근에 유리
- 크기의 동적 변경(배열 대신 쓰는 이유)
- 추가, 삭제 효율적(인덱스 변경없이 참조만 변경)
- 메모리의 재사용이 가능함
-> 자료 삭제시 해당 노드의 참조가 사라짐으로 나중에 가비지 컬렉터가 메모리 반환.
#단점
- 접근이 느리다( 순차적으로 검색해야함).
- 다음 링크 공간이 필요하다( 추가 메모리 할당).
#종류
단순 연결리스트 : 각 자료 요소들이 다음 데이터에 대한 참조를 가지고 있음.
이중 연결리스트 : 양방향(메모리 공간 소모), 이전데이터와 다음데이터 참조를 모두 추가.
원형 이중 연결 리스트 : 단순 연결리스트의 마지막 자료에대한 참조를 추가
[3] 스택
정의 : 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO형식의 구조.
#특징
LIFO(후입선출) : 나중에 들어온 애를 먼저 뽑음.
삽입(PUSH), 삭제(POP), 반환(peek), 비어있는 여부(isEmpty())
Top이라는 index가 필요 -> 초기값 -1(공백)
스택의 크기를 동적으로 하는 것이 효율적.
#사용 사례
- 재귀
- 실행 취소
- 웹 브라우저 방문기록
- 역순 문자열 만들기
- 수식의 괄호 검사(연산자 우선순위)
- 후위 표기법
[4] 큐
정의 : 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 넣은 데이터가 먼저 나오는 FIFO구조 형식.
#특징
추가(add), 제거(remove), 반환(peek), 삭제와 반환(poll), 비어있는지 여부(isEmpty())
초기 공백은 front = rear = 0임.
연결리스트와, 배열로 구현가능(삽입 | 삭제 시 원소 재배치)
#사용사례
- BFS
- 캐시 구현
- 프로세스 관리
#우선순위 큐
요소에 NULL을 허용하지 않음(큐는 허용)
-
자료구조 - 비선형(그래프,트리), 셋, 힙
[1] 그래프 vs 트리
[2] 그래프
#그래프의 구현 2가지
1) 인접리스트
정의 : 모든 정점을 인접 리스트에 저장, 즉 각각 정점에 인접한 정점들을 리스트에 표시.
-> ArrayList나 LinkedList를 이용해서 인접리스트 표현.
2) 인접 행렬
정의 : 인접 행렬은 N*N의 행렬로써, arr[i][j]가 true면 간선(i->j)이 있다는 뜻.
-> 배열에 전부다 저장.
#둘의 장단점
1-1) 인접 리스트 장점
그래프내에서 적은 숫자의 간선만을 가지는 희소 그래프인 경우 사용
- 어떤 노드에 인접한 노드를 쉽게 찾음
- 그래프트 존재하는 모든 간선의 수는 O(N+E)안에 알 수 있다.
1-2) 인접 리스트 단점
- 간선이 너무 많으면 시간이 많이 필요.
2-1) 인접 행렬 장점
그래프에 간선이 많이 존재하는 밀집 그래프 인 경우 사용.
- 두 정점을 연결하는 간선의 존재여부(M[i][j])를 O(1)안에 즉시 알 수 있다.
- 정점의 차수는 O(N)안에 알 수 있음
2-2) 인접 행렬 단점
- 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회 해야 함.
- 그래프에 존재하는 모든 간선의 수는 O(N^2)안에 알 수 있다(전체 조사)
- 0으로 비워두면 메모리 낭비.
[3] 트리
#종류
- 이진트리
- 포화 이진트리 : 모든 레벨에 노드가 포화상태로 채어져 있음.
- 완전 이진트리 : 빈자리 없는 이진트리.
- 편향 이진트리 : 최소의 개수의 노드를 가지며, 한쪽 방향의 자식노드만 가짐.
메모리를 많이 소모.
-
자료구조 - 힙
정의 : 우선순위 큐를 위하여 만들어진 자료구조. (가장 효율적임)
#특징
완전 이진트리의 일종.
힙은 일종의 반정렬 상태(느슨한 정렬)
-> 큰값이 상위레벨에 있고, 작은 값이 하위 레벨에 있다 정도.
힙트리는 중복된 값을 허용(이진 탐색트리는 허용안함)
#종류
최대 힙 : key(부모노드) >= key(자식노드)
최소 힙 : key(부모노드) <= key(자식노드)
#구현
힙을 저장하는 표준적인 자료구조는 배열.
구현을 쉽게하기 위해 첫번쨰 인덱스 0 사용 안함.
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음.
! 힙에서의 부모와 자식 노드의 관계
- 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
- 오른쪽 자식의 인덱스 = (부모의 인덱스)*2 + 1
- 부모의 인덱스 = (자식의 인덱스)/2
-
Collection - List, Set, Map
List : 순서 O(인덱스 O), 데이터 중복 O
Set : 순서 X(인덱스 X), 데이터 중복 X
Map : Key & Value, Key 중복 X, Value 중복 O
[1] List
정의 : 데이터를 순서에 맞게 일렬로 구성.
#ArrayList vs LinkedList
1)ArrayList
!장점
- 검색이 빠르다(인덱스)
- 순차적으로 객체를 추가 및 삭제가 빠르다.
2)LinkedList
!장점
- 배열의 중간 위치에 추가,제거에 빠름(Array크기와 인덱스 조정이 필요없기 떄문)
!단점
- 앞뒤로 두개의 참조를 저장하기 떄문에 ArrayList보다 많은 메모리 차지.
-
정렬
참고 :
알고리즘 정렬기본
CheerUp_Cheers 알고리즘 정렬기본 본문 CS 알고리즘 정렬기본 meorimori 2020. 5. 15. 01:26 Prev 1 2 3 4 5 ··· 43 Next
meorimori.tistory.com
-
DP - Knapsack, LCS, 부분집합의 합
정의 : 전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결.
#특징
모든 작은 문제들을 한번만 풀어야함
-> 정답을 구한 작은 문제를 어딘가에 메모(메모이제이션)
큰 문제를 풀어갈 때, 메모한 작은 문제의 결과값을 이용.
#조건
작은 문제가 반복이 일어남.
같은 문제는 구할 때마다 정답이 같다(메모이제이션 활용)
#메모이제이션
한번 계싼한 문제는 다시 계산하지 않고 저장해두고 활용하는 방식.
#방법
- Bottom-up
작은 문제부터 차근차근 구해나가는 방법
해결용이, 가독성 떨어짐
- Top-down
재귀함수로 구현하는 경우가 대부분 탑다운, 큰문제를 풀때 작은 문제가 풀리지 않았다면 그제서야 작은문제 해결
가독성 좋음, 코드작성 힘듬.
#사용사례
- 최장 공통 부분 수열(LCS)
- 부분집합의 합
- 배낭 문제
- 피보나치
-
그래프 - BFS, DFS(백트래킹)
[1] BFS
정의 : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.
#특징
사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때.
직관적이지가 않음 : 거리에 따라 단계별적 탐색
어떤 노드를 방문햇는지 여부가 반드시 검사(없으면 무한루프)
방문한 노드를 차례로 꺼내는 큐 (Queue)를 사용.
#시간복잡도
인접리스트 표현된 그래프 : O(V+E) - 한 행에서의 열을 찾으면 되기 떄문.(희소그래프가 유리 = 적은간선)
인접행렬 : O(V^2) - 모든 행에서 열을 찾아야 하니까.
[2] DFS
정의 : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방법.
#특징
사용하는 이유 : 모든 노드를 방문하고자 할떄 이방법을 사용.
자기 자신을 호출하는 순환 알고리즘의 형태.
전위 순회를 포함한 다른형태의 트리순회는 모두 DFS의 한 종류.
어떤 노드를 방문했는지 여부가 반드시 검사(없으면 무한루프)
DFS는 BFS보다는 간단하지만, 느림.
#구현방법
- 순환 호출 이용(재귀)
- 명시적 스택을 사용
명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였따가 다시 꺼내어 작업.
#시간복잡도
- 인접리스트 표현된 그래프
O(V+E) - 모든 정점을 확인하는 V, 각 정점에서 연결된 간선을 확인하는 E
+ (희소그래프가 유리 = 적은간선)
- 인접행렬
O(V^2) - 한번의 DFS임, n개 찾자하면 ->총 시간복잡도는 (N^3)
-
Disjoint - makeSet, FindSet, UnionSet
정의 : 교집합이 없는(서로 중복이 없는) 집합들.
#언제쓰냐
그룹을 합치는 문제.
같은 그룹인지 묻는 문제
몇개의 그룹인지 세는 문제.
#구현방식
makeSet, FindSet, UnionSet
연결리스트로 구현시 : 원소들을 합칠 떄 링크를 바꾸는 과정은 과소비.
트리로 구현시 : 부모만 가르킴 ( 자기 자신이면 그녀석이 대표자임)
#문제 및 개선
합치는 행위를 어디에 기준을 두고 붙일 것인가?
낮은 rank(깊이)의 집합을 높은 집합에 합치자.
-
최소 신장 트리(MST) - Prim, Kruskal
정의 : 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
간선이 많으면 프림 알고리즘, 간선이 적으면 크루스칼. (간조쿠 간많프)
#특징
사이클이 없음.
정점은 N, 간선은 N-1
#종류
[1] Prim(프림)
!과정
1) 임의 정점을 하나 선택해서 시작(어떤것이든 상관없음)
2) 선택한 정점과 인접하는 정점중의 최소 비용의 간선을 선택
3) 모든정점이 선택될 떄까지 반복.
[2] Kruskal(크루스칼)
!특징
인접행렬을 저장할 필요없이, 간선만있으면 됨(간선이적어야..)
서로서 집합을 통하여 집합을 봄.
같은 대표자면 싸이클.
!과정
1) 최초, 모든 간선을 가중치에 따라 오름차순 정렬
2) 가중치가 낮은 간선부터 선택하면서 트리를 증가
-> 사이클 존재시 다음으로 가중치 낮은 간선 선택
3) n-1개의 간선이 선택될 떄까지 앞과정 반복.
#프림 vs 크루스칼
[1] Prim : 가중치를 정점에 매겨놓고, 정점을 선택해 나감
O[V^2] : 순차검색을 사용할 경우
O[E Log V] : 최소힙(우선순위 큐)을 사용할 경우
[2] KRUSKAL : 가중치를 간선에 매겨놓고, 간선을 선택해 나감.
O[E log E] or O[E log V] : DisjoinSet, 퀵또는 병합 정렬 사용시
O[E * a ] : DisjointSet, 카운팅 정렬 사용시
-
최소거리 갱신 - 다익스트라, 벨만포드, 플로이드 와샬
정의 : 특정 정점에서 시작하는 각 정점까지의 거리를 구하는 알고리즘
다익스트라 : 특정 정점에서 각정점 까지 | 시간 복잡도 O(V^2), 우선순위큐 사용시 O(ELogV)
벨만포드 : 음의 가중치가 주어진 경우 | 시간 복잡도 O(VE), 초기화가 V, 순환구조 검사 E
플로이드 와샬 : 모든 정점에서의 최소거리를 구할 경우 | O(V^3)
[1] 다익스트라(Dijkstra)
#과정
0) 시작 정점은 0으로 할당.
1) 모든 정점들을 최소 우선 순위 큐에 삽입
2) 최단 경로 가중치 값이 가장 적은 정점을 선택하여 인접 간선들에 대해 Relax
3) (이전 정점까지의 최단경로 추정값 + 가중치값 < 원래 가중치) 일 경우만 업데이트.
4) 큐가 빌때까지 반복.
[2] 벨만포드
#특징
음수 가중치가 존재하는 모든 정점에서의 최단 경로를 알 수 있음.
시간복잡도 O(VE)
-> 정점이 V, 간선이 E라고 했을 때 V-1번 간선들을 모두 돌아봄.
음의 가중치를 가지기 때문에, 음의 사이클을 조심해야함.
->V번째 간선들을 돌아봤을 때, 가중치가 수정이되면 음의 싸이클이 존재.
[3] 플로이드 와샬
#특징
DP를 통해서 최소거리를 갱신.
모든 정점에서의 최단 경로를 알 수 있음.
시간복잡도 O(N^3)
->for문이 3개가 돌아(k,i,j)
-
문자열 알고리즘 - KMP, 라빈카프, 보이어 무어
[1] KMP
#시간복잡도
기존의 완전 탐색 - O(MN), 10000길이의 문자열이면 1억..
시간 복잡도 O(N+M) // 최초로 선형시간.. N : 문자열길이, M : 전체 길이
2번째 부터 다시 시작하면됨, 뒤쪽은 모르니까.
뒤쪽 부터 접두사와 접미사가 같으면서 길이가 긴것을 찾아라!
-> ABA(접미사, 2 3 4) = ABA(접두사, 0 1 2)
1)파이를 만들어야 함.
2)본문자열도 파이만드는것처럼 하면됨.
[2]라빈 카프
문자열 검색을 위해 해시값 함수를 이용
-> 비교의 부담을 줄이자.
가장 안좋은 케이스를 주면 O(MN), 평균적으로 선형
[3]보이어 무어
뒤에서 부터 시작하는 알고리즘.
시간 복잡도 O(MN)
-
위상 정렬
정의 : 어떤일을 하는 순서를 찾는 알고리즘
즉, 방향 그래프의 존재하는 각 정점들의 선행 순서를 위배하지 않고 모든 정점을 나열하는 것.
#특징
하나의 방향 그래프에는 여러 위상 정렬이 가능하다.
위상 정렬 과정에서 선택되는 순서를 위상순서(토포로지컬 오더)라 한다.
그래프에 남아있는 정점중 진입 차수가 0인 정점이 없으면, 알고리즘은 종료되고 이러한 그래프는 실행불가능 문제.
#과정
1) 진입 차수가 0인 정점선택
여러개 있을 경우 어떤 정점을 선택해도 무방.
선택한 정점을 큐에 삽입
2) 선택된 정점과 여기에 부속된 간선을 삭제
선택된 정점을 큐에서 삭제
선택된 정점에 부속된 모든 간선에대해 간선의 수를 감소
3) 모두 삭제될떄까지 반복, 종료.
#사용사례
- 선수 과목
- 작업이 완료되야 끝나느 프로젝트
-
세그먼트 트리
정의 : 배열에 부분 합을 구할 때 사용하는 개념입니다. 이 때 문제는 배열의 값이 지속적으로 바뀔 수 있기 때문에 매 순간 배열의 부분 길이 만큼, 즉 O(N) 만큼의 시간이 걸리기 때문에 이를 트리로 구현하여 O(logN) 의 시간으로 해결하는 방법입니다.시간 복잡도
- 자료 저장: O(n log n)
- 특정 구간 최적해 검색: O(log n + k)
#특징
- 부모노드의 값은 양 쪽 자식 노드 값(왼쪽= idx*2, 오른쪽 idx*2+1)의 합
- 배열의 요소들은 리프 노드에 위치
- 기존 데이터 배열의 크기를 N 이라 하면, 리프 노드의 개수가 N 이 됨.
트리의 높이 H 는 [ logN ] 이 되고, 배열의 크기는 2^(H+1) 이 됩니다.
- Start랑 End가 같으면 리프 노드.
#언제사용?
구간에 대한 정보를 저장함.
특정 구간의 최적화된 답을 구하는 문제에 사용.
부분 구간의 최적 답들 중에서 최적 답을 구할 수 있음.
#시간 복잡도
자료 저장: O(n log n)
특정 구간 최적해 검색: O(log n + k)
#LAZY PROPAGATION
- 이건 자료를 업데이트할 때 최악의 경우 O(N log N) 복잡도가 될 수 있는데, 이를 방지하고 시간 복잡도를 O(log N) 으로 고정시키기 위한 알고리즘이다.
- UPDATE 를 할 때, 당장 필요한 변경만 진행하고 자식 노드에 대해서는 다음에 해당 노드를 재탐색시 변경하는 전략임.
-
이분 탐색
- 정의
탐색 범위를 두부분으로 분할하면서 찾는 방식
- 순서
1) 정렬
2) left와 right로 mid값 설정
3) mid와 내가 구하고자하는 값 비교
4) 구할값이 mid보다 크면 left = mid +1, 반대면 right = mid -1
5) left > right가 될떄까지 비교
-
비트 마스크
- 사용이유
작은 메모리와 빠른 수행시간으로 해결 가능
코드 간결.
- 활용
[1,2,3,4,5]라는 집합에서 임의로 몇개를 뽑는 경우의 수(부분 집합)
비트 마스킹 시, 각 요소를 인덱스처럼 표현하여 효율적인 접근 가능.
ex) [1,2,3,4,5] -> 11111, [2] -> 00010
- 연산
1) 삽입 : OR 연산
2) 삭제 : AND와 NOT
3) 조회 : AND
