지금까지 강의를 들으면서 나온 알고리즘 개념에 대해 정리하려고 한다.

에라토스테네스 체

public static void solution(int input){
    int[] arr = new int[input+1];   //배열을 검사할때 배열과 index값을 맞추기 위해
    int count = 0;
    for(int i=2; i<=input; i++){
        if(arr[i]==0){  //arr[i] == 0일 경우 해당 index는 소수이므로 카운트
            count++;
            for(int j=i; j<=input; j+=i){  //해당 수의 배수들은 모두 체크
                arr[j] = 1;
            }
        }
    }
    System.out.println(count);
}

소수 판별 (에라토스테네스 체)

에라토스테네스 체는 소수를 판별할때 가장 시간 복잡도가 적게 풀수 있는 알고리즘인데 1은 소수가 아니므로 2부터 input까지 입력된 수가 소수인지 판별하는 알고리즘이다. 여기서 왜 시간복잡도를 빠르게 할 수 있냐면 최초 2가 들어왔을 때 arr[2] = 0이므로 count값이 올라가고 그 밑에 반복문에서 input까지 2의 배수들은 모두 1로 체크가 된다. 이렇게 되면 앞으로 실행되는 첫번째 반복문에서 arr[i] = 0에 걸리지 않으므로 첫 반복에 2의 배수들은 모두 걸려졌다. 이렇게 반복이 실행되면서 점점 소수를 제외한 수들은 걸러진 채로 실행되기 때문에 범위의 수가 더 커도 빠르게 값을 반환 받을 수 있다.

Two Pointers

public static int solution(int m){
    int answer = 0;
    int sum = 0;
    int lt = 0;
    int n = m/2+1;
    int[] natureNumber = new int[n];
    for(int i=0; i<n; i++){
        natureNumber[i] = i+1;
    }
    for(int rt = 0; rt<n; rt++){
        sum+=natureNumber[rt];
        if(sum == m) answer++;
        while(sum>=m){
            sum-=natureNumber[lt++];
            if(sum==m) answer++;
        }
    }
    return answer;
}

연속된 자연수의 합

Two Pointers라는 알고리즘은 lt와 rt의 두 포인터 값을 대신할 값을 만들어 하나의 배열에서 두 포인터를 사용하여 값을 체크하는 방법으로 많이 사용된다. 위 문제와 같이 여러 수의 합이 입력된 값이 되는 경우의 수를 구하는 방식으로도 사용된다. 이런 Two Pointer 알고리즘을 사용하는 이유는 2개 이상의 배열을 비교할땐 반복문이 2개 이상이 사용된다. 이렇게되면 시간복잡도가 O(N^2) 이상으로 증가되는데 이러면 알고리즘 문제에서 모두 탈락이다 ㅎㅎ 그렇기 때문에 이 시간복잡도를 O(N)으로 줄여주기 위해 Two Pointers 알고리즘을 사용하는 것이다.

Sliding Window

public static int solution2(int n, int[] arr){
    int answer = 0;
    int sum = 0;
    //n까지 먼저 값을 구하고
    for(int i=0; i<n; i++){
        answer += arr[i];
    }
    sum = answer;
    //다음 값부터는 sliding window 알고리즘으로 구현
    for(int i=n; i<arr.length; i++){
        sum = sum - arr[i-n] + arr[i];
        answer = Math.max(answer, sum);
    }

    return answer;
}

최대 매출
Sliding Window는 옆으로 여는 창문처럼 배열을 밀고 나가는 형상을 떠올리면 이해하기 쉬울 것이다. 이 알고리즘도 Two Pointers 알고리즘과 같이 2개 이상의 배열을 비교하거나 반복문이 2개 이상 나올때 사용하면 좋은데 시간복잡도를 동일하게 O(N)까지 줄여줄 수 있다.

Hash Sliding Window

public static ArrayList<Integer> solution2(int n, int k, int[] arr) {
    ArrayList<Integer> answer = new ArrayList<>();
    HashMap<Integer, Integer> map = new HashMap<>();
    for(int i=0; i<k-1; i++){
        map.put(arr[i], map.getOrDefault(arr[i],0)+1);
    }
    int lt = 0;
    for(int rt = k-1; rt<n; rt++){
        map.put(arr[rt], map.getOrDefault(arr[rt],0)+1);
        answer.add(map.size());
        map.put(arr[lt], map.get(arr[lt])-1);
        if(map.get(arr[lt])==0) map.remove(arr[lt]);
        lt++;
    }
    return answer;
}

매출액의 종류

위에서 사용한 Sliding Window 알고리즘을 배열 뿐 아니라 Hash에도 사용할 수 있는데. 이 또한 시간복잡도를 줄이기 위해서이다. 위 알고리즘을 사용한 문제를 살펴보면 최초 전체 데이터를 입력 받고 그 뒤에 입력받은 값만큼 구간을 나누어 해당 구간에 종류가 몇개인지 반환해주는 알고리즘인데 일반 반복이나 hash로 풀려고 하면 무조건 O(N^2) 이상이 나온다. 그래서 Sliding Window 알고리즘을 함께 사용하여 문제를 풀이해낸 것이다.

Stack Frame

스택 프레임은 코드라기 보다는 하나의 java의 메서드의 호출에 대한 개념을 이해해야하는데. JVM의 구조 이해와 Stack Frame을 함께 이해한다면 쉽게 이해할 수 있을 것이다.

재귀 호출과 JVM 구조

부분 집합 구하기 DFS

위 두 글을 차례대로 보면서 이해한다면 Stack Frame에 대해서 이해하고 재귀를 이해하기 쉬울 것이다.

DFS (Depth First Search)

DFS는 깊이 우선 탐색으로 말 그대로 트리에서 하나의 말단 노드까지 우선 탐색하며 그 다음 자식의 말단 노드까지 탐색하는 방법이라 생각하면 될거 같다. 물론 전위, 중위, 후위 순회 방식에 따라 다를 수 있다.

기본 개념은
이진 트리 순회 DFS

글을 참고하며 코드를 익히면 좋을 것 같다.

//전위 순회
public static void DFS(Node root){
    if(root==null) return ;
    System.out.print(root.data+" ");
    DFS(root.lt);
    DFS(root.rt);
}

//중위 순회
public static void DFS2(Node root){
    if(root==null) return ;
    DFS(root.lt);
    System.out.print(root.data+" ");
    DFS(root.rt);
}
//후위 순회
public static void DFS3(Node root){
    if(root==null) return ;
    DFS(root.lt);
    DFS(root.rt);
    System.out.print(root.data+" ");
}

위 3가지 방식을 탐색하는 방법으로 기본적인 구조로

if(조건) return;
DFS(root.lt);
DFS(root.rt);

와 같은 구조를 많이 취한다.

if(조건) return ;
return Max.min(DFS(root.lt), DFS(root.rt));

와 같이 노드의 최소값을 구하는 방식도 있고 해당 문제에 따라 다음과 같은 방식으로 변경하면 된다. 여기서 공통점은 조건을 통해 반환을 해주고 재귀를 통해 계속해서 탐색을 이어간다는 것이다. Stack Frame의 구조를 이해하고 있다면 결국 말단 노드의 값에 대한 반환이 이뤄져야 그 부모 노드의 반환이 이어진다는 것을 이해할 수 있을 것이다.

BFS (Breadth First Search)

BFS는 너비 우선 탐색으로 DFS가 말단 노드를 먼저 찍고 최상단으로 다시 올라오는 알고리즘이라면 BFS는 트리에서 단계별로 탐색하는 것을 의미한다.

이진트리 레벨 탐색 BFS

public void bfs(Node node){
    Queue<Node> que = new LinkedList<>();
    que.offer(node);
    int level = 0;
    while(!que.isEmpty()){
        System.out.println("level : "+level);
        int length = que.size();
        for(int i=0; i<length; i++){
            Node poll = que.poll();
            System.out.print(poll.data+" ");
            if(poll.lt != null) que.offer(poll.lt);
            if(poll.rt != null) que.offer(poll.rt);
        }
        System.out.println();
        level++;
    }
}

이진트리 레벨 탐색도 기본 구조를 먼저 이해해보자.

Queue<> que = new LinkedList<>();

우선 탐색 전 queue 자료구로를 사용하여 다음에 탐색할 트리의 노드들을 담아 둬야한다. 그래서 queue를 생성한 후 최초의 노드를 offer()를 통해 넣어준다. (여기서 offer()와 add()는 동일한 동작을 실행하는 메서드로 add()를 사용해도 무관하다.)

그 후 반복을 통해 단계별로 탐색을 시작하는데 que에는 해당 노드의 자식값이 계속해서 offer되며 다음 반복이 실행될때는 그 전 노드들의 자식들의 값을 모두 탐색하며 다시 해당 노드들의 자식 노드들이 offer된다.

지금까지 공부하며 배운 알고리즘을 틈틈히 정리해놔야 잊지 않고 계속해서 문제를 풀어낼 수 있을거 같아서 정리해봤다. 아직 배울것이 많으므로 계속해서 정리해나가자!