고민의 흔적

이진 탐색

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

이진 탐색 핵심 이론

1.  현재 데이터셋의 중앙값을 선택한다.
2. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 과정 1 ~ 3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

시간복잡도

O(logN)

코드 예시

int start = 0;
int end = arr.length - 1;
while(start <= end) {
	int mid = (start + end) / 2;
    int midv = arr[mid];
    if(midv > target) {
    	end = mid - 1;   // 핵심 : 중간값이 찾고자하는 값보다 크면 end를 바꿈
    } 
    else if (midv < target) {
    	start = mid + 1;  // 핵심 : 중간값이 찾고자하는 값보다 작으면 start를 바꿈
    }
}

BFS

너비 우선 탐색으로 그래프를 완전 탐색하는 알고리즘 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다. 또한 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

BFS 핵심 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

   BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다.

   그래프를 인접 리스트로 표현하는 것이 역시 DFS와 동일하다.

2. 큐에서 노드를 꺼낸후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

   큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다.

   이때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다.

   또한 큐에서 꺼낸 노드는 탐색 순서에 기록한다.

3. 큐 자료구조에 값이 없을 때까지 반복하기

   큐에 노드가 없을 때까지 앞의 과정을 반복한다.

코드 예시

static boolean visit[];   // 방문 배열 선언
static ArrayList<Integer>[] A;  // 인접리스트 선언

public static void BFS(int Node) {
	Queue<Integer> que = new LinkedList<Integer>();
    que.add(Node);
    visit[Node] = true;
    
    while(!que.isEmpty()) {
    	int now = que.poll();
        for(int i : A[now]) {
        	if(!visit[i]) {
            	visit[i] = true;
                que.add(i);
            }
        }
    }
}

시간 복잡도(노드 수 : V, 에지 수 : E)

 - 인접 리스트 = O(V+E)

 - 인접 행렬 = O(V^2)

DFS

깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

DFS 핵심 이론

DFS는 한번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현한다.

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

   DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기이다.

2. 스택에서 노드 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입

   pop을 수행하여 노드를 꺼낸다.

   꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크한다.

3. 스택 자료구조에 값이 없을 때까지 반복

   앞의 과정을 스택 자료구조에 값이 없을 때까지 반복한다.

   이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는다.

코드 예시

static boolean visit[] // 방문 배열 선언
static ArrayList<Integer>[] A // 인접 리스트 선언

public static void DFS(int Node) {  // DFS 구현하기
	visit[Node] = true;
    for(int i : A[Node]) {
    	if(!visited[i]) {
        	DFS(i);
        }
    }
}

시간 복잡도(노드 수 : V, 에지 수 : E)

 - 인접 리스트 = O(V+E)

 - 인접 행렬 = O(V^2)

스택

스택은 삽입과 삭제 연산이 후입 선출 LIFO로 이뤄지는 자료구조이다. 후입 선출은 삽입과 삭제가 한쪽에서만 일어나는 특징이 있다.

스택 용어

위치

• top : 삽입과 삭제가 일어나는 위치를 뜻한다.

연산

• push : top 위치에 새로운 데이터를 삽입하는 연산
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산

스택의 중요성

스택은 깊이우선탐색, 백트래킹 종류의 알고리즘에 사용되므로 반드시 알아 두어야 한다.

후입 선출은 개념 자체가 재귀 함수 알고리즘 원리와 같다.

큐 

큐는 삽입과 삭제 연산이 선입선출 FIFO로 이뤄지는 자료구조이다. 스택과 다르게 먼저 들어온 데이터가 먼저 나간다. 그래서 삽입과 삭제가 양방향에서 이뤄진다.

큐 용어

• rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.
• front : 큐에서 가장 앞의 데이터를 가리키는 영역이다.
• add : rear 부분에 새로운 데이터를 삽입하는 연산이다.
• poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
• peek : 큐의 맨 앞에 있는 데이터를 확인할 때 사용하는 연산이다.

큐는 너비 우선 탐색에서 자주 사용하므로 중요한 자료구조입니다.

우선순위 큐

우선순위 큐는 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다.

큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다. 우선순위 큐는 일반적으로 힙을 이용해 구현하는데 힙은 트리 종류 중 하나이다. 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. 

최대 힙(Max Heap)이란?

• 최대 힙(Max Heap)은 부모 노드가 자식 노드보다 값이 큰 완전 이진트리를 의미한다.
• 최대 힙의 루트 노드는 전체 트리에서 가장 큰 값을 가지는 특징이 있다.
• 항상 전체 크리가 최대 힙 구조를 유지하도록 자료구조를 설계해야 한다.
• 최대 힙도 큐를 기반으로 동작하기 때문에 push, pop이라는 함수가 있다.

우선순위 큐와 큐의 차이점

• 일반적인 큐: 선형적인 형태를 가지고 있다.
• 우선순위 큐: 트리(Tree) 구조로 보는 것이 합리적이다.

시간 복잡도

• 우선순위 큐의 삽입과 삭제는 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도이다.
• 우선순위 큐를 이용한 정렬은 𝑂(𝑁𝑙𝑜𝑔𝑁)의 시간 복잡도이다.

투 포인터

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬되어있는 두 리스트의 합집합에도 사용된다.

시간 복잡도

투 포인터는 O(n)의 시간 복잡도를 가집니다.

1. sum에 누적을 시키면서 전체를 탐색하는 투 포인터 이동 원칙

투 포인터 이동 원칙을 활용해 배열의 끝까지 탐색하면서 합이 N이 될 경우의 수를 구한다.

start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 효과가 같으며, end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장한다는 의미이다. 같을 때는 1 증가시키고 end_index를 오른쪽으로 이동한다.

while(end_index != N) 일 때까지 반복

• sum > N : sum = sum - start_index; start_index++;
• sum < N : end_index++; sum = sum sum + end_index;
• sum == N : end_index++; sum = sum + end_index; count++;

2. 2개를 가지고 전체를 탐색하는 투 포인터 이동 원칙

오름차순으로 정렬해야된다. 

while( i < j )

• A[i] + A[j] > M : j--;   -> 번호의 합이 M보다 크므로 큰 번호 index를 내린다.
• A[i] + A[j] < M : i++;  -> 번호의 합이 M보다 작으므로 작은 번호 index를 올린다.
• A[i] + A[j] == M : i++; j--; count++;  -> 양쪽 포인터를 모두 이동시키고 count를 증가시킨다.