데일리썽

1. 순차 탐색 (Sequential Search)

탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미

데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법

2. 구현

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

@Slf4j
public class Sequential {
    public static Integer Sequential(List<Integer> dataList, Integer search) {
        for (int i = 0; i < dataList.size(); i++) {
            if (dataList.get(i) == search) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        List<Integer> dataList = new ArrayList<>();
        for (int i = 0; i < 11; i++) {
            dataList.add(rand.nextInt(11));
        }

        log.error("________________ = {}", dataList);

        log.error("________________ = {}", Sequential(dataList, 10));
    }
}

3. 분석

최악의 경우 리스트 길이가 n일 때, n번 비교해야 함

O(n)

1. 이진 탐색 (Binary Search)

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

2. 분할 정복 알고리즘과 이진 탐색

분할 정복 알고리즘 (Divide and Conquer)

• Divide : 문제를 하나 또는 둘 이상으로 나눈다.
• Conquer : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눈다.

이진 탐색

• Divide : 리스트를 두 개의 서브 리스트로 나눈다.
• Conquer :
  • 검색할 숫자 (search) > 중간값 이면 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
  • 검색할 숫자 (search) < 중간값 이면 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

3. 구현

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

@Slf4j
public class BinarySearch {
    public static Boolean binarySearch(List<Integer> dataList, Integer search) {
        log.error("________________ = {}", dataList);

        if (dataList.size() == 1 && search == dataList.get(0)) {
            return true;
        }

        if (dataList.size() == 1 && search != dataList.get(0)) {
            return false;
        }

        if (dataList.size() == 0) {
            return false;
        }

        Integer medium = dataList.size() / 2;

        if (search == dataList.get(medium)) {
            return true;
        } else {
            if (search > dataList.get(medium)) {
                return binarySearch(dataList.subList(medium, dataList.size()), search);
            } else {
                return binarySearch(dataList.subList(0, medium), search);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        List<Integer> dataList = new ArrayList<>();
        for (int i = 0; i < 11; i++) {
            dataList.add(rand.nextInt(11));
        }

        Collections.sort(dataList);

        log.error("________________ = {}", binarySearch(dataList, 10));
    }
}

4. 분석

시간 복잡도는 O(logn)

1. 병합 정렬 (merge sort)

재귀용법을 활용한 정렬 알고리즘

리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

2. 구현

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

@Slf4j
public class MergeSort {
    public static void split(List<Integer> dataList) {
        int medium = (int)(dataList.size() / 2);
        List<Integer> leftList = dataList.subList(0, medium);
        List<Integer> rightList = dataList.subList(medium, dataList.size());
        log.error("________________ = {}", medium);
        log.error("________________ = {}", leftList);
        log.error("________________ = {}", rightList);
    }

    public static List<Integer> mergeSplit(List<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }

        int medium = (int)(dataList.size() / 2);
        List<Integer> leftList = mergeSplit(dataList.subList(0, medium));
        List<Integer> rightList = mergeSplit(dataList.subList(medium, dataList.size()));

        return merge(leftList, rightList);
    }
    public static List<Integer> merge(List<Integer> leftList, List<Integer> rightList) {
        int leftIndex = 0;
        int rightIndex = 0;

        List<Integer> mergedList = new ArrayList<>();

        // leftList, rightList 남아 있을 때
        while (leftList.size() > leftIndex && rightList.size() > rightIndex) {
            if (leftList.get(leftIndex) > rightList.get(rightIndex)) {
                mergedList.add(rightList.get(rightIndex));
                rightIndex++;
            } else {
                mergedList.add(leftList.get(leftIndex));
                leftIndex++;
            }
        }

        // leftList만 남아 있을 때
        while (leftList.size() > leftIndex) {
            mergedList.add(leftList.get(leftIndex));
            leftIndex++;
        }

        // rightList만 남아 있을 때
        while (rightList.size() > rightIndex) {
            mergedList.add(rightList.get(rightIndex));
            rightIndex++;
        }


        return mergedList;
    }

    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        List<Integer> dataList = new ArrayList<>();
        for (int i = 0; i < 11; i++) {
            dataList.add(rand.nextInt(11));
        }

        log.error("________________ = {}", dataList);

        dataList = mergeSplit(dataList);

        log.error("________________ = {}", dataList);
    }
}

3. 분석

시간복잡도는 O(nlogn)

1. 퀵정렬 (quick sort)

기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성함

각 왼쪽 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하며 위 작업을 반복함

함수는 왼쪽 + 기준점(pivot) + 오른쪽을 리턴함

2. 구현

import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

@Slf4j
public class QuickSort {

    public static List<Integer> quickSort(List<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }

        List<Integer> leftList = new ArrayList<>();
        List<Integer> rightList = new ArrayList<>();
        List<Integer> pivotList = new ArrayList<>();

        Integer pivot = dataList.get(0);

        for (int i = 0; i < dataList.size(); i++) {
            if (pivot > dataList.get(i)) {
                leftList.add(dataList.get(i));
            } else if (pivot < dataList.get(i)) {
                rightList.add(dataList.get(i));
            } else {
                pivotList.add(dataList.get(i));
            }
        }
        return Stream.of(quickSort(leftList), pivotList, quickSort(rightList)).flatMap(Collection::stream).collect(Collectors.toList());
    }

    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        List<Integer> dataList = new ArrayList<>();
        for (int i = 0; i < 11; i++) {
            dataList.add(rand.nextInt(11));
        }

        log.error("________________ = {}", dataList);


        dataList = quickSort(dataList);

        log.error("________________ = {}", dataList);


    }
}

3. 분석

병합정렬과 유사

시간복잡도는 O(nlogn)

최악의 경우(pivot이 가장 크거나 가장 작으면 모든 데이터를 비교해야함) O(n^2)

문제 제목 : 효율적인 해킹

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main8 {
    public static int pcCnt, connCnt, hackingCnt, maxHackingCnt;
    public static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    public static boolean[] visited = new boolean[10001];

    public static Integer bfs(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(node);
        visited = new boolean[10001];
        visited[node] = true;

        hackingCnt = 1;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int adjNode : adjList.get(now)) {
                if (!visited[adjNode]) {
                    queue.offer(adjNode);
                    visited[adjNode] = true;
                    hackingCnt++;
                }
            }
        }

        return hackingCnt;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        pcCnt = Integer.parseInt(st.nextToken());
        connCnt = Integer.parseInt(st.nextToken());

        for (int i = 0; i < pcCnt + 1; i++) {
            adjList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < connCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int pc1 = Integer.parseInt(st.nextToken());
            int pc2 = Integer.parseInt(st.nextToken());
            adjList.get(pc2).add(pc1);
        }

        maxHackingCnt = 0;
        List<Integer> resultList = new ArrayList<Integer>();
        for (int i = 1; i < pcCnt + 1; i++) {
            int cnt = bfs(i);

            if (cnt > maxHackingCnt) {
                maxHackingCnt = cnt;
                resultList = new ArrayList<>();
                resultList.add(i);
            } else if (cnt == maxHackingCnt) {
                resultList.add(i);
            }
        }

        for (Integer result : resultList) {
            System.out.print(result + " ");
        }
    }
}

문제 제목 : 유기농 배추

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static int t, m, n, k;
    public static int[][] ground = new int[50][50];
    public static boolean[][] visited = new boolean[50][50];

    public static int[] moveX = {0, 0, -1, 1};
    public static int[] moveY = {1, -1, 0, 0};

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int nowX = now[0];
            int nowY = now[1];

            for (int i = 0; i < 4; i++) {
                int nextX = nowX + moveX[i];
                int nextY = nowY + moveY[i];
                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                    if (ground[nextX][nextY] == 1 && !visited[nextX][nextY]) {
                        queue.offer(new int[] {nextX, nextY});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nextX = x + moveX[i];
            int nextY = y + moveY[i];

            if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                if (ground[nextX][nextY] == 1 && !visited[nextX][nextY]) {
                    dfs(nextX, nextY);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();

        for (int i = 0; i < t; i++) {
            m = sc.nextInt();
            n = sc.nextInt();
            k = sc.nextInt();

            ground = new int[50][50];
            visited = new boolean[50][50];

            for (int j = 0; j < k; j++) {
                int y = sc.nextInt();
                int x = sc.nextInt();
                ground[x][y] = 1;
            }

            int result = 0;

            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (ground[j][k] == 1 && !visited[j][k]) {
                      //  bfs(j, k);
                        dfs(j, k);
                        result++;
                    }
                }
            }

            System.out.println(result);
        }
    }
}

문제 제목 : 바이러스

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static int pcCnt;
    public static int connCnt;
    public static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    public static boolean[] visited = new boolean[101];
    public static int resulCnt;

    public static void addEdge(int n, int m) {
        adjList.get(n).add(m);
    }

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

        while (!queue.isEmpty()) {
            int now = queue.poll();
            resulCnt++;
            for (int i = 0; i < adjList.get(now).size(); i++) {
                int adjNode = adjList.get(now).get(i);
                if (!visited[adjNode]) {
                    queue.offer(adjNode);
                    visited[adjNode] = true;

                }
            }
        }


    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        pcCnt = sc.nextInt();
        connCnt = sc.nextInt();

        for (int i = 0; i < pcCnt + 1; i++) {
            adjList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < connCnt; i++) {
            int pc1 = sc.nextInt();
            int pc2 = sc.nextInt();
            addEdge(pc1, pc2);
            addEdge(pc2, pc1);
        }

        bfs(1);
        System.out.println(resulCnt - 1);
    }
}

문제 제목 : 숨바꼭질

난이도 : 하

문제 유형 : BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.util.*;

public class Main {
    public static int n, k;
    public static int MAX = 100001;
    public static boolean[] visited = new boolean[MAX];
    public static int[] time = new int[MAX];

    public static Integer bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        visited[n] = true;

        while (!queue.isEmpty()) {
            int now = queue.poll();

            if (now == k) return time[now];

            int next = now - 1;
            if (next >= 0 && next < MAX && !visited[next]) {
                queue.offer(next);
                visited[next] = true;
                time[next] = time[now] + 1;
            }

            next = now + 1;
            if (next >= 0 && next < MAX && !visited[next]) {
                queue.offer(next);
                visited[next] = true;
                time[next] = time[now] + 1;
            }

            next = now * 2;
            if (next >= 0 && next < MAX && !visited[next]) {
                queue.offer(next);
                visited[next] = true;
                time[next] = time[now] + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        System.out.println(bfs());
    }
}