KOMAS

알아야 할 개념

시간복잡도, 공간 복잡도

알아야 할 자료구조

배열, 연결 리스트, 스택, 큐, 덱, 힙, 트리, 해시, 그래프

알아야 할 알고리즘

정렬, 구현, 재귀, 그리디, 탐색(+DFS/BFS, 백트래킹, 이분 탐색), 다이내믹 프로그래밍, 그래프 알고리즘

알고리즘

배열 문제

Array, LinkedList

Sliding window

Two Pointer

1차원 BFS/DFS

구현

재귀

Back Tracking

Union-Find

Divide and Conquer

그리디

정렬

기본 정렬 문제

Merge Sort

Quick Sort

탐색

DFS/BFS

Back Tracking

이분 탐색

Binaray Search

Parametric Search

다이내믹 프로그래밍

기본 DP

2차원 DP

최장 증가 부분 수열(LIS)

그래프

최단경로

Dijkstra

Floyd-Warshall

최소 신장 트리(Minimum Spanning Tree)

Kruscal

Prim

위상 정렬(Topology sort)

BinarySearch를 사용하면 검색 범위를 logN으로 엄청나게 단축시킬 수 있다.

만약 탐색할 범위가 너무 크다면 고려해봐야 한다.

특히 응용이라고 할 수 있는 최댓값, 최솟값을 찾아야 하는 이분 탐색을 이용하는

매개 변수 탐색 Parametric Search는 굉장히 유용하다.

주의할 점은 이분 탐색을 사용하기 이전에 탐색할 배열은 무조건 정렬되어있어야 한다.

이분 탐색은 기준 값과 가변 값을 통해 Start와 End를 결정한다.

package Search.BinarySearch;

public class BinarySearchTest {

    static int[] arr;

    public static void main(String[] args) {
        arr = new int[]{1,3,5,7,9,11,13};
        int idx = BinarySearchCode(9);
        System.out.println(idx);
    }

    public static int BinarySearchCode(int findNumber){
        int s = 0;
        int e = arr.length - 1;
        int mid;

        int returnNumber = 0;

        while(s <= e){
            mid = (s+e) / 2;

            if(findNumber == arr[mid]) {
                returnNumber = mid;
                break;
            }
            else if(findNumber > arr[mid])
                s = mid + 1;
            else if(findNumber < arr[mid])
                e = mid - 1;
        }
        return returnNumber;
    }
}

이분 탐색의 코드 자체는 간단하다.

left에서 시작하는 s, right에서 시작하는 e가 서로 교차하게 되면 종료한다.

(s+e)/2를 이용한 중간 값 mid를 계속 조건에 맞게 변화시키며 탐색범위를 이분한다.

찾지 못하였다면 그냥 종료될 것이고, 찾았다면 idx를 리턴한다.

이분 탐색에서 가장 중요하다고 생각하는 점은

변하는 가변 값과 변하지 않는 기준 값이다.

기준 값과 가변 값과의 비교를 통해 s, e 범위를 결정한다.

현재 코드에서는 찾을 숫자(기준 값)를 기준으로

mid를 이용해서 가변 값과의 비교를 통해 s, e를 결정하고 있지만

Prametric Search를 하게 되면 기준 값은 문제를 보고 결정을 해주어야 한다.

public static long binarySearch(int need){
    long s = 0;
    long e = 2_000_000_000;
    long returnHeight = 0;

    while(s <= e){
        long mid = (s + e) / 2;

        // 기준값 설정
        // 자른 값들의 총합을 이용
        long sum = 0;
        for(int i = 0; i<arr.length; i++){
            int ele = arr[i];
            if(ele > mid)
                sum += ele - mid;
        }

        if(sum >= need) { // 조건을 만족하므로 범위를 더 엄밀하게 줄임
            s = mid + 1;
            returnHeight = mid;    // 조건을 충족한다면 일단 저장
        }else if(sum < need)
            e = mid - 1;
    }
    return returnHeight;
}

백준 2805 나무자르기 문제의 코드 일부다.

해당 문제에서 기준 값은 need 이다. (함수의 매개변수로 받고 있음)

가변 값은 mid를 이용해 구한 sum이다.

mid를 기준으로 자른 값들의 총합(sum)이 need 이상이면,

더 엄밀하게 자르기 위해 s를 더 올려서 mid를 높인다.

만족하지 않는다면 e를 낮춰서 mid를 낮춘다.

탐색 범위를 마지막에 만족하는 것까지 좁힐 수 있으므로 최대값을 구할 수 있다.

이분 탐색, 매개 변수 탐색을 구현할 땐 기준 값, 가변 값을 무엇으로 할 지 항상 생각하자.

Prametric Search 문제

https://www.acmicpc.net/problem/2805

https://www.acmicpc.net/problem/1654

[알고리즘] 다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm)

다익스트라 알고리즘은 출발지 -> 경유지 -> 목적지를 이용하여 최단 경로를 구하게 된다.

이 과정을 반복하게 되면 고정된 출발지에서 모든 edge의 최단 경로를 구할 수 있다.

필요 사항

우선 순위 큐 (순서대로 확인하는 것이 아닌, 거리가 가장 짧은 것부터 수행하기 때문에 수행 시간을 단축)

고정된 출발지에서 목적지까지의 경로 값 저장 배열

최소 비용을 만들기 위해 필요한 Node의 개수는 항상 3개라고 생각해야 한다. [출발, 경유, 목적]

출발지 -> 경유지, 경유지 -> 목적지로 따로 생각해야 한다.

경유지를 반복문을 돌리므로 목적지는 복수개다.

주목할 부분은 경유지 -> 목적지 인 부분이다.

목적지였던 부분이 다음부터 경유지로 사용이 되어

경유지가 향하는 모든 edge의 비용을 확인한다.

퍼져나가는 방식으로 최종적으로 모든 노드의 최소 비용을 알 수 있다.

round 1 = 경유지 -> 목적지

round 2 = 경유지 -> 목적지 

round 3 = 경유지 -> 목적지

[목적지가 최소 경로 비용으로 처리되면 다음부터는 목적지가 경유지로 쓰임]

BFS 동작 방식과 유사하다.

동작 예시

다익스트라 알고리즘은 경유지로 가장 먼저 자기 자신을 기준으로 update 한다.

1번 노드에서 3, 4번 노드를 update 시켜줄 수 있다.

[1 -> 1 -> 3]     [1 -> 1 -> 4]

dist배열 = [INF, 0, INF, 6, 3, INF]  // 0번은 편의를 위해 사용하지 않는다.

3, 4번 노드가 update 되고,

큐에 3, 4번 노드가 들어갔다.

4번 노드의 가중치가 가장 작으므로 우선순위 큐에 의해 가장 먼저 나온다.

4번 노드에서 2, 3번 노드를 update 시켜줄 수 있다.

[1 -> 4 -> 2]      [1 -> 4 -> 3]

dist배열 = [INF, 0, 4, 4, 3, INF] 

2, 3번 노드가 update 되고,

큐에 2, 3번 노드가 들어갔다.

현재 큐에 3번 노드가 두 번 들어갔다.

이 경우는 먼저 들어간 3번 노드는 가중치가 6으로 dist [3]의 값보다 크므로 사용되지 않고 버려진다.

1 -> 1 -> 3 경로보다 1 -> 4 -> 3 경로가 최소 비용이므로 1 -> 4 -> 3을 사용하면 되기 때문이다.

(update 된 거리보다 크다면, update 한 노드는 큐에 들어간 것이므로 최소가 보장. 버려도 되는 이유)

이 같은 방식으로 시작 노드를 기준으로 퍼져나가며 모든 노드의 최소 비용을 계산한다.

다익스트라 알고리즘은 방향 그래프여야 하며, 거리가 음수면 안된다.

거리가 음수, 그리고 사이클이 존재한다면 거리를 계속 줄이는 음수 사이클이 발생. -무한대 형성

public class Dijkstra {
    static int[] dist;
    static int[] path; // 자신의 앞 경로를 갖고 있다. ** 모든 경로를 확인할 수 있다.

    static List<List<Node>> list = new ArrayList<>(); // 간선들

    static final int edgeCount = 5 + 1;
    static final int vCount = 7;

    public static void main(String[] args) {
        //노드 5개
        dist = new int[edgeCount]; // 0 사용안함.
        path = new int[edgeCount];
        //간선 7개
        for(int i = 0; i<=vCount; i++) {
            list.add(new ArrayList<>());
        }

        // (1 - > 5) 2000 쓰는 경로
        list.get(1).add(new Node(4, 2000));
        list.get(1).add(new Node(5, 2000));

        // (1 -> 5) 10 쓰는 경로
        list.get(1).add(new Node(2, 5));
        list.get(2).add(new Node(5, 5));

        // (1 -> 5) 3 쓰는 경로
        list.get(1).add(new Node(3, 1));
        list.get(3).add(new Node(4, 1));
        list.get(4).add(new Node(5, 1));

        
        // TODO: 이 부분 주의 자신은 0으로 만들어야함
        // 자기 자신 빼고 나머지 INF 로 초기화
        Arrays.fill(dist, 100_000_000);
        dist[1] = 0; // 시작

        
        dijk();

        // 결과
        System.out.println(Arrays.toString(dist));
        // 경로
        System.out.println(Arrays.toString(path));
    }

    // TODO: 출발지 1번은 계속 고정
    public static void dijk(){
        Queue<Node> q = new PriorityQueue<>((o1,o2) -> o1.w - o2.w);
        q.add(new Node(1, 0)); // 경유지, 비용 (1 -> 1 -> n)

        while(!q.isEmpty()) { // TODO: 경유지 뽑기 // 1 -> M
            Node mid = q.poll(); // 1과 연결된 경유지
            
            // 과거 ,  현재
            if(mid.w > dist[mid.dest]) // update 된 거리보다 큐에서 뽑은게 더 크면 사용 안하고 버림
                continue;

            // TODO: 경유 -> 도착 꺼내는 부분
            for(Node d : list.get(mid.dest)){
                if(dist[d.dest] > dist[mid.dest] + d.w){ // 갱신이 되는 부분.
                    dist[d.dest] = dist[mid.dest] + d.w;
                    // 갱신이 된 것. 1->n , n->M
                    // (1 -> 도착지)  [[ (1 -> 경유(테이블)  + 경유(테이블) - > 도착지 ]]
                    // 계속 갱신       계속 생신

                    // TODO: 현재 목적지가 다음부터는 경유지로 쓰인다.
                    q.offer(new Node(d.dest, dist[d.dest]));
                    // 갱신된 (1 -> 목적지) 를 넣어준다.
                    // 갱신된걸 넣지 않으면 for 부분을 또 확인하기 때문에 갱신된 값을 넣어주는게 좋다.

                    path[d.dest] = mid.dest; // 길찾기 용도 (자신의 앞 노드)
                }
            }
        }
    }
}

// 경유지로도 쓰고, 목적지로도 쓰임
class Node{
    int dest; // 도착지
    int w; // 가중치

    Node(int dest, int w){
        this.dest = dest;
        this.w = w;
    }

    public String toString(){
        return this.dest + " " + this.w;
    }
}

[알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm)

플로이드 워셜 알고리즘은 edge에서 edge로 이동할 때 최소비용을 구하는 알고리즘이다.

모든 경로의 최소비용을 구할 수 있다.

구현

플로이드 워셜 알고리즘의 구현은 간단하다.

k, i, j를 사용하는 3중 for문이 있을 때

3중 for문으로 가장 바깥 k를 사용하는 for문은 edge의 총개수만큼 반복한다.

k는 중간에 거쳐가는 edge이다.

i는 시작 edge, j는 도착 egde로 사용한다.

현재 비용보다 거쳐가는 비용이 더 적다면 거쳐가는 비용을 사용한다.

자기 자신으로 가는 경로는 0, 도착이 불가능한 경로는 INF(충분히 큰 값)로 표시한다.

이해

구현은 간단하지만 이해는 쉽지 않았다.

플로이드 워셜 알고리즘은 가장 바깥 for문

즉, 거쳐가는 k가 계속 증가한다고 생각하면 된다.

(경로 값이 크다면 증가하지 않겠지만, 이해를 위해 증가한다고 생각)

[거쳐가는 edge]

 시작 -> 0 -> 도착

시작 -> 0->1 -> 도착

시작 -> 0->1->2 -> 도착

시작 ->  0->1->2->3... -> N개의 edge까지 -> 도착

단순히 거쳐가는 경우가 증가하게끔 나타냈지만

 모든 순열의 경로를 알 수 있다.

시작 -> 0->1 -> 도착

시작 -> 1->0 -> 도착

시작 -> 2->4->1 -> 도착

시작 -> 1->4->2->3->5 -> 도착

...

다른예제

k는 0번 edge부터 가장 마지막 edge까지  증가하며

i 부터 j까지 가는 모든 경우를 계속 갱신한다.

예를 들어

가장 처음 0번을 거쳐가는 경우를 생각하자. (k= 0)

0번을 거치며 2번 edge에서 4번 edge의 경로는 갱신되어

2번 (시작)  ->  0번 (거쳐감)  ->  4번 (도착)

2번 -> 4번 는 현재까지의 최소비용으로 갱신되었다.

(k=1)인 경우는 잠시 제쳐두고

그다음 2번을 거쳐가는 경우를 생각하자. (k=2)

그럼 2번을 거쳐가는 경우에서

1번 (시작) -> 2번 (거쳐감) -> 4번 (도착)

을 갱신하려 할 때

보기에는 단순히 2번을 거쳐가는 것으로 보이지만 사실

2번 -> 4번은

2번 -> 0번 -> 4번 을 사용한다. 이게 현재까지의 최소비용이었기 때문이다.

dist[2][4]는 2->0->4로 update되어있다.

1번 -----------> 2번 ------(0번을 지나는 경로)------> 4번

결국, 앞에서 구한 최소 경로를 반복적으로 사용하기 때문에

보기완 달리 사실 많은 edge들을 이동하는 경로의 최소 비용을 사용하는 것이다.

[JAVA] 알고리즘 DFS [Depth-First Search] 깊이 우선 탐색

DFS [Depth-First Search]는 깊이 우선 탐색이며 깊이를 우선적으로 탐색합니다. 

2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며 깊이 탐색을 통해 방문하여 모든 노드를 탐색하는 방법입니다.

BFS와 마찬가지로 모든 노드를 탐색하는 방법 중 하나입니다.

• DFS - 재귀, stack 자료 구조 활용
• BFS - Queue 자료 구조 활용

DFS를 코드로 구현하기 위해선 3가지가 필요합니다.

• 탐색할 2차원 배열 또는 그래프
• 방문처리를 하기 위한 boolean type 
• Stack 자료 구조 또는 재귀 함수

방문체크를 위한 boolean 배열과 그래프를 선언합니다.

추가로 Stack 자료 구조를 활용하기보다는 재귀 함수를 통해서 구현해보도록 하겠습니다.

가장 먼저 DFS의 매개변수로 들어온 int x 노드부터 깊이 탐색을 진행합니다.

x 노드를 다시 방문하지 않도록 방문처리를 가장 먼저 처리해주도록 하겠습니다. 

x 노드와 연결된 노드들을 확인하기 위해 for (int i = 0; i < graph [x]. length; i++) 반복문을 사용하여

x 노드와 연결된 모든 노드들을 확인해줍니다.

반복을 통해 하나씩 확인해가며  if (! visited [graph [x][i]])를 이용하여 이미 방문이 돼있다면 true,

방문하지 않았다면 false 이므로 방문하지 않아야만 재귀 함수를 통해 해당 노드를 DFS 인자로 넣은 후 호출해줍니다.

여기서 생각해야 할 점은 재귀 함수를 호출하여 제어를 넘겨주었으므로

for 반복문은 재귀 함수가 완전히 처리된 이후에 다시 제어를 얻어 진행하던 반복을 진행하게 됩니다.

호출한 함수가 완료되야 제어를 얻어 다음 노드로 반복을 진행하게 됩니다.

이러한 재귀 함수를 이용하는 점이 바로 Stack 자료 구조 방식으로 깊이 탐색을 가능하도록 해줍니다.

간단하게  말하자면, 해당 dfs함수에서 재귀함수를 호출하면 현재 진행하는 반복이 멈춘후 재귀함수를 먼저 진행한다. 라고 생각하시면 됩니다.

전체 코드

[JAVA] 알고리즘 BFS [Breadth-First Search] 너비 우선 탐색

BFS [Breadth-First Search]는 너비 우선 탐색이며 너비를 우선적으로 탐색합니다. 

2차원 배열이나 그래프 탐색에서 한번 방문한 노드는 다시 방문하지 않으며 주변을 순차적으로 방문하여 모든 노드를 탐색하는 방법입니다.

모든 노드를 탐색하는 알고리즘으로 깊이 우선 탐색을 하는 DFS와는 달리 Stack을 이용하지 않으며 Queue를 이용하여 전개할 수 있습니다.

• DFS - 재귀, stack 자료 구조 활용
• BFS - Queue 자료 구조 활용

BFS를 코드로 구현하기 위해서 3가지를 우선적으로 구현해놓아야 합니다. 

• 탐색할 2차원 배열 또는 그래프
• 방문처리를 하기 위한 boolean type 
• Queue 자료 구조

굳이 static으로 처리할 필요는 없습니다.

여러 함수에서 사용될 것이라 예상되면 매개변수로 넘겨주는 방법 대신에 클래스 변수로 처리하여

모든 함수에서 바로 사용할 수 있게끔 하는 편입니다.

앞서 선언된 3가지를 이용해서 BFS함수를 작성하도록 하겠습니다.