알고리즘 면접 준비

정렬 차이

https://yeo-computerclass.tistory.com/422

정렬 정리(선택, 버블, 삽입, 합병, 퀵, 힙 정렬)

 

---

이분 탐색

• 정렬된 배열을 이분 분할하여 탐색하는 알고리즘
• 시간 복잡도: O(logN)

    public static int binarySearch(int target, int[] arr) {
        Arrays.sort(arr);

        int start = 0;
        int end = arr.length-1;

        while(start <= end) {
            int mid = (start + end) / 2;

            if(target == arr[mid]) {
                return mid;
            }
            else if(arr[mid] < target) {
                start = mid + 1;
            }
            else {
                end = mid - 1;
            }
        }

        return -1;
    }

---

투 포인터

배열을 가리키는 2개의 포인터를 이용해 원하는 값을 추출하는 알고리즘 방식이다.

반복문(for, while)에서 탐색할 때 효율을 위해 종종 쓰이며 단순히 일차원 배열을 투 포인터로 탐색하는 것입니다. 

(문제 참고: https://www.acmicpc.net/problem/2003)

int start = 0; //첫 번째 포인터
long sum = 0;
int cnt = 0;

for (int end = 0; end < N; end++) {
	sum += arr[end];
	while (sum > target) {
		sum -= arr[start++];
	}
	if (sum == target) cnt++;
}

---

DFS & BFS

• DFS
  깊이 우선 탐색, 한 노드에서 시작하여, 연결된 가장 깊은 노드까지 방문하는 방식입니다. 
• BFS
  넓이 우선 탐색, 한 노드에서 시작하여, 인접한 노드를 먼저 탐색하는 방식입니다.

public static void dfs(int curNode) {
        visited[curNode] = true;
        System.out.print(curNode + " ");

        for (int nextNode = 1; nextNode <= n; nextNode++) {
            if (map[curNode][nextNode] == 1 && visited[nextNode] == false) {
                dfs(nextNode);
            }
        }
    }

    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            int curNode = q.poll();
            System.out.print(curNode + " ");

            for (int nextNode = 1; nextNode <= n; nextNode++) {
                if (map[curNode][nextNode] == 1 && visited[nextNode] == false) {
                    q.offer(nextNode);
                    visited[nextNode] = true;
                }
            }
        }
    }

---

Dijksta

한 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘

• 우선순위 큐를 사용하면 시간 복잡도: O(ElogV)
   각 노드마다 연결된 간선을 탐색하는 시간은 (E)이고 우선순위 큐(=힙 트리)를 이용하기 때문에 logV를 곱해주어야 합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {
    static int INF = Integer.MAX_VALUE;
    static ArrayList<Node>[] graph;
    static int[] dist;

    public static void main(String[] args) throws IOException {

        int V, E;
        int start;
        int u, v, w;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine());

        graph = new ArrayList[V + 1];
        dist = new int[V + 1];

        for (int i = 1; i <= V; i++) {
            graph[i] = new ArrayList<>();
            dist[i] = INF;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            graph[u].add(new Node(v, w));
        }

        dijkstra(start);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if (dist[i] == INF) sb.append("INF\n");
            else sb.append(dist[i] + "\n");
        }

        System.out.println(sb);
    }

    static void dijkstra(int start) {
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(); //오름차순
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            int now = curNode.v;
            int cost = curNode.cost;

            if (dist[now] < cost) continue;
            for (int i = 0; i < graph[now].size(); i++) {
                int next = graph[now].get(i).v;
                int nextCost = cost + graph[now].get(i).cost;
                if (nextCost < dist[next]) {
                    dist[next] = nextCost;
                    pq.add(new Node(next, nextCost));
                }
            }
        }

    }

    static class Node implements Comparable<Node> {
        int v, cost;

        public Node(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
}