[이코테] 개인적인 정리 글 (2주차)

지난 글에서 작성했지만 문제는 일단 안 풀리면 넘기고 진행했다.

처음에 계획을 잡았을 때는 페이지 수만 보고 괜찮을 것 같다고 생각했었고 지난주까지는 그래도 예제와 실전문제 조금이었는데 이번 분량은 문제가 엄청 많아서 힘들게 진행했다. 못 푼 문제가 푼 문제보다 압도적으로 많다.

다음엔 풀지 못한 문제들도 잘 풀 수 있도록 공부!!

---

◎ 순차탐색

- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

- 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용

- 시간 복잡도 : O(N)

 

◎ 이진탐색

- 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘

- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색

- 한번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다 : 시간복잡도는 O(logN)

- 구현 방법 : 재귀함수 이용 ,  반복문 이용

- 탐색 범위가 큰 경우 이진 탐색을 이용해 접근해야 하는 경우가 많다.

 

◎ 트리 자료구조

- 트리는 부모 노드와 자식 노드의 관계로 표현

- 트리의 최상단 노드를 루트 노드라고 한다.

- 트리의 최하단 노드를 단말 노드라고 한다.

- 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다.

- 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

 

◎ 이진 탐색 트리

- 이진 탐색이 동작할 수 있도록 고안된 자료구조

- 부모 노드보다 왼쪽 자식 노드가 작다.

- 부모 노드보다 오른쪽 자식 노드가 크다.

- 루트 노드부터 왼쪽 자식 노드 혹은 오른쪽 자식 노드로 이동하며 반복적으로 방문

 

◎ 파라메트릭 서치

- 최적화 문제를 결정문제('예', '아니오'로 답하는 문제)로 바꾸어 해결하는 기법

- 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 파라메트릭 서치를 사용

- 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결

- 파라메트릭 서치 유형은 이진 탐색을 재귀적으로 구현하지 않고 반복문을 이용해 구현하면 더 간결하게 풀 수 있다.

 

◎ 다이나믹 프로그래밍

- 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘

-  다음 조건을 만족할 때 사용

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

- 메모이제이션 : 다이나믹 프로그래밍 구현하는 방법 중 하나.

한번 구한 결과를 메모리 공간(리스트에 저장)에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

'캐싱'이라고도 한다.

- 분할 정복과의 차이는 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점.

- 재귀 함수를 이용하여 다이나믹 프로그래밍 작성 : 탑다운 방식(하향식)

- 반복문을 이용하여 다이나믹 프로그래밍 작성 : 보텀업 방식(상향식) - 다이나믹 프로그래밍의 전형적인 형태

- 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다.

- 가능하면 탑다운보다는 보텀업 방식을 권장. 재귀함수의 스택 크기가 한정되어 있을 수 있기 때문

 

◎ 최단 경로

- 가장 짧은 경로를 찾는 알고리즘

- 보통 그래프를 이용해 표현

- 최단 거리 알고리즘 : 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘

 

◎ 다익스트라 최단 경로 알고리즘

- 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

- '음의 간선'(0보다 작은 값을 가지는 간선)이 없을 때 정상적으로 동작

- 그리디 알고리즘의 한 유형

- 알고리즘의 원리

1. 출발 노드를 설정

2. 최단 거리 테이블(각 노드에 대한 현재까지의 최단거리 정보를 담고 있는 1차원 리스트)을 초기화

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신

5. 3번과 4번을 반복

- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원로를 순차탐색 -> 시간 복잡도 : O(V^2) (V는 노드의 개수)

- 힙 자료구조를 사용하면 선형적으로 탐색하는 경우보다 시간복잡도를 줄일 수 있다 -> 시간 복잡도 : O(ElogV)(E는 간선의 개수) : 가장 짧은 노드를 선택하는 과정을 우선순위 큐를 이용하는 방식으로 대체

	삽입시간	삭제시간
리스트	1	o(N)
힙	O(logN)	O(logN)

 

 

◎ 우선순위 큐

- 힙 자료구조를 통해 구현

- 우선순위가 가장 높은 데이터를 가장 먼저 삭제

- 대부분 프로그래밍 언어에서 라이브러리로 지원

- 대부분 프로그래밍 언어에서는 우선순위 큐 라이브러리에 데이터 묶음을 넣으면 첫번째 원소를 기준으로 우선순위를 설정

- 우선순위 큐를 구현할 때는 최소힙 또는 최대힙을 이용

- 최소힙을 이용하는 경우 값이 낮은 데이터가 먼저 삭제

- 최대힙을 이용하는 경우 값이 큰 데이터가 먼저 삭제

- C++에서는 최대힙, 자바와 파이썬은 최소힙을 이용하여 우선순위 큐 라이브러리가 구현되어 있다.

- 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선 방문하므로 최소 힙 구조를 기반으로 하는 우선순위 큐를 사용하면 적합하다.

- 최소힙을 최대힙처럼 사용하기 위해 일부러 우선순위에 해당하는 값에 음수 부호를 붙여서 넣었다가, 나중에 꺼낸 다음에 다시 음수 부호를 붙여 원래 값으로 돌리는 방법도 사용한다.

 

◎ 플로이드 워셜 알고리즘

- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘

- 시간복잡도 : O(N^3)

- 2차원 리스트에 최단 거리 정보를 저장

- 다이나믹 프로그래밍의 한 유형

 

◎ 서로소 집합 자료구조

- 서로소 집합 : 공통 원소가 없는 두 집합을 의미

- 서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

- union과 find 2개의 연산으로 조작

- union 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

- find 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

(find 연산은 경로 압축 기법(find 함수를 재귀적으로 호출한 뒤에 부모 테이블값을 갱신하는 기법)을 이용하여 최적화 가능)

- 트리 자료구조를 이용하여 집합을 표현

- 계산 과정

1. union 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인

     A와 B의 루트 노드 A', B'를 찾고 A'를 B'의 부모노드로 설정(B'가 A'를 가리키도록 한다)

2. 모든 union연산을 처리할 때까지 1번 과정 반복

- 서로소 집합은 무방향 그래프 내에서 사이클 판별할 때 사용할 수 있다.

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인

     루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행. 루트노드가 서로 같으면 사이클이 발생한 것

2. 모든 간선에 대해 1번 반복

 

◎ 신장 트리

- 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미

- 신장 트리 중 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 : 최소 신장 트리 알고리즘

- 트리 자료구조는 노드가 N개일 때 간선의 개수가 N-1개

 

◎ 크루스칼 알고리즘

- 대표적인 최소 신장 트리 알고리즘

- 그리디 알고리즘의 일종

- 모든 간선에 대해 정렬을 수행한 뒤 가장 거리가 짧은 간선부터 집합에 포함시킨다. 사이클을 발생시킬 수 있는 간선의 경우 집합에 포함시키지 않는다.

- 간선의 개수가 E개일 때, O(ElogE)의 시간복잡도

 

◎ 위상 정렬

- 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘

- 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

- 진입차수 : 특정한 노드로 '들어오는' 간선의 개수

- 과정

1.  진입차수가 0인 노드를 큐에 넣는다

2. 큐가 빌 때까지 다음 과정 반복

   큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 -> 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것

- 시간 복잡도 : O(V+E)