Red-Black Tree 속성/검색/삽입/삭제, 시간복잡도

1. Red-Black Tree

 이진트리 중 Binary Search Tree인 경우에는 한쪽에만 노드들이 치우쳐 있어 균형잡힌 트리가 만들어지지 않을 수 있다. 그렇다면 탐색을 하기 위한 시간이 늘어나게 되는 단점이 있는데, 이를 보완하여 균형잡힌 트리를 만들고자 만들어진 자료구조가 Red-Black Tree라는 것이다.

---

2. Red-Black Tree 정보

Red-Black Tree는 각 노드의 색깔을 red, black 중에 선택하여, 주어진 조건을 만족시켰을 때 성립하는 Tree이다.
Red-Black Tree의 성립조건은 다음과 같다.
 

1. 루트 노드는 언제나 Black이다.

1. Leaf 노드 (말단 노드) 또한 언제나 Black이다.

1. 만약 노드가 Red라면, 그 노드의 자식들은 언제나 Black이다. 즉, red node가 연속으로 올 수 없다.

1. 루트에서 말단 노드까지의 Black node의 개수는 언제나 동일하다. 

 Red-Black Tree의 예시, 출처: wikipedia

위 그림이 Red-Black tree의 예시라고 할 수 있다. 여기서 NIL은 말단 노드를 뜻하고 위의 그림을 보면 red black tree의 property를 모두 만족시켰다는 것을 잘 알 수 있다. 그러면 이제 Red-Black Tree에서의 검색, 삽입, 삭제를 어떻게 구현하는지 살펴보자. 

---

1. 검색

Red-Black Tree에서의 검색은 일반 Binary Search Tree에서의 검색과 동일하다. 만약 parent node보다 찾으려는 숫자가 작다면 왼쪽 child node로 이동해주고, 숫자가 크다면 오른쪽 child node로 이동해주면 된다. 
검색의 경우는 Red-Black Property가 존재한다고 해서 달라지는 부분이 없기 때문에 삽입과 삭제에 집중해보자.

---

2. 삽입 (Insertion) 

먼저 노드를 삽입하려고 하면 그 노드의 색깔을 정해주어야 한다. 우리는 Red-Black Tree에서 삽입할 노드는 무조건 Red라고 가정하고 시작한다. 
여기서 아무 문제없이 삽입이 잘 되는 경우는 삽입하려고 하는 노드의 부모 노드의 색깔이 black일 경우이다. 왜냐하면 Red-Black property 3번에 의해 Red 위에 Red가 나올 수 없기 때문에 Red 위의 부모 노드가 Black일 경우에는 아무런 추가 조치 없이 삽입이 가능해진다. 
 

삽입에서 문제가 없는 경우

즉 위와 같은 그림에서는 전혀 문제가 되지 않는다. 여기서 하얀색으로 표현한 것은 상황에 따라 Red/Black이 되는 경우인데 Red/Black으로 칠해진 노드만 집중해서 보기 위해서 다른 노드는 하얀색으로 표현해놓았다.
 
하지만 문제가 되는 경우는 삽입하려는 부모의 노드가 빨간색일 경우이다. 

삽입에서 문제가 되는 경우

위 그림처럼 Red node가 연속으로 오게 된다면 Red-Black Property 3번을 충족시키지 못한다. 따라서 이 경우에는 추가적인 조치가 필요하다. 
 
이를 위해 우리는 경우를 몇 가지로 나누어볼 수 있다. 

기본골격

위와 같은 기본 구조에서 p와 대칭점에 있는 노드를 우리는 s라고 부를 것이다. sibiling, 형제노드의 약자이다. s 노드가 Red냐 Black이냐에 따라서 삽입의 조정 방법이 달라진다. 
 

s가 Red일 경우 

• 먼저 s가 Red일 경우부터 살펴보겠다.

s가 Red일 경우

위 그림처럼 생각해볼 수 있는데 이 경우에는 아래처럼 바꾸어주면 된다.

 

즉 p와 s 노드를 둘 다 Black으로 바꾸어 주고 P의 parent node를 red로 바꾸어주는 것이다. 하지만 만약 p^2의 parent node 또한 red 였다면 추가적으로 문제가 생긴다. 이 경우에는 p^2 노드를 recursive하게 하여 추가적인 조정을 해주어야 한다. 

 

• 다음으로 만약 s 노드는 Black이고 추가하려는 x 노드가 p의 left child일 경우를 살펴보자

즉, 위와 같은 경우라고 볼 수 있다. 이런 경우에는 아래의 그림처럼 조정해주면 된다. 

즉 p 노드를 중심으로 right rotate를 시키고 p 노드의 색깔을 red 에서 black으로 바꾸어주면 되는 것이다. 

 

• 마지막으로 s 노드가 black이면서 x는 p의 right child인 경우를 살펴보자

위 그림과 같은 경우를 의미한다. 이 경우에는 아래와 같이 변경해주면 된다.

하지만 이런 식으로 변경해도 x과 p가 연속적으로 red가 나타났기 때문에 문제가 된다. 하지만 이 경우는 위에서 s 노드가 black이고 새로운 노드가 left child 인 경우에 해당되기 때문에 두번째 경우로 이동해서 추가적으로 처리해주면 된다. 

 

---

3. 삭제

다음으로는 조금 더 까다로운 Red-Black Tree에서의 삭제를 알아보겠다. 

만약 삭제하려는 노드가 Red면 그 노드만 삭제해주면 되고, Black이더라도 child node가 Red라면 해당 노드를 삭제해주고 child의 색깔을 Black으로 바꿔주면 아무 문제가 없다. 

 

문제가 되는 경우는 삭제하려는 노드와 그 자식 노드의 색깔이 모두 다 Black일 경우이다. 왜냐하면 Red-Black tree property 4번에 의해 leaf 노드까지의 black node의 개수는 모두 일정해야 하기 때문이다. 하지만 Black 노드를 하나 삭제해 버린다면 그러한 property가 깨지기 때문에 문제가 생기는 것이다. 그래서 삭제의 경우에도 몇 가지 경우를 나누어보겠다. 

 

아래 그림에서 x 노드는 Black인 노드 m을 삭제하고 난 이후의 child node를 의미하게 된다. 하지만 Black node의 개수가 하나 모자라기 때문에 옆에 -1로 표시하겠다. 

 

Case 1.

삭제한 이후의 검정색 노드가 하나 모자라는 노드를 x로 표시했을 때 위와 같은 그림이 case 1이다. s 는 Black이고 s의 left child와 right child 노드가 모두 Black인 경우다. 이 경우는 가장 간단한 경우로 아래와 같이 조정해주면 된다.

 

위와 같이 조정해주면 p 노드가 Black으로 바뀌면서 x 노드까지의 경로에 모자랐던 black 노드의 개수를 하나 늘려줌으로써 문제가 해결된다. 

 

case 2.

case1과 유사하지만 이번에는 p 노드까지 모두 다 Black이다. 

이번에도 s 노드를 Red로 바꾸어주지만 Black 노드가 하나 부족한 것이 p node로 전이되었다고 할 수 있다. 그러므로 여기서는 p 노드를 문제 노드로 놓고 재귀적으로 또 문제를 해결해주어야 한다. 

 

case 3. 

s 노드는 black이고 r node가 red인 경우를 뜻한다. 여기서도 마찬가지로 하얀색 노드는 red/black이 와도 괜찮다는 뜻이며 red/black 각각의 경우에 대해 대입해보면 된다. 여기서는 묶어서 한 가지 상황으로 처리한 것이다. 이 경우에는 아래의 그림과 같이 left rotate를 시켜주면 된다. 

 

여기서 하얀색 노드는 이전의 색깔을 그대로 따라간다는 의미이다. 

 

case 4. 

이번에는 위와 반대로 r이 Black이고 L이 red인 경우이다. 이 경우에는 아래와 같이 rotate를 시켜준다. (s를 기준으로 하고 rotate를 시켜주는 것임)

하지만 위와 같이 변경하여도 x에 여전히 -1이 있는 것을 볼 수 있을 것이다. 하지만 이 경우에는 이제 rotate를 시켰으므로 case 3으로 이동할 수 있다는 것을 알 수 있다. case 3으로 가서 똑같이 한번 더 조정을 해주어야 한다.

 

case 5.

마지막 케이스다. 마지막 케이스는 s node가 red 인 경우이다. 이 경우에는 아래와 같이 조정하며 위의 케이스들 중의 하나로 다시 이동하게 된다. 

 

---

3. Red-Black Tree 시간복잡도

검색의 시간복잡도: O(logn) 균형잡힌 트리이기 때문

삽입의 시간복잡도: O(logn) 계속 재귀적으로 호출하면서 루트까지 올라갈 수 있기 때문

삭제의 시간복잡도: O(logn) 계속 재귀적으로 호출하면서 루트까지 올라갈 수 있기 때문

[백준] 1600번 말이 되고픈 원숭이 문제 BFS로 풀어보기

1. 문제

www.acmicpc.net/problem/1600

문제의 입력, 출력, 더 자세한 instruction은 위 백준 링크에서 확인하고 오늘은 1600번 풀이법에 대해 알아보도록 하자.

---

2. BFS 개념

대표적으로 BFS를 사용할 수 있는 문제이다.

https://www.programmingstory.com/2024/02/dfs-bfs.html

BFS에 대해 익숙하지 않다면 위의 개념을 먼저 보고 오는 것을 추천한다.

---

3. 풀이

BFS에 관한 전형적인 문제인데 하나 변형된 부분이 있다. 바로 k번만 특수하게 움직일 수 있다는 것이다. 우리는 그동안 BFS를 풀 때 2차원 배열을 사용하여 행의 좌표, 열의 좌표를 사용하였다. 하지만 이 경우에는 k번만 특수하게 움직일 수 있으니 그동안 얼만큼 움직였는지를 별도로 기록할 필요가 있다. 

 

따라서 이번에는 3차원 배열을 만들어야 한다. 그리고 이동할 수 있는 방향도 총 12가지로 늘어난다. 예전에는 4가지가 대부분이었는데 이번에는 k번 이하로 대각선 방향도 움직일 수 있는 자유가 주어진다.

 

그래서 이번에는 

static final int[] dx = {0,0,1,-1,-2,-1,1,2,2,1,-1,-2};
static final int[] dy = {1,-1,0,0,1,2,2,1,-1,-2,-2,-1};
static final int[] used = {0,0,0,0,1,1,1,1,1,1,1,1};

이런식으로 static 변수들을 가져온다. dx와 dy모두 이동할 수 있는 방향을 뜻하고 used 라는 배열은 대각선으로 이동할 경우에 k번 중에 1번을 쓰는 것이므로 이런 식으로 하나의 배열을 더 준비했다.

---

처음에는 모든 d 배열을 -1로 초기화를 한 뒤에 만약 해당 d 배열의 값이 -1이라면 아직 방문하지 않았다는 뜻이므로 +1을 해준다. 이 문제에서는 인자가 세개가 필요하다는 것을 알 수 있을 것이다. 대각선 방향으로 몇 번 움직였는지의 회수도 queue에 함께 넣어주고 이것이 문제에서 입력받은 횟수보다 작거나 같은지를 확인해주어야 한다. 

 

이후 이 문제의 답은 d[n-1][m-1][k] 에 있다고 생각하면 잘못된 것이다. 문제에서 분명히 k 이하라고 했기 때문에 우리는 k의 값을 0부터 k까지 모두 다 검사하면서 최소값을 찾아야 하는 것이다. 

3. 코드

 

import java.util.*;

public class Main{
     static final int[] dx = {0,0,1,-1,-2,-1,1,2,2,1,-1,-2};
    static final int[] dy = {1,-1,0,0,1,2,2,1,-1,-2,-2,-1};
    static final int[] used = {0,0,0,0,1,1,1,1,1,1,1,1};
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int l = sc.nextInt();
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] a = new int[n][m];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int[][][] d = new int[n][m][l+1];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                Arrays.fill(d[i][j],-1);
            }
        }
        Queue<Integer> q=new LinkedList<>();
        q.add(0); q.add(0); q.add(0);
        d[0][0][0]=0;
        while(!q.isEmpty()){
            int x=q.remove();
            int y=q.remove();
            int c=q.remove();
            for(int k=0; k<12; k++){
                int nx=x+dx[k];
                int ny=y+dy[k];
                int nc=c+used[k];
                if (nx>=0 && nx<n &&ny>=0 &&ny<m && nc<=l){
                    if (a[nx][ny]!=1){
                        if (d[nx][ny][nc]==-1){
                            d[nx][ny][nc]=d[x][y][c]+1;
                            q.add(nx);
                            q.add(ny);
                            q.add(nc);
                        }
                    }
                }
            }
        }
        int ans = -1;
        for (int i=0; i<=l; i++) {
            if (d[n-1][m-1][i] != -1){
                if (ans == -1 || ans > d[n-1][m-1][i]) {
                ans = d[n-1][m-1][i];
            }
            } 
            
        }
        System.out.print(ans);
    }
}

이렇게 변형문제가 있을 수 있으니 잘 연습해두자.

[백준] 17141번 연구소2 문제 BFS로 풀어보기

1. 문제

 www.acmicpc.net/problem/17141

자세한 문제의 사항은 위의 링크를 클릭하여 백준 사이트에서 확인해보자.

---

2. 풀이

먼저 이 문제에서는 바이러스를 최대 m개 놓을 수 있기 때문에 어떤 위치에 바이러스 m개를 배치할지를 결정해주어야 한다. 그러기 위해서 먼저 문제에서 2라고 표시된 부분에 바이러스를 놓을 수 있다고 했기 때문에 가능한 바이러스의 위치를 ArrayList에다 넣어주도록 하겠다 (나는 virus라는 이름의 ArrayList를 만들어주었다). 그런 다음에 2라고 표시된 부분은 벽이 아니므로 자유롭게 움직일 수 있기에, 다시 0으로 바꾸어준다. 이러면 바이러스 자리인지 빈칸 자리인지 구분이 되지 않지만 우리는 ArrayList에다 넣어주었기 때문에 문제가 없다. 

 

다음으로 m개의 바이러스 자리를 결정하기 위해서 재귀함수를 사용해준다.

static void recur(int index, int cnt) {
        if (index == virus.size()) { 
            if (cnt == m) {//m개를 다 결정한 경우 
                bfs();
            }
        } else {
            int x = virus.get(index).x;
            int y = virus.get(index).y;
            a[x][y] = 3;
            recur(index+1, cnt+1); //해당 배열의 위치에 바이러스를 놓기로 결정한 경우
            a[x][y] = 0;
            recur(index+1, cnt);//해당 배열의 위치에 바이러스를 놓지 않기로 결정한 경우
        }
    }

위와 같은 재귀함수를 만들어주었다. 이런 식으로 재귀함수로 바이러스 m개의 위치를 결정해준다. 만약 마지막 바이러스의 위치에 도착했는데 cnt가 m개라면 m개의 바이러스 위치를 모두 결정해준 것이니 bfs 함수를 호출해주면 된다. 

 

여기서 바이러스의 진짜 위치를 표시해주기 위해서 만약 해당 좌표에 바이러스가 놓인 것이라면 그 값을 3으로 바꾸어주는 추가 작업도 실시해준다.

---

이제 그러면 bfs 함수가 어떻게 구성되어있는지 보도록 하겠다. (variable이 헷갈린다면 먼저 이 글의 가장 하단의 전체 코드를 보고 오는 것이 더 이해가 빠를 수 있다 )

static void bfs() {
        for (int i=0; i<n; i++) {
            for(int j=0; j<n; j++){
                d[i][j]=-1;
            }
        }
        Queue<Pair> q = new LinkedList<>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 3) {
                    q.add(new Pair(i,j));
                    d[i][j] = 0;
                }
            }
        }
        while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (a[nx][ny] != 1 && d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1;
                        q.add(new Pair(nx, ny));
                    }
                }
            }
        }
        int cur = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] != 1) {
                    if (d[i][j] == -1) return;
                    if (cur < d[i][j]) cur = d[i][j];
                }
            }
        }
        if (ans == -1 || ans > cur) {
            ans = cur;
        }
    }

먼저 d라는 배열을 모두 -1로 초기화해준다. 그런 다음 바이러스의 위치를 모두 queue에다가 넣어준다. 만약 벽이 아니고 방문하지 않은 칸이라면 이를 다시 queue에 넣어두는 등 일반적으로 우리가 BFS를 구할 때 하는 행동을 해준다. 

 

그런 다음에 d의 최댓값을 찾는 것이 사실상 이 문제에서 구하고자 하는 값이다. 따라서 모든 배열의 칸을 돌면서 현재의 ans가 iteration에서 돌아서 나온 최댓값보다 작다면 이를 새로 update시키는 과정을 거친다. 

 

이렇게 모든 과정을 거치게 되면 우리는 문제에서 구하고자 하는 값을 얻을 수 있다. 아래는 Java로 구현한 전체 코드이다.

3. 코드

---

import java.util.*;
class Pair {
    int x, y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int[][] a;
    static int[][] d;
    static final int[] dx = {0,0,1,-1};
    static final int[] dy = {1,-1,0,0};
    static int n, m;
    static ArrayList<Pair> virus = new ArrayList<>();
    static int ans = -1;
    static void bfs() {
        for (int i=0; i<n; i++) {
            for(int j=0; j<n; j++){
                d[i][j]=-1;
            }
        }
        Queue<Pair> q = new LinkedList<>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 3) {
                    q.add(new Pair(i,j));
                    d[i][j] = 0;
                }
            }
        }
        while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (a[nx][ny] != 1 && d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1;
                        q.add(new Pair(nx, ny));
                    }
                }
            }
        }
        int cur = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] != 1) {
                    if (d[i][j] == -1) return;
                    if (cur < d[i][j]) cur = d[i][j];
                }
            }
        }
        if (ans == -1 || ans > cur) {
            ans = cur;
        }
    }
    static void recur(int index, int cnt) {
        if (index == virus.size()) {
            if (cnt == m) {
                bfs();
            }
        } else {
            int x = virus.get(index).x;
            int y = virus.get(index).y;
            a[x][y] = 3;
            recur(index+1, cnt+1);
            a[x][y] = 0;
            recur(index+1, cnt);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[n][n];
        d = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
                if (a[i][j] == 2) {
                    a[i][j] = 0;
                    virus.add(new Pair(i,j));
                }
            }
        }
        recur(0,0);
        System.out.println(ans);
    }
}

[백준] 2251번 물통문제 BFS로 풀어보기

1. 문제

1) 링크

www.acmicpc.net/problem/2251

더 자세한 문제의 제한은 위의 링크에 들어가서 확인해보자

 

---

2. 풀이

이 물통 문제는 처음에 어떻게 풀까 고민을 하다가 위 풀이를 보고 BFS로 풀면 된다는 것을 알게 되었다.

 

물통 초기상태

물통의 총합이 변하지 않는다는 것이 문제에서 가장 중요한 열쇠이다. 그러면 물통 자체는 3개가 있지만 두개만 우리는 미지수로 두고 나머지 하나는 총합에서 빼는 식으로 구상하면 된다. 그리고 심지어 전체 합은 문제 시작 때 주어져있기 때문에 (2번 물통 양이 처음에는 sum이다) 매우 편하게 구할 수 있다.

 

그런 다음에 처음 물통 0과 물통 1은 0,0으로 시작하니 이들을 queue에 넣어주고 여기서부터 물통에 물을 옮겨담을 수 있는 모든 조합을 시도해보는 것이다. 

 

순열로 해도 되지만 이렇게 6개밖에 되지 않는 것은 그냥 배열로 from, to 해서 여섯가지를 모두 시도해보는 것이 간단하다. 

그리고 이 문제에서 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다고 했으므로 우선 다른 물통에 물을 다 부어놓고 이것이 용량을 초과하게 되면 다시 원래 물통에 넘친 만큼 부어준다는 식으로 구현을 하면 될 것 같다. 

그러면 비록 넘칠 때까지 부었어도 넘친 부분을 원상복구시켜주면서 물통이 가득찰 때까지만 부은 것이 되기 때문이다. 

 

그리고 제한이 200밖에 되지 않기 때문에 200까지 배열의 용량을 넉넉히 만들어 구해주면 된다.

 

Pair라는 class를 만들어도 되지만 나는 그것이 번거로워서 그냥 0번째 물통 값 넣어주고 1번째 물통 값 넣어주고 이런 식으로 구현했다. 전혀 문제 없는 방식이고 대신 queue에서 뺄 때도 두개를 다 빼주어야 한다.

 

3. 코드 

import java.util.*;

public class Main{
    final static int to[]={0,0,1,1,2,2};
    final static int from[]={1,2,0,2,0,1};
    public static void main(String[] arg){
        Scanner sc=new Scanner(System.in);
        int water[]=new int [3];
        for(int i=0; i<3; i++){
            water[i]=sc.nextInt();
        }
        int sum=water[2];
        boolean check[][]=new boolean[201][201];
        boolean ans[]=new boolean[201];
        Queue <Integer> q= new LinkedList<>();
        q.add(0);
        q.add(0);
        check[0][0]=true;
        ans[water[2]]=true;
        while(!q.isEmpty()){
            int cur[]=new int [3];
            cur[0]=q.remove();
            cur[1]=q.remove();
            cur[2]=sum-cur[0]-cur[1];
            for(int k=0; k<6; k++){
                int next[]={cur[0], cur[1], cur[2]};
                next[to[k]]+=next[from[k]];
                next[from[k]]=0;
                if (next[to[k]]>=water[to[k]]){
                    next[from[k]]=next[to[k]]-water[to[k]];
                    next[to[k]]=water[to[k]];
                }
                if (!check[next[0]][next[1]]){
                    check[next[0]][next[1]]=true;
                    q.add(next[0]);
                    q.add(next[1]);
                    if (next[0]==0){
                        ans[next[2]]=true;
                    }
                }
            }
        }
        for(int i=0; i<=water[2]; i++){
            if (ans[i]){
                  System.out.print(i + " ");
            }
        }
        System.out.println();
    }
}

여기서 check라는 배열은 0번째 물통 값, 1번째 물통 값의 조합이 예전에 나온 조합임을 확인하는 boolean 배열이고 ans 배열은 문제의 조건을 만족시키는지 확인하는 배열이다. 

 

이런식으로 구하면 문제에서 요구하는 조건은 ans 배열을 0부터 2번 물통 최대 값(sum)까지 따라가면서 true인 값을 적어주면 된다.

[백준] 16638번 괄호 추가하기 2 비트마스크로 풀어보기

1. 문제

1) 링크

www.acmicpc.net/problem/16638

2) 문제

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계산 해야 한다. 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 41이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 (3+8)×7-(9×2)와 같이 추가했으면, 식의 결과는 59가 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

3) 입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

4) 출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

---

2. 풀이

더 자세한 입출력 예시는 위 백준 링크에서 확인할 수 있다. 

이 문제는 먼저 Class를 하나 더 만들어주는 것이 편하다. class Calc를 하나 만들어주고 instance로 num과 op를 가지고 있도록 만들어준다. 여기서 op는 operator의 약자로 숫자면 0, 더하기면 1, 빼기면 2, 곱하기면 3을 가지게 만들어준다. 

 

즉 아래와 같은 형태인 것이다.

class Calc{
    int num, op;
    Calc(int num, int op) {
        this.num = num;
        this.op = op;
    }
}

그런 다음에 비트마스크를 활용하여 괄호가 올 수 있는 모든 경우를 체크할 것인데, 이 문제는 괄호 안에 하나의 연산자밖에 존재하지 않고 중첩이 불가능하므로 오히려 쉬운 문제이다. 연산자의 개수는 (n-1)/2개이므로 연산자의 개수를 기준으로 비트마스크를 해주면 된다. 즉 for문의 형태가 아래와 같은 식인 것이다.

int m = (n-1)/2; //연산자의 개수
for(int i=0; i<(1<<m); i++){
            boolean possible = true;
            for (int j=0; j<m-1; j++) {
                if ((i&(1<<j)) > 0 && (i&(1<<(j+1))) > 0) {
                    possible = false; //중첩 괄호 확인
                }
            }
            if (!possible) continue;
            
            }

이런식으로 for문이 돌면 중첩괄호가 아닌 모든 괄호의 경우를 체크할 수 있고 이제는 괄호가 있는 경우를 먼저 계산해준다. 이 문제는 순서가 괄호가 있는 수 먼저 계산 -> 곱하기 먼저 계산 -> 나머지 계산 이런 식으로 진행되어야 한다. 

 

괄호를 먼저 계산하면, 원래 있는 수 배열이 훼손될 수 있기 때문에 tmp라는 새로운 배열을 하나 더 만들어주고 괄호를 계산해준다. 아래 코드는 괄호를 계산하는 부분의 코드이다.

Calc[] tmp=new Calc[n]; //tmp 배열에 옮기기
            for (int j=0; j<n; j++) {
                tmp[j] = new Calc(a[j].num, a[j].op);
            }
            for(int j=0; j<m; j++){
                if ((i&(1<<j))>0){ //괄호가 있으면 
                    int k=2*j+1; //실제 괄호의 위치
                     if (tmp[k].op == 1) { //더하기
                         tmp[k-1].num += tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    } else if (tmp[k].op == 2) { //빼기
                        tmp[k-1].num -= tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    } else if (tmp[k].op == 3) { //곱하기
                        tmp[k-1].num *= tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    }
                }
            }

다음에 *, +, -을 더 계산해야 하기 때문에 괄호로 이미 계산한 연산자의 경우 op의 값으로 -1을 가지게 업데이트 시켜주어 다음번 계산 시에 고려하지 않게 한다. 

 

이렇게 되었다면 괄호 부분의 숫자가 다 계산이 된 것이다. 이제 곱하기 부분을 먼저 계산해주고, 그 다음에는 순차적으로 하나씩 계산해주어서 최댓값을 찾아주면 된다. 

 

---

3. 코드

이 모든 것을 종합한 전체 Java code는 아래와 같다.

import java.util.*;
class Calc{
    int num, op;
    Calc(int num, int op) {
        this.num = num;
        this.op = op;
    }
}
public class Main{
    public static void main(String[] args){
          Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        Calc[] a = new Calc[n];
         for (int i=0; i<n; i++) {
            if (i%2 == 0) {
                a[i] = new Calc(s.charAt(i)-'0', 0);
            } else {
                int op = 1; //+일 경우
                if (s.charAt(i) == '-') {
                    op = 2;
                } else if (s.charAt(i) == '*') {
                    op = 3;
                }
                a[i] = new Calc(0, op);
            }
        }
        int m = (n-1)/2; //연산자의 개수
        int ans = -2147483648; //가장 최소값
        for(int i=0; i<(1<<m); i++){
            boolean possible = true;
            for (int j=0; j<m-1; j++) {
                if ((i&(1<<j)) > 0 && (i&(1<<(j+1))) > 0) {
                    possible = false; //중첩 괄호 확인
                }
            }
            if (!possible) continue;
            Calc[] tmp=new Calc[n]; //tmp 배열에 옮기기
            for (int j=0; j<n; j++) {
                tmp[j] = new Calc(a[j].num, a[j].op);
            }
            for(int j=0; j<m; j++){
                if ((i&(1<<j))>0){ //괄호가 있으면 
                    int k=2*j+1; //실제 괄호의 위치
                     if (tmp[k].op == 1) { //더하기
                         tmp[k-1].num += tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    } else if (tmp[k].op == 2) { //빼기
                        tmp[k-1].num -= tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    } else if (tmp[k].op == 3) { //곱하기
                        tmp[k-1].num *= tmp[k+1].num;
                        tmp[k].op = -1;
                        tmp[k+1].num = 0;
                    }
                }
            }
            //괄호 계산 완료
            ArrayList<Calc> c=new ArrayList<>();
            for(int j=0; j<n; j++){
                if (j%2==0){ //숫자일 경우
                    c.add(tmp[j]);
                }else if (tmp[j].op==-1){
                 j++; //이미 괄호로 처리한 것
                }
                    else{
                    //우선 곱하기만 먼저 계산
                    if (tmp[j].op==3){
                        int num=c.get(c.size()-1).num* tmp[j+1].num;
                        c.remove(c.size()-1);
                        c.add(new Calc(num, 0));
                        j += 1;
                    }
                        else{
                            c.add(tmp[j]);
                        }
                }
            }
            Calc b[] = c.toArray(new Calc[c.size()]);
            int m2 = (b.length-1)/2;
            int val = b[0].num;
            for (int j=0; j<m2; j++) {
                int k = 2*j+1;
                if (b[k].op == 1) {
                    val += b[k+1].num;
                } else if (b[k].op == 2) {
                    val -= b[k+1].num;
                } else if (b[k].op == 3) {
                    val *= b[k+1].num;
                }
            }
            if (ans < val) {
                ans = val;
            }
        }
          System.out.println(ans);
    }
}

조금 긴 코드이지만 하나씩 이해해보면 어려움이 없을 것이다. 

[유니온 파인드] union find 경로 압축

1. union find 경로 압축

Union Find에서 Find 를 할 때 루트가 가장 최 상단에 있다면 시간복잡도가 O(N) 이 나올수가 있기 때문에 굉장히 느리다. 

 

이런 문제점을 해결하기 위해서 우리는 경로 압축이라는 방법을 사용할 수 있다. 

 

부모 루트를 계속 연결시키는 것이 아니라 최상단의 노드를 부모로 정하는 것이다. 이렇게 구현하게 되면 트리의 모양은 바뀌지만 우리가 구현하려고 하는 알고리즘에는 전혀 지장을 주지 않는다. 

 

2. Find 함수 수정 

그래서 우리는 Find 함수를 아래와 같이 조금 수정해주려고 한다.

 

int Find(int x) {
 if (x==parent[x]){
  return x; //루트일 경우 루트 노드 return
 }
 else{
   int y=Find (parent[x]);
   parent[x]=y; // 부모 노드를 최상단 루트로 바꾸어줌
   return y;
 }

}

위 사이트에 올라와있는 코드를 그대로 사용했는데 여기에 parent[x]=y 라는 코드가 추가된 것이다. 

 

이렇게 하면 우리는 O(N)이던 연산의 시간을 O(α(N)) 으로 확실히 줄일 수 있다.

[백준] 17088번 등차수열 변환 문제 풀어보기

1. 문제

www.acmicpc.net/problem/17088

문제는 위 링크에 들어가면 확인할 수 있다.

---

2. 풀이

이 문제는 등차수열의 성질을 활용하여 푸는 문제인데, 첫째항과 공차를 결정하여서 풀 수 있다.

 

가능한 첫째항은 a1, a1+1, a1-1 이렇게 세 가지가 가능하고, 마찬가지로 둘째항은 a2, a2+1, a2-1 이렇게 세 가지가 가능하다. 

 

그러면 총 3*3= 9가지의 경우의 수가 존재하고 첫째항과 공차가 결정되므로 모든 항에 대해서 가능한지 결정해보면 된다. 

3. 코드 

따라서 이를 코드로 구현한 것은 아래와 같다.

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        if (n == 1) {
            System.out.println(0);
            System.exit(0);
        }
        int ans=-1;
        for(int c1=-1;c1<=1; c1++ ){
            for(int c2=-1; c2<=1; c2++){
                int change=0;
                if (c1!=0) change++;
                if (c2!=0) change++;
                int a1=a[0]+c1;
                int d=a[1]+c2-a1;
                boolean ok=true;
                int cur=a1+d;
                for(int i=2; i<n; i++){
                    cur+=d;
                    if (a[i]==cur) continue;
                    else if (a[i]+1==cur || a[i]-1==cur){
                        change++;
                    }
                    else{
                        ok=false;
                        break;
                    }
                }
                if (ok) {
                    if (ans == -1 || ans > change) {
                        ans = change;
                    }
                }
            }
        }
         System.out.println(ans);
    }
}

 

여기서 change란 숫자를 변경하는 횟수를 뜻한다. 1 차이가 나면 1번 변경하면 가능하기 때문에 change를 1 증가시키는 것이다.

[백준] 16943번 숫자 재배치 문제 풀어보기

1. 문제

www.acmicpc.net/problem/16943

문제는 위 링크에 들어가면 확인할 수 있다.

---

2. 풀이

위 풀이에서 매번 순열을 하는 코드는 자바로 아래와 같이 구현할 수 있다.

 static boolean next_permutation(char[] a) {
        int i = a.length-1;
        while (i > 0 && a[i-1] >= a[i]) {
            i -= 1;
        }

        if (i <= 0) {
            return false;
        }

        int j = a.length-1;
        while (a[j] <= a[i-1]) {
            j -= 1;
        }

        char temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;

        j = a.length-1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }

자바에서 순열을 만드는 코드이다. 

---

또한 우리가 문자로 입력을 받았기 때문에 이를 다시 숫자로 돌리는 과정이 필요하다. 

C++의 경우에는 위의 풀이처럼 stoi를 써야 하지만 자바는 이를 또 구현해주는 과정이 필요하다. 

 

char 배열을 int로 바꿔주는 부분의 함수는 아래와 같다.

 

   static int toNum(char[] a) {
        int ans = 0;
        for (char ch : a) {
            ans = ans * 10 + (ch - '0');
        }
        return ans;
    }

---

따라서 매번 순열로 순서를 바꾸어주고 이를 다시 toNum 함수를 사용해서 숫자로 바꾸어주는 것이다. 그런 다음에 문제의 조건을 만족하는지 살펴보면 된다.

 

3. 코드 

전체 코드는 아래와 같다.

import java.util.*;
public class Main {
    static boolean next_permutation(char[] a) {
        int i = a.length-1;
        while (i > 0 && a[i-1] >= a[i]) {
            i -= 1;
        }

        if (i <= 0) {
            return false;
        }

        int j = a.length-1;
        while (a[j] <= a[i-1]) {
            j -= 1;
        }

        char temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;

        j = a.length-1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }
    static int toNum(char[] a) {
        int ans = 0;
        for (char ch : a) {
            ans = ans * 10 + (ch - '0');
        }
        return ans;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        char[] a = sc.next().toCharArray();
        int b = sc.nextInt();
        Arrays.sort(a);
        int ans = -1;
        do {
            int number = toNum(a);
            if (a[0] != '0' && number < b) {
                if (ans == -1 || ans < number) {
                    ans = number;
                }
            }
        } while (next_permutation(a));
        System.out.println(ans);
    }
}