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

✏️ 문제

주어진 방법대로 주사위를 굴렸을 때 윗면에 써진 숫자를 구하는 문제입니다. 자세한 규칙은 문제 설명을 참고해 주세요.

🧠 접근

주사위를 굴렸을 때 각 방향별로 눈의 위치 변화 계산

주사위가 각 방향별로 회전하면 값의 위치가 어떻게 바뀌는지를 메서드로 작성합니다. 규칙은 아래와 같습니다.

- 초기 위치의 인덱스를 0, 1, 2, 3, 4, 5라고 가정했을 때 회전 시 평면 상에서의 각 면은 아래와 같이 변화한다.
    - 동쪽 (direction = 1) → 3, 1, 0, 5, 4, 2
    - 서쪽 (direction = 2) → 2, 1, 5, 0, 4, 3
    - 북쪽 (direction = 3) → 4, 0, 2, 3, 5, 1
    - 남쪽 (direction = 4) → 1, 5, 2, 3, 0, 4

private static int[] rotateDice(int[] dice, int direction) {
    if (direction == 1) return new int[]{ dice[3], dice[1], dice[0], dice[5], dice[4], dice[2] };
    if (direction == 2) return new int[]{ dice[2], dice[1], dice[5], dice[0], dice[4], dice[3] };
    if (direction == 3) return new int[]{ dice[4], dice[0], dice[2], dice[3], dice[5], dice[1] };
    return new int[]{ dice[1], dice[5], dice[2], dice[3], dice[0], dice[4] };
}

주어진 방법대로 주사위를 굴리고 주사위 및 지도 평면상의 값 변경

이동하지 않으면 출력하지 않습니다.

for (int movement: move) {
    int nextX = currentDiceX + DX[movement];
    int nextY = currentDiceY + DY[movement];
    // 이동할 수 없는 경우 처리
    if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) continue;
    // 다음 주사위의 지도 상 위치
    currentDiceX = nextX;
    currentDiceY = nextY;            
    // 주사위를 다음 좌표로 이동
    dice = rotateDice(dice, movement);
    if (map[currentDiceY][currentDiceX] == 0) {
        map[currentDiceY][currentDiceX] = dice[5];
    } else {
        dice[5] = map[currentDiceY][currentDiceX];
        map[currentDiceY][currentDiceX] = 0;
    } 
    builder.append(dice[0] + "\n");
}

주의할 점

시작 좌표의 x, y 값에 주의합니다. 2차원 배열의 크기를 m열 n행으로 정의해야 지도 상에서의 x, y 값이 뒤집히지 않습니다. 그러나 m열 n행 (int[m][n]) 으로 처리할 경우 입력을 지도에 집어넣기가 다소 복잡해지므로 int[n][m]으로 처리하되 필요한 부분의 좌표를 뒤집어 처리하였습니다.

📄 전체 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    private final static int[] DX = { 0, 1, -1, 0, 0 };
    private final static int[] DY = { 0, 0, 0, -1, 1 };
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder builder = new StringBuilder();
        int[] nmxyk = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = nmxyk[0], m = nmxyk[1], y = nmxyk[2], x = nmxyk[3];
        int[][] map = new int[n][m];
        int[] dice = new int[6];
        // 지도 요소 입력
        for (int i = 0; i < n; i++) map[i] = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] move = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int currentDiceX = x, currentDiceY = y;

        for (int movement: move) {
            int nextX = currentDiceX + DX[movement];
            int nextY = currentDiceY + DY[movement];
            // 이동할 수 없는 경우 처리
            if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) continue;
            // 다음 주사위의 지도 상 위치
            currentDiceX = nextX;
            currentDiceY = nextY;            
            // 주사위를 다음 좌표로 이동
            dice = rotateDice(dice, movement);
            if (map[currentDiceY][currentDiceX] == 0) {
                map[currentDiceY][currentDiceX] = dice[5];
            } else {
                dice[5] = map[currentDiceY][currentDiceX];
                map[currentDiceY][currentDiceX] = 0;
            } 
            builder.append(dice[0] + "\n");
        }
        System.out.print(builder.toString());
    }

    private static int[] rotateDice(int[] dice, int direction) {
        if (direction == 1) return new int[]{ dice[3], dice[1], dice[0], dice[5], dice[4], dice[2] };
        if (direction == 2) return new int[]{ dice[2], dice[1], dice[5], dice[0], dice[4], dice[3] };
        if (direction == 3) return new int[]{ dice[4], dice[0], dice[2], dice[3], dice[5], dice[1] };
        return new int[]{ dice[1], dice[5], dice[2], dice[3], dice[0], dice[4] };
    }
}

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

✏️ 문제

지도 상에서 주어진 섬을 연결하는 최단 경로를 찾는 문제입니다.

🧠 접근

각 지도의 섬을 구분할 수 있도록 섬 번호 설정

다리를 놓기 시작해야 하는 위치는 간단히 정할 수 있지만, 현재 배열에는 0, 1만 들어 있으므로 다른 섬에 도달했는지를 판정할 수 없습니다.

그래서 아래와 같은 메서드를 사용해 배열의 내용을 '각 섬마다 다른 숫자를 가지도록' 변경해 줍니다.

private static void setIslandNumber(int[][] map, int x, int y, int size, int number) {
    isVisited = new boolean[size][size];
    map[x][y] = number;
    for (int i = 0; i < 4; i++) {
        int nextX = x + DX[i];
        int nextY = y + DY[i];
        if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue;
        if (map[nextX][nextY] == 1) setIslandNumber(map, nextX, nextY, size, number);
    }
}

예제의 지도 입력은 아래와 같이 바뀌어 저장되게 됩니다.

// before
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

// after
2 2 2 0 0 0 0 3 3 3
2 2 2 2 0 0 0 0 3 3
2 0 2 2 0 0 0 0 3 3
0 0 2 2 2 0 0 0 0 3
0 0 0 2 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 0
0 0 0 0 4 4 0 0 0 0
0 0 0 0 4 4 4 0 0 0
0 0 0 0 0 0 0 0 0 0

시작 위치를 결정

현재 판정하고자 하는 위치가 섬 안에 있고 주위 4방향을 탐색, 바다가 한 칸 이상 있다면 다리를 놓을 수 있는 위치입니다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (map[i][j] != 0) {
            boolean flag = false;
            for (int k = 0; k < 4; k++) {
                int nextX = i + DX[k];
                int nextY = j + DY[k];
                if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) continue;
                if (map[nextX][nextY] == 0) {
                    flag = true;
                    break;
                }      
            }
            if (flag) calculateDistance(map, i, j, n);
        }
    }
}

모든 시작 위치에 대해 시작점으로부터 거리를 구한 2차원 배열 작성

• 현재 시작한 섬의 번호라면 탐색할 필요가 없으니 더 이상 탐색하지 않습니다.
• map의 범위를 넘어선 경우에는 더 이상 탐색하지 않습니다.
• 그 외에는 모두 시작점으로부터의 거리를 구합니다.
• 작성된 2차원 배열에서 현재 섬 번호, 바다가 아닌 점까지의 거리 중 최솟값을 구합니다.

위 단계에서 구한 최솟값은 다른 섬에 도달한 이후에 한 칸을 더 세었으므로 1을 빼 주어야 합니다.

private static void calculateDistance(int[][] map, int x, int y, int size) {
        isVisited = new boolean[size][size];
        int startIslandNumber = map[x][y];
        distance[x][y] = 0;
        isVisited[x][y] = true;

        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        while (!queue.isEmpty()) {
            Point current = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = current.x + DX[i];
                int nextY = current.y + DY[i];
                if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue;
                if (isVisited[nextX][nextY]) continue;
                isVisited[nextX][nextY] = true;
                distance[nextX][nextY] = distance[current.x][current.y] + 1;
                queue.add(new Point(nextX, nextY));
            }
        }

        // 다른 섬이라면 해당 위치까지의 값 중 최솟값으로 갱신
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (map[i][j] != 0 && map[i][j] != startIslandNumber) 
                    minimumDistance = Math.min(minimumDistance, distance[i][j]);
            }
        }
    }

번외: 섬의 번호를 기입하는 방법

private static void setIslandNumber(int[][] map, int x, int y, int size, int number) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        map[x][y] = number;
        while (!queue.isEmpty()) {
            Point current = queue.poll();
            map[current.x][current.y] = number;
            for (int i = 0; i < 4; i++) {
                int nextX = current.x + DX[i];
                int nextY = current.y + DY[i];
                if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue;
                if (map[nextX][nextY] == 1) queue.add(new Point(nextX, nextY));   
            }
        }
    }
}

섬의 번호를 기입하는 과정을 너비 우선 탐색(BFS)으로 작성하게 될 경우 섬의 크기가 클 경우 큐에 좌표 정보가 계속 쌓여 메모리를 매우 많이 사용하게 됩니다.

가령, Java에서 아래 코드와 같이 class를 생성하고 해당 인스턴스를 계속 사용한다면 메모리 제한을 넘을 위험이 있으니 섬의 번호를 매길 때에는 깊이 우선 탐색(DFS)를 사용하는 것을 고려해 보시기 바랍니다.

아래 코드에서 setIslandNumber()를 BFS로 작성했을 때에는 메모리 초과 오류를, DFS로 변경 이후에는 AC를 받았습니다.

📄 전체 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    private final static int[] DX = { 1, 0, -1, 0 };
    private final static int[] DY = { 0, -1, 0, 1 };
    private static int minimumDistance = Integer.MAX_VALUE;
    private static int[][] distance;
    private static boolean[][] isVisited;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) map[i] = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        distance = new int[n][n];
        int currentNumber = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1) {
                    setIslandNumber(map, i, j, n, currentNumber);
                    currentNumber += 1;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] != 0) {
                    boolean flag = false;
                    for (int k = 0; k < 4; k++) {
                        int nextX = i + DX[k];
                        int nextY = j + DY[k];
                        if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) continue;
                        if (map[nextX][nextY] == 0) {
                            flag = true;
                            break;
                        }      
                    }
                    if (flag) calculateDistance(map, i, j, n);
                }
            }
        }
        System.out.print(minimumDistance - 1);
    }

    /**
     * 섬에 번호를 매긴다.
     * @param map
     * @param x
     * @param y
     * @param size
     * @param number
     */
    private static void setIslandNumber(int[][] map, int x, int y, int size, int number) {
        isVisited = new boolean[size][size];
        map[x][y] = number;
        for (int i = 0; i < 4; i++) {
            int nextX = x + DX[i];
            int nextY = y + DY[i];
            if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue;
            if (map[nextX][nextY] == 1) setIslandNumber(map, nextX, nextY, size, number);
        }
    }

    private static void calculateDistance(int[][] map, int x, int y, int size) {
        isVisited = new boolean[size][size];
        int startIslandNumber = map[x][y];
        distance[x][y] = 0;
        isVisited[x][y] = true;

        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        while (!queue.isEmpty()) {
            Point current = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = current.x + DX[i];
                int nextY = current.y + DY[i];
                if (nextX < 0 || nextX >= size || nextY < 0 || nextY >= size) continue;
                if (isVisited[nextX][nextY]) continue;
                isVisited[nextX][nextY] = true;
                distance[nextX][nextY] = distance[current.x][current.y] + 1;
                queue.add(new Point(nextX, nextY));
            }
        }

        // 다른 섬이라면 해당 위치까지의 값 중 최솟값으로 갱신
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (map[i][j] != 0 && map[i][j] != startIslandNumber) 
                    minimumDistance = Math.min(minimumDistance, distance[i][j]);
            }
        }
    }

}

class Point {
    public int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

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

✏️ 문제

비밀번호 자릿수가 주어졌을 때 사용 가능한 모든 비밀번호 중 '비밀번호에 들어갈 수'가 모두 포함된 비밀번호의 개수를 구하는 문제입니다.

🧠 접근

기초적인 브루트포스 문제입니다.

모든 가짓수를 찾은 뒤 숫자 포함 판정

아래와 같이 구합니다. 정해진 자릿수가 되면 선견지명으로 알게 된 비밀번호의 자리가 포함되어 있는지 판정합니다.

private static void dfs(int depth, int target, int[] required, Integer[] result) {
        if (depth == target) {
            for (int i = 0; i < required.length; i++) 
                if (!Arrays.asList(result).contains(required[i]))
                    return;
            count += 1;
            return;
        }
        for (int i = 0; i < 10; i++) {
            result[depth] = i;
            dfs(depth + 1, target, required, result);
        }
    }

결과를 출력

조건을 만족할 때마다 dfs()에서 1씩 더해 주었습니다. 이 count를 출력하면 됩니다.

dfs(0, n, required, result);
System.out.print(count);

예외 처리 추가

m이 0일 경우 (선견지명으로 알게 된 비밀번호가 없는 경우) 두 번째 줄이 입력되지 않습니다. 입력되지 않을 경우 비밀번호는 10진수이고 모든 경우가 가능한 경우이므로 자릿수가 $n$일 때 경우의 수는 $10^n$가 됩니다.

if (m == 0) {
    System.out.print((int) Math.pow(10, n));
    System.exit(0);
}

📄 전체 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    private static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int[] nm = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = nm[0], m = nm[1];
        if (m == 0) {
            System.out.print((int) Math.pow(10, n));
            System.exit(0);
        }
        int[] required = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Integer[] result = new Integer[n];
        dfs(0, n, required, result);
        System.out.print(count);
    }

    private static void dfs(int depth, int target, int[] required, Integer[] result) {
        if (depth == target) {
            for (int i = 0; i < required.length; i++) 
                if (!Arrays.asList(result).contains(required[i]))
                    return;
            count += 1;
            return;
        }
        for (int i = 0; i < 10; i++) {
            result[depth] = i;
            dfs(depth + 1, target, required, result);
        }
    }
}

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

✏️ 문제

지도의 크기와 시작점, 갈 수 있는 위치, 갈 수 없는 위치가 주어졌을 때 시작점으로부터의 거리를 출력하는 문제입니다.

🧠 접근

기초적인 너비 우선 탐색 문제입니다. 각 위치로 가는 거리가 최소여야 하므로 너비 우선 탐색으로 접근할 수 있습니다.

지도 입력 및 시작점 찾기

시작점은 입력받을 때 찾을 수 있습니다.

map = new int[n][m];
distance = new int[n][m];
isVisited = new boolean[n][m];

for (int i = 0; i < n; i++) {
    map[i] = Arrays.stream(reader.readLine().split(" "))
                                 .mapToInt(Integer::parseInt)
                                 .toArray(); // 지도를 작성
    if (!isStartChecked)  // 시작점이 체크되지 않았을 때에만 각 행에 대해 체크
        for (int j = 0; j < m; j++) 
            if (map[i][j] == 2) {
                isStartChecked = true;
                startX = i;
                startY = j;
                break;
            }
}

구한 시작점으로 너비 우선 탐색 수행

시작점을 기준으로 너비 우선 탐색을 수행합니다. distance 배열에 시작점으로부터의 거리를 작성하게 됩니다.

private final static int[] DX = { 1, 0, -1, 0 };
private final static int[] DY = { 0, -1, 0, 1 };

private static void bfs(int x, int y) {
    Queue<Point> queue = new LinkedList<>();
    queue.add(new Point(x, y));
    isVisited[x][y] = true; // 시작점 방문

    while (!queue.isEmpty()) {
        Point current = queue.poll();

        for (int i = 0; i < 4; i++) {
            int nextX = current.x + DX[i];
            int nextY = current.y + DY[i];

            if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) continue;
            if (map[nextX][nextY] == 0) continue; // 방문 불가능한 곳
            if (isVisited[nextX][nextY]) continue; // 이미 방문한 곳

            queue.add(new Point(nextX, nextY));
            distance[nextX][nextY] = distance[current.x][current.y] + 1; // 거리는 이전 지점으로부터 +1
            isVisited[nextX][nextY] = true;
        }
    }
}

거리를 출력

구해진 distance 배열을 이용하여 거리를 출력합니다. 방문 가능한 지점인데 벽으로 막혀 갈 수 없는 곳은 map 배열에서 1, 방문여부는 false이므로 해당 위치만 -1을 출력하도록 처리합니다.

StringBuilder builder = new StringBuilder();

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) 
        if (!isVisited[i][j] && map[i][j] == 1)
            builder.append(-1 + " ");
        else 
            builder.append(distance[i][j] + " ");
    builder.append("\n");
}

System.out.print(builder.toString());

문제가 모두 해결되었습니다.

📄 전체 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    private final static int[] DX = { 1, 0, -1, 0 };
    private final static int[] DY = { 0, -1, 0, 1 };
    private static int[][] map, distance;
    private static int m, n;
    private static boolean[][] isVisited;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder builder = new StringBuilder();
        boolean isStartChecked = false;
        String[] size = reader.readLine().split(" ");
        n = Integer.parseInt(size[0]);
        m = Integer.parseInt(size[1]);
        int startX = -1, startY = -1;

        map = new int[n][m];
        distance = new int[n][m];
        isVisited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            map[i] = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            if (!isStartChecked) 
                for (int j = 0; j < m; j++) 
                    if (map[i][j] == 2) {
                        isStartChecked = true;
                        startX = i;
                        startY = j;
                        break;
                    }
        }

        bfs(startX, startY);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) 
                if (!isVisited[i][j] && map[i][j] == 1)
                    builder.append(-1 + " ");
                else 
                    builder.append(distance[i][j] + " ");
            builder.append("\n");
        }

        System.out.print(builder.toString());
    }

    private static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        isVisited[x][y] = true;

        while (!queue.isEmpty()) {
            Point current = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = current.x + DX[i];
                int nextY = current.y + DY[i];

                if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) continue;
                if (map[nextX][nextY] == 0) continue;
                if (isVisited[nextX][nextY]) continue;

                queue.add(new Point(nextX, nextY));
                distance[nextX][nextY] = distance[current.x][current.y] + 1;
                isVisited[nextX][nextY] = true;
            }
        }
    }
}

class Point {
    public int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

？ 여담

무식할 정도로 큰 크기의 배열을 순회하는 방법인 만큼 소요시간이 길 수밖에 없었지만 800ms는 너무 큰 소요시간이었습니다. 소요 시간을 줄일 방법을 찾으면 추가 포스팅하겠습니다.

읽어 주셔서 감사합니다.

기존에 JavaScript 기반으로 작성된 React 프로젝트를 TypeScript로 변환하는 과정과 그 과정에서 발생한 에러를 해결하는 과정을 다루도록 하겠습니다.

✏️ 과정 1: 웹팩이 JS 대신 TS를 로딩하도록 설정

CRA(Create-react-app)를 사용한 경우와 사용하지 않은 경우로 분리하여 설명하겠습니다.

with CRA

CRA를 사용하신다면 프로젝트를 TypeScript로 다시 생성하면 됩니다.

npx create-react-app "path" --typescript

그리고 기존 컴포넌트를 새 프로젝트의 src로 옮기고 과정 2를 진행합니다.

without CRA

1. 우선 기존 프로젝트에 TypeScript를 추가합니다.

   yarn add typescript @types/node @types/react @types/react-dom
   yarn add -D @babel/preset-typescript ts-loader

2. babel.config.js에 TypeScript 프리셋을 추가합니다.

   module.exports = {
   presets: [
    '@babel/preset-react',
    '@babel/preset-env',
    '@babel/preset-typescript',
   ],
   };

3. webpack.config.js에서 ts 파일을 로드하도록 설정을 변경합니다. 진입점을 꼭 바꿔 주어야 합니다.

   {...}
   

module.exports = { {...}, entry: './src/index.tsx', resolve: { extensions: ['*', '.ts', '.tsx', '.js'], }, module: { rules: [ { test: /.tsx?$/, use: 'ts-loader', exclude: /node_modules/, }, {...} ], } };

4. tsconfig.json을 추가합니다.
또는 Google TypeScript Style을 이용할 수도 있습니다.
```bash
tsc init # TypeScript 기본
npx gts init # Google style

✏️ 과정 2: 모든 js, jsx 파일을 ts, tsx 확장자로 변경

JSX 문법을 포함하는 JS 파일은 tsx, 일반 JS 파일은 ts 확장자로 모두 바꿉니다. 과정을 완료하면 위와 같은 구조가 됩니다. 사진이 너무 길쭉해져 디렉터리를 닫아 놓았을 뿐 하위 디렉터리의 모든 파일도 변경하여야 합니다.

✏️ 과정 3: 각 파일에서 발생하는 Type 에러를 모두 해결

가장 시간이 오래 걸리며 프로젝트 규모에 따라 영겁의 세월이 걸릴 수도 있는 과정입니다.

아래는 TypeScript에서 기본적으로 요구하는 사항 외에 React 또는 연관 라이브러리에 의해 발생하거나 잘 알려진 에러에 대한 해결 방법입니다.

Argument of type 'HTMLElement | null' is not assignable to parameter of type 'Element | DocumentFragment'

💩 에러가 생기는 코드

const container = document.getElementById('root');
const root = createRoot(container); // error!

React 루트 엘리먼트를 만들 때 container가 null일 수 있어 발생하는 문제입니다. 해당 container가 null일 때에 대해 예외 처리를 해 줍니다. 혹은 타입 단언을 해 주셔도 됩니다.

✅ 수정 결과

const container = document.getElementById('root');
if (!container) throw new Error('Failed to find root element');
const root = createRoot(container);

Binding element implicitly has an 'any' type

💩 에러가 생기는 코드

const MyComponent = ({ foo }) => {
  return <div>{foo}</div>;
}; // error!

React 함수형 컴포넌트의 인자 타입이 지정되지 않아 발생하는 문제입니다. type을 지정합니다.

✅ 수정 결과

type MyComponentProps = {
  foo?: string;
};

const MyComponent = ({ foo }: MyComponentProps) => {
  return <div>{foo}</div>;
}

Module can only be default-imported using the 'esModuleInterop' flag

💩 에러가 생기는 코드

import React from 'react'; // error!

CommonJS 모듈을 ES6 모듈 코드베이스로 가져오려 할 때 발생하는 문제입니다. Default named import를 다음과 같이 변경합니다.

✅ 수정 결과

import * as React from 'react';

No overload matches this call: useRef()

💩 에러가 생기는 코드

const ref = useRef(); // error!

useRef에 맞는 정의가 오버로딩되어 있지 않아 발생하는 문제입니다. 이 정의에 대해 잘 설명해 주신 포스팅이 있습니다.

✅ 수정 결과

const ref = useRef() as React.MutableRefObject<HTMLDivElement>;

No overload matches this call: styled-components

💩 에러가 생기는 코드

const StyledAppbar = styled.div`
  ${(props) =>
    props.left &&
    css`
      {...}
    `}
  ${(props) =>
    props.right &&
    css`
      {...}
    `}
`; // error!

props를 사용 중인 경우 해당 프로퍼티에 맞는 인터페이스가 없어 발생하는 문제입니다. 해당 컴포넌트에 맞는 인터페이스를 생성합니다.

✅ 수정 결과

interface AppbarInterface {
  left?: boolean;
  right?: boolean;
}
const StyledAppbar = styled.div<AppbarInterface>`
  ${(props) =>
    props.left &&
    css`
      {...}
    `}
  ${(props) =>
    props.right &&
    css`
      {...}
    `}
`;

📚 마치며

이외에도 적지 않은 TS 에러를 마주칠 수 있습니다. 하지만 그리 걱정하지는 않아도 될 것이, 여러분이 겪었던 에러는 전세계의 누군가는 똑같이 겪었으며 해결 방법도 어딘가에는 올라와 있습니다. 우리의 친구인 Stackoverflow에도요.

부족한 글 읽어 주셔서 감사합니다.

첫 Next.js 프로젝트로 개인 포트폴리오 웹 사이트를 개발할 때의 이야기입니다. window 크기를 사용해야 할 일이 있어 React에서 했던 것처럼 자연스럽게 window 사이즈 Hook을 만들어 사용하려 했는데...

웬걸, window가 없답니다.

왜 그럴까?

결론부터 말하면 클라이언트 사이드 렌더링과 서버 사이드 렌더링의 차이 때문이었습니다. Next.js는 페이지를 최초로 렌더링할 때 서버에서 렌더링하는데(SSR) 여기에는 window, document와 같은 브라우저 전역 객체가 없습니다. 해당 전역 객체는 클라이언트 사이드에서만 사용할 수 있기에 코드를 약간 수정해 주어야 합니다.

해결 방법 1: typeof

if (typeof window !== undefined) {...}

window 객체가 있는지 확인하는 기본적인 방법입니다.

해결 방법 2: useEffect (componentDidMount)

const windowInfo = useWindow(); // custom hook

useEffect(() => {
  ...
}), [windowInfo]);

클라이언트 렌더링 이후 동작하는 useEffect hook을 사용할 수 있습니다.

해결 방법 3: dynamic import

import dynamic from "next/dynamic";

const AppbarWithoutSSR = dynamic(() => import("./Appbar"), {
  ssr: false,
});

export default AppbarWithoutSSR;

브라우저 전역 객체를 이용해야 하는 컴포넌트를 클라이언트에서 렌더링하도록 강제하면 정상적으로 window 등을 사용할 수 있습니다.

마치며

필자는 최종적으로 3번을 사용했습니다. 1번이나 2번으로도 충분히 문제를 해결할 수 있지만 기왕 Next.js를 사용한 만큼 next스럽게(?) 해결하고 싶었습니다.

한편, next/dynamic은 앞서 사용한 CSR 강제뿐 아니라 React의 suspense와 조합하여 컴포넌트 로딩이 완료되기 전에 표시할 fallback도 지정할 수 있습니다. next/dynamic이 React.lazy의 확장이기 때문입니다.

부족한 글 읽어 주셔서 감사합니다.

주의: 이 내용은 필자가 JavaScript 개념을 리마인드하면서 작성한 것으로 정확하지 않은 정보가 있을 수 있습니다.

📚 어디에나 있지만 조금 특이한 그놈

배열은 어느 언어에서든 거의 빼놓지 않고 등장하는 기초적인 자료 구조입니다. 자바스크립트도 비슷하며, Array 라는 객체의 프로토타입을 통해 배열을 사용할 수 있습니다.

하지만 자바스크립트의 배열은 C-like 언어의 고정 크기 배열과는 미묘한 차이가 있습니다. 이런 차이는 어디에서 오는 것인지 배열을 이해하면서 알아보도록 합시다.

📄 배열

배열의 생성

자바스크립트에서 배열을 생성하는 방법은 크게 두 가지가 있습니다. 하나는 다른 언어에서도 보이는 리터럴, 다른 하나는 배열 생성자입니다.

배열 리터럴

const array = ['사과', '배', '감귤'];

다른 언어의 그것과 정말 비슷하지만 중괄호가 아닌(중괄호는 객체를 생성하는 괄호로 예약되어 있으니) 대괄호로 생성한다는 점이 그 차이입니다. 파이썬의 리스트를 생성하는 방법과 유사합니다.

생성자 함수 Array()

const foo = ('사과');
const bar = ('사과', '배', '감귤');

배열도 객체이기에 생성자 함수를 통해서도 만들 수 있습니다. 매개변수의 개수를 길이로 하는 배열을 생성하게 됩니다.

배열의 요소

객체에 동적으로 프로퍼티를 추가, 삭제할 수 있듯 배열에도 동적으로 요소를 추가, 삭제할 수 있습니다. 자바스크립트의 배열은 아무 위치에나 요소를 삽입, 삭제할 수 있습니다. 배열의 크기는 자동으로 확장됩니다.

const foo = ['사과', '배', '감귤'];
foo[5] = '수박'

위와 같은 코드를 실행하면 foo 배열에는 아래와 같이 요소가 들어 있게 됩니다.

['사과', '배', '감귤', undefined, undefined, '수박']

확장된 배열 사이의 빈 공간에는 실제로 원소가 위와 같이 들어있지는 않으며, 메모리 공간도 차지하지 않습니다. 해당 위치의 값을 꺼내려 하면 undefined가 나온다는 의미로 이해하시면 됩니다.

length 프로퍼티

앞서 설명한 자바스크립트 배열의 특수성 덕에 length가 가리키는 값도 조금 차이가 있습니다. 배열의 length는 배열 내 원소의 가장 큰 인덱스 + 1 입니다. 1을 더한 것은 인덱스가 0부터 시작하기 때문입니다.

length 프로퍼티는 명시적으로 값을 변경할 수도 있으며, length 값이 요소의 최대 인덱스보다 작아지면 변경된 length보다 인덱스가 큰 배열 요소는 삭제됩니다.

const foo = ['사과', '배', '감귤'];
foo.length = 2;
console.log(foo); // ['사과', '배']

배열의 프로퍼티

배열도 어쨌거나 Object.prototype를 상속받는 자바스크립트 객체이므로 배열의 요소와는 별개로 프로퍼티를 추가, 삭제할 수 있습니다.

const foo = ['사과', '배', '감귤'];
foo.name = 'fruits';
console.log(foo.name); // fruits

🧹 배열 표준 메소드

들어가기 전에, 불변성(Immutability)?

자바스크립트를 공부하다 보면 불변성(Immutability)가 자주 언급됩니다. 말 그대로 변하지 않는 것을 의미하는데, 원시 타입은 모두 불변이지만 객체는 그렇지 않습니다.

그런데 배열을 조작하는 메소드 중에는 특이하게도 불변성이 유지되는 메소드가 있습니다. 여기서는 배열의 불변성 유지 여부를 기준으로 각 메소드를 설명하겠습니다.

불변성이 정확히 무엇이고, 불변성을 유지하는 것이 중요한 이유에 대해서는 차후 별도의 포스트로 다루겠습니다. 대표적인 메소드만 정리했으며 이외에도 더 많은 배열 메소드가 있습니다.

Mutable methods

원본 배열을 수정하여 불변성이 유지되지 않는 배열 메소드입니다.

unshift / push

배열의 처음 / 마지막(length가 가리키는 위치)에 원소를 추가합니다.

const foo = ['사과', '배', '감귤'];
foo.unshift('바나나');
foo.push('수박');
console.log(foo); // [ '바나나', '사과', '배', '감귤', '수박' ]

shift / pop

배열의 처음 / 마지막 원소를 뺍니다.

const foo = ["사과", "배", "감귤"];
console.log(foo.pop()); // 감귤
console.log(foo.shift()); // 사과
console.log(foo); // [ '배' ]

fill

startIndex부터 endIndex 전까지 value로 배열을 채웁니다. length 값을 벗어난 인덱스에 대해서는 아무 작업도 하지 않습니다.

array.fill(value, startIndex, endIndex);

let foo = ["사과", "배", "감귤"];
foo = foo.fill("바나나", 0, 2);
console.log(foo); // [ '바나나', '바나나', '감귤' ]

reverse

배열의 순서를 반전합니다.

let foo = ["사과", "배", "감귤"];
foo = foo.reverse();
console.log(foo); // [ '감귤', '배', '사과' ]

sort

배열 요소를 정렬합니다. 함수의 반환값을 통해 정렬 순서를 결정합니다.

array.sort(function);

let foo = ["사과", "배", "감귤"];
foo = foo.sort();
console.log(foo); // [ '감귤', '배', '사과' ]

splice

배열의 특정 구간을 추출하거나 해당 구간에 요소를 추가합니다. 시작 인덱스로부터 길이가 count인 부분 배열(없으면 인덱스로부터 전체)를 추출하며, item을 시작 인덱스부터 차례로 삽입합니다(인자가 있으면).

array.splice(startIndex, count?, ...items?);

let foo = ["사과", "배", "감귤"];
console.log(foo.splice(1, 2, "수박", "멜론", "참외")); // [ '배', '감귤' ]
console.log(foo); // [ '사과', '수박', '멜론', '참외' ]

Immutable methods

불변성이 유지되는 배열 메소드입니다.

forEach

배열의 각 요소에 대해 콜백 함수를 실행합니다. 반환 값은 없습니다.

const foo = [1, 2, 3, 4, 5];
const bar = [];
foo.forEach((item) => bar.push(item));
console.log(bar); // [ 1, 2, 3, 4, 5 ]

map

배열의 각 요소에 대해 콜백 함수를 실행하고 반환 값을 모아 새로운 배열로 만듭니다.

const foo = [1, 2, 3, 4, 5];
const bar = foo.map((item) => item * 5);
console.log(bar); // [ 5, 10, 15, 20, 25 ]

filter

배열의 각 요소에 대해 콜백 함수를 실행하고 반환 값이 true인 값만 모아 새로운 배열로 만듭니다.

const foo = [1, 2, 3, 4, 5];
const bar = foo.filter((item) => item % 2 === 0);
console.log(bar); // [ 2, 4 ]

reduce

배열의 각 요소에 대해 누적 합계를 냅니다.

const foo = [1, 2, 3, 4, 5];
const bar = foo.reduce((a, b) => a + b);
console.log(bar); // 15

번외: 유사 배열 객체(array-like objects)?

배열을 제외한 자바스크립트의 객체에는 기본적으로 length 프로퍼티가 없습니다. 그런데 어떠한 방법으로든 객체에 length 프로퍼티가 추가되면 해당 객체는 유사 배열 객체로 기능하게 됩니다.

유사 배열 객체는 배열과 구조가 유사하나 map, forEach와 같은 배열 표준 메소드를 갖고 있지 않습니다.

대표적인 유사 배열 객체로는 Function.arguments가 있습니다.

✍️ 마치며

자바스크립트의 배열은 쓰는 방법만 안다면 매우 강력합니다. 특히 불변성을 유지하면서 배열을 수정하는 방법은 여러 곳에서 폭넓게 사용되니 다른 건 몰라도 불변성이 유지되는 map, filter, reduce, forEach 등의 메소드는 반복 숙달하는 것을 추천드립니다.

다음 포스트에서는 자바스크립트의 핵심이라고 할 수 있는 함수에 대해 다루겠습니다.

읽어 주셔서 감사합니다.

참고문헌

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array

정말 오랜만에 글을 쓰게 되었습니다. 이번에는 Babel과 세트로 등장하곤 하는 Webpack에 대해 알아보도록 하겠습니다.

웹팩은 의존성을 가진 여러 자바스크립트 모듈을 사전 지정된 규칙으로 합쳐 주는 번들러입니다. 그런데 모듈은 또 뭐고, 의존성은 또 뭐고, 번들링은 또 뭐란 말인가요? 대체 그런 게 왜 필요한 걸까요?

그냥 자바스크립트 쓰면 되는 거 아니야?

언제나 그렇듯 가능은 합니다. 그러나 자바스크립트를 HTML에서 바로 가져올 경우 필연적으로 스크립트는 전역 스코프를 건드리게 되어 전역 스코프의 오염을 피할 수 없습니다.

let a = 100;

const setNumber = function() {
  a = 50;
  console.log(a);
}

setNumber();
console.log(a);

이 때 setNumber() 의 console.log() 는 50을 출력하며 이는 자명합니다. 그런데 마지막 줄의 console.log() 는 무엇을 출력할까요?

출력은 100이 아닌 50입니다. 함수 스코프 내에서 a = 50 을 수행함으로써 전역 스코프의 a 의 값이 바뀌어 버린 것입니다.

미봉책, IIFE

전역 스코프가 오염되는 문제를 해결하기 위해 즉시실행 함수 표현식(IIFE, Immediately invoked function expression)가 도입되었습니다. 별도의 스코프를 사용함으로써 전역 스코프의 오염을 피하려는 시도였죠.

(() => {
  // execution
})();

하지만 이 방법도 한계는 있습니다. 스코프의 분리라는 목적에는 충실했지만 코드 상의 해당 위치에서 바로 실행되는 만큼 항상 우리의 의도대로 작동하게 하기가 어려웠습니다.

모듈화만 된다면 이 문제가 깔끔하게 해결될 텐데..

모듈이 나왔습니다. 그래서?

자바스크립트 파일을 모듈화하려는 시도는 여러 구현 명세를 만들어 냈습니다. 대표적으로 AMD, CommonJS, UMD가 있습니다.

여러 커뮤니티에서 각자의 구현 스펙을 제안하고 있었으나 ES6에서 모듈 시스템을 표준화함으로써 모듈을 사용할 수 있는 일관된 환경이 갖추어졌습니다.

하지만 현실은 항상 장밋빛이지는 않습니다.

ES module이 나오고부터도 몇 년이 지나서야 일부 브라우저가 지원하기 시작했고 현재는 거의 모든 현역 브라우저가 모듈을 지원하지만 브라우저가 모듈 여러 개를 나누어 요청하고 의존성이 있는 스크립트가 평가가 완료되기 전까지 해당 모듈의 평가가 중단(block)됩니다. 퍼포먼스가 중요한 웹 환경에선 정말 난감한 일입니다.

이 문제를 해결할 구세주가 등장했으니, 그 이름하야 웹팩입니다.

두 번째, 웹팩 (Webpack)

상술한 의존 관계에 있는 어려 모듈을 합쳐 주는(번들링이라고 합니다)하는 장치가 웹팩입니다. 즉 ES6을 지원하지 않는 구형 브라우저에 대응하기 위해 의존성을 갖는 모듈을 번들링하고, 번들링된 결과물을 Babel이 ES5 스펙으로 트랜스파일링(babel-loader)해 브라우저 호환성이 보장되는 스크립트로 만드는 것이죠. 번들링 조건에 따라 HTTP 요청 횟수가 줄어든다는 이점도 챙길 수 있습니다.

웹팩의 기본

웹팩은 앞서 설명했듯 의존성을 가진 여러 모듈을 번들링해 주는 장치입니다. 여기서의 설정을 조금씩 고쳐 자신의 입맛대로 번들링을 할 수 있습니다.

웹팩 설치

초기화를 해 준 뒤 웹팩 필수 의존성을 설치해 줍시다.

yarn init -y
yarn add webpack webpack-cli -D

src 폴더를 만든 뒤 웹팩이 처리할 진입점 파일 index.js과 합을 구하는 모듈 sum.js를 만들어 주세요.

index.js

import sum from "./sum";

console.log(sum(1, 2));

sum.js

const sum = (a, b) => a + b;

export default sum;

그리고 프로젝트 루트에 webpack.config.js 파일을 만들어 주세요. 이 파일이 웹팩이 어떻게 작동할지를 결정합니다.

모두 만들고 나면 위와 같은 구조가 됩니다. webpack.config.js 파일에는 아래와 같은 빈 객체를 export하도록 설정해 주세요. 이 객체에 내용을 채워서 웹팩의 작동 규칙을 정하게 됩니다.

module.exports = {}

웹팩 설정 객체에 들어가는 내용은 아래와 같습니다.

mode

모듈을 번들링하는 방법을 정의합니다.

• development 개발 모드입니다. dependencies와 함께 devDependencies까지 번들링됩니다.
• production 프로덕션 모드입니다. devDependencies는 번들링되지 않습니다.

module.exports = {
  mode: process.env.NODE_ENV === "development" ?
      "development" : "production",
};

entry

모듈 번들링을 시작하는 진입점입니다. 여기부터 의존 관계를 파악하여 번들링한다고 생각하면 됩니다. 진입점은 배열로 여러 개를 지정할 수도 있습니다.

module.exports = {
  entry: "./src/index.js",
};

output

번들링된 결과물을 내보낼 곳입니다. 기본값은 /dist에 JS 파일이 main.js, 나머지 파일이 /dist 안에 내보내어집니다.

module.exports = {
  output: {
    path: path.resolve(__dirname, "./build"),
    publicPath: "/",
    filename: "[name].[chunkhash].js",
  },
};

path

결과물이 내보내어질 경로입니다.

publicPath

정적 파일이 로드되는 경로입니다. CDN을 따로 두고 있을 경우 유용합니다.

filename

내보내어질 파일명입니다. 내보내어질 파일명은 지정된 템플릿을 사용하거나 수동 입력할 수 있습니다. 예시는 청크 이름과 청크 해시를 파일명에 붙인 것으로, 파일명을 지정하는 템플릿은 여기의 output.filename에서 확인할 수 있습니다.

module

로더와 플러그인, 개발 서버 관련 실습은 내용이 너무 길어지기에 별도의 포스트로 분리합니다.

그런데 웹팩은 조금 특이하게도 모든 파일을 모듈로 간주합니다. 대신 이런 파일을 웹팩이 직접 로딩할 수 있지는 않기에 로더를 통해 JS 코드로 로딩합니다.

module.exports = {
  module: {
    rules: [
      {
        test: /\.(js|jsx)$/,
        exclude: '/node_modules/',
        loader: 'babel-loader',
      },
      {
        test: /\.svg$/,
        use: ['@svgr/webpack'],
      },
      {
        test: /\.css$/,
        use: [MiniCssExtractPlugin.loader, 'css-loader'],
      },
      {
        test: /\.(png|jpg|jpeg|gif|ico)$/,
        exclude: /node_modules/,
        use: {
          loader: 'file-loader',
          options: {
            name: '[contenthash].[ext]',
          },
        },
      },
    ],
  }, 
}

module의 rules 배열에 각 규칙이 들어가 있습니다. 그럼 각 rule을 파헤쳐 봅시다.

test

규칙을 적용할 조건(정규식)입니다. 해당 조건에 맞는 파일을 로더가 처리하도록 합니다.

exclude

조건을 만족하지만 로더가 가져올 필요가 없는 특수 조건(정규식)입니다. 보통 Node.js 모듈이 저장되는 경로인 node_modules가 지정됩니다.

loader

조건을 만족할 때 사용할 로더가 하나 뿐이고 적용할 옵션이 없다면 use 대신 쓸 수 있습니다. 로더 이름을 문자열로 입력합니다.

use

조건을 만족할 때 사용할 로더입니다. 배열이며, 맨 뒤에서부터 역순으로 처리합니다.

use: [MiniCssExtractPlugin.loader, 'css-loader']

use (with options)

로더 옵션이 필요할 경우 객체로 입력합니다.

• loader : 사용할 로더입니다.
• option : 로더의 옵션입니다.

  use: {
      loader: 'file-loader',
      options: {
            name: '[contenthash].[ext]',
      },
  }

자주 쓰이는 로더는 아래와 같습니다.

css-loader

CSS 파일을 읽어들일 수 있게 해 줍니다.

style-loader

JS 파일로 변환된 CSS 코드를 HTML에 주입해 줍니다.

file-loader

웹팩 아웃풋에 파일을 옮겨 모듈로 사용할 수 있게 합니다. 주로 이미지 등의 에셋을 가져올 때 사용합니다.

url-loader

일정 크기 미만의 작은 이미지를 Data URI Scheme으로(Base64) 인코딩해 주는 로더입니다. 작은 크기의 반복적인 네트워크 요청을 줄여 성능 개선을 도모할 수 있습니다.

플러그인

플러그인은 번들된 결과물을 처리하는 장치입니다.

plugins: [
  new CleanWebpackPlugin(),
]

자주 쓰이는 플러그인은 아래와 같습니다.

BannerPlugin (웹팩 내장)

번들 결과물 상단에 주석으로 배너를 달아 줍니다.

DefinePlugin (웹팩 내장)

환경 변수 정보를 제공합니다. 기본적으로 NODE_ENV가 들어갑니다.

HtmlWebpackPlugin

진입점으로 설정한 JS 파일을 스크립트로 포함하는 HTML 파일 생성을 자동화합니다. 일종의 템플릿을 생성해 주는 플러그인입니다.

MiniCssExtractPlugin

결과물에서 CSS 파일을 분리해서 따로 만들어 줍니다. 성능상의 이점을 위한 플러그인입니다.

CleanWebpackPlugin

이전 빌드 결과물을 삭제하여 찌꺼기가 발생하지 않게 해 줍니다.

마치며

여기서 설명한 웹팩 옵션은 일부에 불과합니다. 언급한 것 이외에도 수많은 하위 옵션이 있으며 입맛에 따라 손볼 수 있습니다.

다음 포스트에서는 웹팩과 바벨을 함께 사용해 간단한 React 웹 앱을 만들어 봄으로써 각각의 사용법을 간략하게나마 알아보도록 하겠습니다.

읽어 주셔서 감사합니다.

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

✏️ 문제

주어진 조건 하에서 높이 c를 구하는 문제입니다.

🧠 접근

삼각형의 닮음 관계를 이용하여 해결할 수 있는 문제입니다.

문제의 그림을 도식화하면 아래와 같습니다.

높이를 구하는 지점 C를 기준으로 내린 수선의 발을 F라 하면 두 삼각형에서 닮음 관계를 찾을 수 있습니다.

• 삼각형 ABC와 AFE
• 삼각형 BAD와 BFE

이 때, 닮음 관계를 이용하여 아래 두 식을 도출할 수 있습니다.

$a_1=\frac{c(a_1+a_2)}{h_2}$, $a_2=\frac{c(a_1+a_2)}{h_1}$

선분 AB의 길이를 $a=a_1+a_2$라고 하면

$a=$$\frac{c(a_1+a_2)}{h_2}+\frac{c(a_1+a_2)}{h_1}=\frac{c(h_1+h_2)(a_1+a_2)}{h_1h_2}$

수식을 정리하면 $c(h_1+h_2)=h_1h_2$, 즉 $c=\frac{h_1h_2}{h_1+h_2}$이 됩니다.

마지막으로 피타고라스 정리에 의해 $h_1^2=x^2-a^2, h_2^2=y^2-a^2$이므로 두 값을 이용해 구하는 값 $c$의 오차 범위가 $10^{-3}$ 이내가 되도록 이분 탐색하면 됩니다.

while (right - left >= 0.001) {
    double width = (left + right) / 2;
    double h1 = Math.sqrt(Math.pow(x, 2) - Math.pow(width, 2));
    double h2 = Math.sqrt(Math.pow(y, 2) - Math.pow(width, 2));
    double res = (h1 * h2) / (h1 + h2);

    if (res >= c) left = width;
    else right = width;
}

위 과정을 수행한 뒤 오차 범위 안으로 들어온 이분 탐색의 두 피벗 값 중 하나를 출력하면 문제가 해결됩니다.

📄 전체 소스 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        double x = Double.parseDouble(input[0]);
        double y = Double.parseDouble(input[1]);
        double c = Double.parseDouble(input[2]);


        double left = 0, right = Math.min(x, y);

        while (right - left >= 0.001) {
            double width = (left + right) / 2;
            double h1 = Math.sqrt(Math.pow(x, 2) - Math.pow(width, 2));
            double h2 = Math.sqrt(Math.pow(y, 2) - Math.pow(width, 2));
            double res = (h1 * h2) / (h1 + h2);

            if (res >= c) left = width;
            else right = width;
        }
        System.out.println(String.format("%.3f", right));
    }
}

켈시어 Github 켈시어 웹 인터프리터 Github Web

🌁 배경

여느 토이 프로젝트가 그렇듯 처음부터 거창한 목표를 갖고 시작한 건 아니었다. 한 게임에서 등장하는 인물의 말투가 너무 웃겨서, 최근에 본 엄랭의 구조에서 착안해 그 인물의 어투를 모사한 언어를 만들겠다고 마음먹었다.

개발이라... 그런건가. 내 말투를 말이지.

❓ 켈시어 구현체 개발

개발 자체는 노베이스가 아니었던만큼 신속하게 진행됐다. 이렇게 빨라도 괜찮은거야? 라는 말이 나올 만큼. 마침 Node.js를 가장 많이 다루어 보기도 했고.

문자열을 정규표현식으로 처리하는 과정에서 한 번만 찾는 것이 아닌 전역 검색하는 방법을 습득한 건 덤이다.

• g 플래그는 문자열 전역에서(한번 찾는다고 중단하지 않음)
• i 플래그는 대소문자 구분 없이

export const checkOnlyDots = (statement) => 
    statement.replace(/\./gi, "").length > 0;

다만 한 가지 방법만으로는 원하는 형태로 문자열을 가공하기 힘들어 여러 함수를 순차적으로 돌렸는데, 덕분에 처리된 문자열이 올바른 형태인지 검증하는 로직이 덕지덕지 붙어 가독성을 떨어트렸다.

타입 체크만 좀 잘 되었어도... 하는 아쉬움이 남는다.

하지만 우리에게는 또 다른 문제가 남아 있었으니, 바로 배포였다.

배포

npm에 프로젝트를 게시해 보기는 처음이었다. 어쩌저찌 구글링 해가며 배포를 위한 준비를 다 마치고 npm link 로 로컬에서 실행해 보는데 자꾸 모듈이 없다고 한다.

분명 프로젝트 경로에 잘 들어있고 import/export 구문도 문제없는데 말이다. 이 문제는 정말 황당하고도 어이없게 해결되었는데, package.json의 files에 모듈이 있던 경로를 지정하지 않아서 발생한 문제였다.

{
  (...)
  "files": [
    "cli",
    "dist"
  ],
  (...)
}

이렇게 경로를 지정하고 나니 언제 그랬냐는 듯이 실행이 잘 되었고, 역사적인(?) 첫 npm 패키지 배포를 할 수 있게 되었다.

❗️ 켈시어 웹 인터프리터 개발

특정 인물의 어투를 모티브로 한 만큼 대화창 형태로 UI를 구성했다.

반응형 UI는 미디어 쿼리와 grid 레이아웃으로 금방 구현했지만 문제는 대화창이었다.

코드를 입력한 뒤 결과가 대화식으로 보여지는 만큼 스크롤을 맨 아래로 내려줄 필요가 있었는데, 분명 useRef로 DOM을 지정해준 뒤 해당 위치로 스크롤을 내렸는데도 어중간하게 내려오는 문제가 생겼다.

state가 변경되면 DOM 요소가 리렌더링되는데, 리렌더링이 완전히 되지 않은 상태에서 스크롤을 내렸기에 렌더링이 완료되지 않은 시점의 끝까지 스크롤링이 된 것이라는 추측을 할 수 있었다.

그래서 리렌더링이 끝난 뒤에 스크롤링이 이루어질 수 있도록 약간의 sleep을 주었다.

{
  (...)
  setLog(...);
  await sleep(100);
  conversationLog.current.scrollTop = conversationLog.current.scrollHeight;
}

React 차원에서 렌더링이 끝났는지 알 수 있는 방법이 분명 있을 것 같았지만 빠른 구현이 우선이었기에 이와 같은 임시방편을 사용했다. 언젠가는 고쳐야 할 기술 부채인 셈이다.

+ 추가

위에서 적용한 sleep 핵을 간단하게 해결했다. 렌더링이 끝난 후에 스크롤을 해야 한다는 점에 착안, useEffect() Hook을 사용하였다.

React의 생명주기 메소드에 대한 이해가 부족해 잘못된 코드를 작성했던 것.

// Scroll on re-render
useEffect(() => {
  conversationLog.current.scrollTop =
    conversationLog.current.scrollHeight;
}, [log]);

더 높은 Lighthouse 점수를 향해서

크롬 브라우저에 내장된 Lighthouse는 개발자 도구에 내장된 퍼포먼스 측정 도구로, 여기서 측정된 점수는 사용자 경험(UX)을 판단하는 지표가 된다. 점수를 올려보고자 아래와 같은 방법을 적용했다.

1. 네트워크 부하가 큰 웹 폰트에 대해 font-display: swap 적용

   폰트의 용량이 클 경우 font-display 속성을 기본값으로 두면 로딩이 완료될 때까지 해당 폰트를 사용하는 엘리먼트의 글자가 보이지 않게 된다. (정확히는 브라우저마다 기본값이 다르며, Chrome, Edge 기준이다.) 이 때 swap 옵션을 적용하면 로딩 전에는 현재 사용할 수 있는 내장 폰트를 사용하다가 로딩이 완료되면 해당 폰트로 바꾸게 된다. 로딩 전까진 필자가 기대한 레이아웃이 아니고 로딩 완료 시 Layout shift가 조금 생길 수는 있으나 사용자가 페이지와 더 일찍 상호작용할 수 있게 된다는 장점이 더 크다고 보았다.

2. 사용하지 않는 모듈 삭제 및 직접 구현

   • 마크다운 구현 초기 버전에서는 사용 설명의 마크다운을 표시하기 위해 @uiw/react-markdown-preview 라이브러리를 사용했다. 마크다운을 필자의 의도와 동일하게 보여주었지만 패키지가 꽤나 무거웠다. 그래서 해당 패키지는 보내주고 필요한 마크다운 요소만 직접 styled-components 로 구현하였다. 아래 코드는 구현한 마크다운 요소의 일부이다.

   • react-icons 를 @react-icons/all-files 으로 대체 분명히 번들 사이즈를 줄일 만큼 줄였다고 생각했는데 이상할 정도로 번들 크기가 컸다. 최적화 전 번들 크기는 1.36MB로 규모에 비해 말도 안 되게 큰 수치다. 번들 사이즈를 어떻게 줄일 수 있을지 고민하던 중, react-icons 가 사용하지 않는 아이콘까지 아이콘 그룹 전체를 import한다는 점에 착안해 필요한 것만 하나씩 import하는 방법을 찾았고 @react-icons/all-files 으로 모든 아이콘을 대체했다.

위 최적화 방법을 모두 적용하고 난 뒤 번들 크기는 370KB로 여전히 작지는 않지만 납득할 수 있는 수치로 내려왔다.

마지막으로 호스팅 중인 현 시점의 Lighthouse 점수를 공개한다.

간단한 웹 앱이긴 하지만 프론트엔드 개발을 시작한 후로 이런 점수는 처음 받아본다. 조금은 감격스럽다.

📚 마치며

다른 사이드 프로젝트를 진행하던 중 갑자기 꽂혀서 진행하게 된 토이 프로젝트였는데 흥미가 확 당겨 시작한 프로젝트였던 만큼 즐겁게 개발할 수 있었다.

한편 장기적으로는 이 웹 앱을 PWA로 구현할 생각이 있고 관련 리소스도 모두 준비해 두었지만 Service worker 구현에 애로사항이 꽃피어 다음 구현 목표로 조정했다. 진행하던 사이드 프로젝트가 마무리되는 대로 PWA 구현에 집중하지 않을까 싶다.

어제보다 더 나은 프론트엔드 개발자가 되기 위해 오늘도 달린다.

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

✏️ 문제

재귀로 구현된 피보나치 함수를 사용할 때 종료 조건 fibonacci(0)과 fibonacci(1)이 몇 번 반복되는지 찾는 문제입니다.

🧠 접근

언제나 그렇듯 한번 써 봅시다. 피보나치 수를 구하는 함수를 f(n) $(n \ge 0)$ 이라고 합시다.

f(0) 은 종료 조건이므로 f(0) 1회,f(1) 0회입니다. f(1) 은 종료 조건이므로 f(0) 0회,f(1) 1회입니다. f(2) 는 f(1)과 f(0) 을 호출하므로 각각 1회입니다. ... 이런 방법으로 반복하면 아래와 같이 호출 횟수를 확인할 수 있습니다.

f(0) 의 호출 횟수는 n = 0 일 때 1, n 이 1 이상일 때에는 f(n - 1) 이 되고, f(1) 의 호출 횟수는 아예 피보나치 수열을 따르고 있는 것이 보이죠.

따라서 피보나치 수열의 값을 미리 구해 놓고 위 조건에 따라 출력하면 됩니다.

// 피보나치 수열을 미리 구함
int[] fibonacci = new int[40 + 1];
fibonacci[1] = 1;
for (int i = 2; i <= 40; i++) 
    fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];

(...)
for (int i = 0; i < testCase; i++) {
    (...)
    int fZero, fOne;
    if (input == 0) {
        fZero = 1;
        fOne = 0;
    } else {
        fZero = fibonacci[input - 1];
        fOne = fibonacci[input];
    }
    (...)
}
(...)

문제가 전부 해결되었습니다.

📄 전체 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder builder = new StringBuilder();
        int[] fibonacci = new int[40 + 1];
        fibonacci[1] = 1;
        for (int i = 2; i <= 40; i++) 
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];

        int testCase = Integer.parseInt(reader.readLine());

        for (int i = 0; i < testCase; i++) {
            int input = Integer.parseInt(reader.readLine());
            int fZero, fOne;
            if (input == 0) {
                fZero = 1;
                fOne = 0;
            } else {
                fZero = fibonacci[input - 1];
                fOne = fibonacci[input];
            }
            builder.append(fZero + " " + fOne + "\n");
        } 
        System.out.print(builder.toString());
    }
}

주의: 본 포스트는 저자가 학습하면서 작성한 글이므로 잘못된 내용이 있을 수 있습니다. 지적과 제언은 언제든지 환영입니다.

✏️ 들어서며

중간 삽입, 삭제가 안 되는 선형 리스트

앞서 알아본 연결 리스트는 원소의 삽입, 삭제가 비교적 자유롭습니다. 찾는 위치까지 이동한 다음 작업을 수행해야 하지만 적어도 작업을 수행할 수는 있습니다.

이번에 알아볼 자료 구조인 선형 리스트는 연결 리스트와 다르게 삽입과 수정은 한쪽 또는 양쪽 끝에서만 가능합니다.

근데 이런 게 필요해?

그런데 이런 자료 구조가 왜 필요할까요? 중간 원소도 못 뽑고 앞뒤로만 접근해야 하는 자료 구조가 의미가 있을까요?

연결 리스트는 삽입과 삭제가 간편하지만 연산마다 링크를 재설정해야 하는 등 구현과 실제 연산이 복잡합니다. 반면 스택과 큐(덱도 포함합니다)은 맨 끝만 접근하면 되므로 구현이 매우 간단하고 빠릅니다.

그렇기에 선입선출(First-in-first-out, FIFO)이나 후입선출(Last-in-first-out, LIFO)이 필요한 상황에서 굳이 연결 리스트를 쓸 필요가 없습니다.

상황에 따라서 스택과 큐가 유리한 상황이 분명히 있으므로 우리는 이 상황을 파악하여 적절한 자료 구조를 선택, 사용하면 됩니다.

각 자료 구조에 대한 구현은 연결 리스트의 구현에서 일부 메서드를 제거하면 가능하므로 생략하였습니다.

스택 📚

스택은 마지막에 들어간 데이터가 처음에 나오는 후입선출 자료 구조입니다. 안에 책이 쌓여 있는 박스를 열었을 때 마지막으로 넣은 책부터 빼는 것을 스택으로 비유할 수 있습니다.

스택에는 아래 두 가지 연산이 있습니다.

• push
• pop

Push

스택에 요소를 삽입하는 연산입니다.

정해진 위치의 끝에만 삽입하므로 시간복잡도는 관계 없이 항상 O(1) 입니다.

Pop

스택에 들어 있던 요소를 꺼내는 연산입니다.

정해진 위치의 끝에서만 꺼내므로 탐색은 필요하지 않고, 따라서 시간복잡도는 항상 O(1) 입니다.

큐 🚶🚶🚶

큐는 처음에 들어간 데이터가 처음에 나오는 선입선출 자료 구조입니다.

큐에는 아래 두 가지 기본 연산이 있습니다.

• enqueue
• dequeue

Enqueue

큐에 요소를 삽입하는 연산입니다. 스택과 마찬가지로 정해진 방향으로만 삽입하므로 시간 복잡도는 O(1) 입니다.

Dequeue

큐의 정해진 위치에서 요소를 제거하는 연산입니다. 정해진 방향에서만 (삽입 위치의 반대) 제거하므로 시간 복잡도는 O(1) 입니다.

덱 ↔️🚶🚶🚶↔️

덱(Deque; Double-ended queue)는 데크라고도 부르며 양 끝에서 삽입, 삭제 연산을 할 수 있는 자료 구조입니다. 큐가 양방향으로 있다고 생각하면 쉽습니다.

덱에는 아래 네 가지 기본 연산이 있습니다.

• push_first
• push_last
• pop_first
• pop_last

Push

덱의 양 끝에 요소를 삽입하는 연산입니다. 두 정해진 지점으로만 삽입하므로 push_first, push_last 모두 시간 복잡도는 O(1) 입니다.

Pop

덱의 양 끝에서 요소를 제거하는 연산입니다. 두 개의 정해진 지점으로만 삭제가 이루어지므로 앞, 뒤 관계없이 시간 복잡도는 O(1) 입니다.

🧹 마치며

사실 앞서 구현한 연결 리스트 구조를 내부적으로 활용하는 일은 굉장히 드뭅니다. Java의 LinkedList는 넉넉한 크기의 배열을 생성하여 필요할 때마다 추가 확장하는 방법으로 구현되어 있으며 Python의 C 구현체인 CPython 또한 배열을 동적 할당하고 필요할 때마다 확장하고 있습니다.

연결 리스트로 비교적 쉽게 구현할 수 있지만, 시간이 된다면 연결 리스트가 아닌 배열로 스택과 큐를 직접 구현해보는 것도 좋습니다.

다음 포스트에서는 트리에 대해 다루겠습니다. 읽어 주셔서 감사합니다.

⚠️ 유의사항 필자는 가독성과 구조화에 중점을 두고 문제를 풀이합니다. 필요하다면 클래스를 자주 사용하므로 절차지향 언어로 문제해결을 한다면 적용이 어려울 수 있습니다.

🔗 링크

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

✏️ 문제

주어진 조건에 따라 톱니바퀴를 회전시킨 후, 12시 방향이 S극인 톱니바퀴의 개수를 구하는 문제입니다.

🧠 접근

구현 난도가 마냥 낮지는 않지만 지문에서 설명하는 대로 구현하면 해결할 수 있는 문제입니다.

지문이 조금 아리까리하게 작성되어 있어서 이게 맞나... 하면서 여러번 지문을 돌려보고 부족한 필자의 문해력을 탓하게 된 문제이기도 합니다.

주의해야 할 사항은 아래 세 가지로 정리할 수 있습니다.

• 처음에 돌아가는 톱니바퀴는 맞물림 여부와 관계없이 반드시 돌아갑니다.
• 맞물림이 되지 않은 톱니바퀴 이후의 모든 톱니바퀴는 돌아가지 않습니다.
• 모든 맞물림 여부는 돌아가기 전에 확인해야 합니다.

톱니바퀴 구현

처음에는 덱을 활용하여 구현할까 생각했으나 맞물림 위치와 구해야 하는 톱니의 위치가 다르기에 효율적인 구현이라고 볼 수 없습니다.

특정 톱니의 값을 가져오는 데 굳이 추가 순회를 해서 확인하게 하는 건 품이 많이 들고, 그렇다고 톱니의 개수가 늘어나거나 줄어드는 것도 아니니까요.

톱니의 개수는 고정되어 있으니 톱니의 기본 상태를 배열에 저장해 두고 인덱스를 시작점으로 둔 뒤 회전에 따라 인덱스를 바꾸면 되겠다고 판단하였습니다.

class Gear {
    private int[] gear; // 톱니바퀴의 초기 상태
    private int currentPos; // 톱니바퀴의 초기 인덱스

    public Gear(int[] array) {
        gear = array;
        currentPos = 0;
    }

    // 왼쪽으로 돌아가면 인덱스 값은 증가함
    public void rollLeft() {
        currentPos = (currentPos + 1) % 8;
    }

    // 오른쪽으로 가면 인덱스 값은 감소함
    public void rollRight() {
        if (currentPos == 0) currentPos = 7;
        else currentPos -= 1;
    }

    // 인덱스 기준으로 각각 12시, 3시, 9시 값을 가져옴
    // 3시와 9시는 톱니바퀴가 맞물리는 지점
    public int get12() {
        return gear[currentPos];
    }

    public int get3() {
        return gear[(currentPos + 2) % 8];
    }

    public int get9() {
        return gear[(currentPos + 6) % 8];
    }
}

규칙에 따라 톱니바퀴를 돌리기

사실 필요한 모든 사항이 클래스로 구현되었기에 상술한 주의점을 생각하면서 규칙에 따라 구현하기만 하면 됩니다.

1. 먼저 톱니바퀴가 회전하는 방법을 저장해 둘 배열을 선언합니다.
2. 시작점은 반드시 돌아가도록 배열에 기록합니다.
3. 왼쪽과 오른쪽으로 각각 순회하면서 톱니바퀴의 회전 여부를 기록합니다.
4. 기록해 둔 배열을 이용해 톱니바퀴를 돌립니다.

int rollCount = Integer.parseInt(reader.readLine());

for (int i = 0; i < rollCount; i++) {
    String[] input = reader.readLine().split(" ");
    int pos = Integer.parseInt(input[0]) - 1;
    int direction = Integer.parseInt(input[1]); // 1 : 시계 방향, -1 : 반시계 방향
    int[] roll = new int[gearCount];

    // 현 위치를 회전시킴
    roll[pos] = direction;

    // 왼쪽 순회
    for (int j = pos - 1; j > -1; j--) {
        Gear current = gears[j];
        Gear prev = gears[j + 1];

        if (prev.get9() == current.get3()) 
            break;
        else {
            roll[j] = -1 * roll[j + 1]; // 반대 방향으로 회전
        }
    }
    // 오른쪽 순회
    for (int j = pos + 1; j < gearCount; j++) {
        Gear current = gears[j];
        Gear prev = gears[j - 1];

        if (prev.get3() == current.get9()) {
            break;
        } else {
            roll[j] = -1 * roll[j - 1];
        }
    }

    // 실제 회전
    for (int j = 0; j < gearCount; j++) {
        if (roll[j] == 1) gears[j].rollRight();
            if (roll[j] == -1) gears[j].rollLeft();
    }
}

이제 12시 방향이 S극인지 확인하고 정답을 출력해주면 끝납니다.

int count = 0;
for (int i = 0; i < gearCount; i++)
    if (gears[i].get12() == 1)
        count += 1;

System.out.println(count);

📄 전체 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int gearCount = Integer.parseInt(reader.readLine());
        Gear[] gears = new Gear[gearCount];

        for (int i = 0; i < gearCount; i++) 
            gears[i] = new Gear(Arrays.stream(reader.readLine().split("")).mapToInt(Integer::parseInt).toArray());

        int rollCount = Integer.parseInt(reader.readLine());

        for (int i = 0; i < rollCount; i++) {
            String[] input = reader.readLine().split(" ");
            int pos = Integer.parseInt(input[0]) - 1;
            int direction = Integer.parseInt(input[1]); // 1 : 시계 방향, -1 : 반시계 방향
            int[] roll = new int[gearCount];

            // 현 위치를 회전시킴
            roll[pos] = direction;

            // 왼쪽 순회
            for (int j = pos - 1; j > -1; j--) {
                Gear current = gears[j];
                Gear prev = gears[j + 1];

                if (prev.get9() == current.get3()) 
                    break;
                else {
                    roll[j] = -1 * roll[j + 1]; // 반대 방향으로 회전
                }
            }

            // 오른쪽 순회
            for (int j = pos + 1; j < gearCount; j++) {
                Gear current = gears[j];
                Gear prev = gears[j - 1];

                if (prev.get3() == current.get9()) {
                    break;
                } else {
                    roll[j] = -1 * roll[j - 1];
                }
            }

            // 실제 회전
            for (int j = 0; j < gearCount; j++) {
                if (roll[j] == 1) gears[j].rollRight();
                if (roll[j] == -1) gears[j].rollLeft();
            }
        }

        int count = 0;
        for (int i = 0; i < gearCount; i++)
            if (gears[i].get12() == 1)
                count += 1;

        System.out.println(count);        
    }  
}

class Gear {
    private int[] gear;
    private int currentPos;

    public Gear(int[] array) {
        gear = array;
        currentPos = 0;
    }

    public void rollLeft() {
        currentPos = (currentPos + 1) % 8;
    }

    public void rollRight() {
        if (currentPos == 0) currentPos = 7;
        else currentPos -= 1;
    }

    public int get12() {
        return gear[currentPos];
    }

    public int get3() {
        return gear[(currentPos + 2) % 8];
    }

    public int get9() {
        return gear[(currentPos + 6) % 8];
    }
}

❗️이 문제와 유사한 문제

• 백준 #14891 톱니바퀴

사실 거의 똑같은 문제이고, 이 문제를 푸셨다면 14891번은 몇 줄만 고치면 맞힐 수 있습니다. 그 반대는 조금은 생각해서 풀어야겠지만요.

주의: 이 내용은 필자가 JavaScript 개념을 리마인드하면서 작성한 것으로 정확하지 않은 정보가 있을 수 있습니다.

🪣 모든 언어의 기본은 자료형!

한 가지 언어만으로는 대개 한계가 있기에 우리는 살면서 여러 프로그래밍 언어를 다루게 됩니다. 그 과정에서 언어를 처음 접할 때 반드시 배우는 것이 있습니다. 바로 자료형입니다.

자료형은 프로그래밍 언어가 자료를 처리, 보관하기 위해 정해 놓은 형태를 말합니다.

여느 언어가 그렇듯 언어가 자료를 어떻게 처리하는지 이해해야 잘 다룰 수도 있게 됩니다.

그렇다면 자바스크립트는 어떤 자료형을 갖고 있을까요?

📄 기본 자료형 (Primitive type)

우선 기본 자료형입니다.

기본 자료형은 그 자체로 하나의 값을 가리킵니다. 즉, 비교 연산이 가능합니다.

다른 언어와 다르게 자바스크립트는 타입 체크가 굉장히 느슨합니다. C-like 언어들은 타입을 명시하고 해당 타입으로만 변수를 사용할 것을 강제하지만, 자바스크립트는 변수를 위한 공간만 줄 뿐 어떤 타입의 데이터도 저장이 가능합니다.

이러한 특성 때문에 문자열 합치기와 같은 상황에서 예기치 못한 문제가 생기곤 합니다.

console.log(("b" + "a" + + "n" + "a").toLowerCase())

위 결과가 banana가 된다는 예시는 정말 유명하죠...

Number

다른 언어에는 숫자의 유형에 따라 다양한 자료형이 있습니다.

그러나 Number 타입은 숫자가 어떻든 관계없이 모두 64비트 부동 소수점으로 처리합니다. 그렇기에 다른 언어보다 실수 계산 시의 오차 문제에 신경을 더 써야 합니다.

const number = 0.1 + 0.2
const divided = 5 / 2

console.log(number == 0.3) // false
console.log(number) // 0.30000000000000004
console.log(divided) // 2.5

BigInt

Number 타입은 64비트 부동 소수점으로 값을 관리하므로 매우 큰 수를 다룰 때 오차 문제가 생길 수 있습니다. 이 문제를 해결하기 위해 ES11에서 BigInt 타입이 새로 등장했습니다.

BigInt() 함수나 정수 리터럴 뒤에 n을 붙여 선언할 수 있습니다.

const bigIntOne = 123456789123456789123456789n
const bigIntTwo = BigInt("123456789123456789123456789")

console.log(bigIntOne.toString()) // "123456789123456789123456789"
console.log(bigIntTwo.toString()) // "123456789123456789123456789"

console.log(typeof bigIntOne) // bigint
console.log(typeof bigIntTwo) // bigint

BigInt는 Number와 일치하지는 않지만 값은 동등합니다.

console.log(1n === 1) // false
console.log(1n == 1) // true

String

문자열 변수입니다.

C 의 char 변수와 유사하게 인덱스로 특정 위치의 문자열을 조회할 수 있습니다. 단, 여기에도 다른 언어와 조금 차이가 있는데, 한 번 정의된 문자열은 수정되지 않는다는 점입니다.

let str = "javascript"

console.log(str[0]) // j
str[4] = "S"
console.log(str) // javascript

Boolean

불리언 자료형입니다. true 와 false 두 가지 값이 있습니다.

Symbol

ES6에서 새로 추가된, 변경 불가능한 원시 값을 저장하는 타입입니다. 객체의 프로퍼티 키로 주로 사용됩니다.

const obj = {};
const sym = Symbol();

obj[sym1] = 'asdf';

console.log(obj); // {Symbol(): 'asdf'}

Undefined

자바스크립트를 쓰게 되면 지겹게 볼 자료형입니다. 값이 할당되지 않은 모든 변수 및 상수는 undefined 를 가리킵니다.

특이하게도, undefined는 타입이기도 하면서 값이기도 합니다.

console.log(typeof undefined) // undefined

null

할당된 값이 없다는 점에서 undefined 와 유사합니다. 대신 null 은 개발자가 명시적으로 값이 비어있음을 나타낼 때 사용합니다.

주의할 점은 null 타입 변수의 typeof 결과는 object라는 점입니다. 따라서 어느 변수가 null인지 확인하려면 ===를 사용하여야 합니다.

const nullValue = null;
console.log(typeof nullValue) // object
console.log(null === nullValue) // true

📄 참조 자료형 (Reference type)

자바스크립트에서 상술한 기본 타입을 제외하면 모든 값은 객체(참조 타입)입니다.

자바스크립트의 객체는 key-value 형태의 프로퍼티를 저장하는 컨테이너입니다. 객체의 프로퍼티로는 기본 타입의 값이나 객체, 함수도 들어갈 수 있으며 함수가 포함된 프로퍼티를 메서드라고 합니다.

객체를 생성하는 방법

객체는 크게 세 가지 방법으로 생성할 수 있습니다.

1. 기본 생성자 함수 Object()
2. 객체 리터럴 { prop0: "foo", prop1: "bar" }
3. 기타 생성자 함수

   const foo = new Object() // 생성자 함수로 생성
   const bar = {
   prop0: "foo",
   prop1: "bar",
   } // 객체 리터럴로 생성
   const add = new Function('x', 'y', 'return x + y') // Function 생성자로 생성

객체의 프로퍼티에 접근하는 방법

객체의 프로퍼티에 접근하여 값을 바꾸거나 조회, 생성할 수 있습니다.

1. 마침표 표기법 객체 이름에 마침표를 찍고 프로퍼티명을 그 뒤에 붙입니다. 어떤 프로퍼티는 이러한 방식으로 접근할 수 없을 수 있습니다. 이런 때에는 대괄호 표기법을 사용합니다.

   const test = { 0: '101', 'asdf': '102' }
   test.foo = 'bar'
   

console.log(test.foo) // bar console.log(test.asdf) // 102 console.log(test.0) // Syntax error!

2. 대괄호 표기법
객체 이름 뒤에 대괄호를 적고 괄호 안에 프로퍼티의 이름을 문자열로 입력합니다.
```javascript
const test = { 0: '101' }
test['foo'] = 'bar'

console.log(test['foo']) // bar

참조 타입의 함정 - Call by reference

않이 이게 왜 다르지

기본 타입은 == 연산자를 통해 비교할 때 값을 비교하지만, 참조 타입은 참조 값을 비교합니다.

const foo = 'fooo'
const bar = 'fooo'

console.log(foo == bar) // true

const obj1 = { value: 100 }
const obj2 = { value: 100 }

console.log(obj1 == obj2) // false

참조 타입의 경우 해당 객체가 저장된 주소가 다르면 다른 객체로 취급하게 됩니다.

복사도 마음대로 안 된다!

기본 타입은 값에 의한 호출(Call by value)로 작동하기에 값을 복사할 때도 복사된 값이 전달됩니다. 즉 독립적인 변수가 됩니다.

하지만 객체는 참조에 의한 호출(Call by reference)로 작동하므로 객체의 참조만 복사될 뿐입니다.

const obj1 = { value: 100 }
const obj2 = obj1

obj2.value = 200
console.log(obj1.value, obj2.value) // 200, 200

obj2의 value 값을 변경했는데 obj1도 같이 변경된 것을 볼 수 있습니다. obj2가 obj1의 참조에 불과하기 때문입니다.

🧹 마치며

지금까지 자바스크립트의 자료형에 대해 간단히 알아보았습니다.

사실 객체에서는 설명할 것이 이것보다 훨씬 방대하지만 여기에서 전부 설명하면 주제가 산으로 가므로 별도의 포스트에서 다루겠습니다.

다음에는 배열에 대해 다룰 예정입니다. 읽어 주셔서 감사합니다.

알고리즘 문제풀이를 하다 보면 한번쯤은 이 이상한 태그를 보게 됩니다.

다이나믹 프로그래밍

대체 다이나믹 프로그래밍이 뭘까요? 그리고 이 태그가 붙은 문제는 왜 다들 해결방법이 가지각색인 걸까요?

그것이 알고싶다 다이나믹 프로그래밍

다이나믹 프로그래밍은 알고리즘을 설계하는 방법으로, 큰 문제를 작은 문제로 나누어 작은 문제의 답을 큰 문제에 적용하는 "계획"을 세우는 문제 해결 기법입니다.

다이나믹 프로그래밍은 아래의 조건을 만족할 때 사용할 수 있습니다.

1. 최적 부분 구조 (Optimal substructure) 큰 문제를 작은 문제로 분해, 작은 문제의 답을 큰 문제에 사용할 수 있는 경우를 의미합니다. 일종의 분할-정복(Divide and conquer)이기도 합니다.
2. 중복되는 부분 문제 (Overlapping subproblem) 작은 문제가 반복 풀이되는 경우를 의미합니다.

작은 문제의 답을 큰 문제에 어떻게 적용하느냐가 다이나믹 프로그래밍의 핵심으로, 이 계획을 어떻게 세우냐에 문제 풀이의 성패가 좌우됩니다.

간단한 예시를 보면서 DP가 무엇인지 알아봅시다.

🪆 DP의 훌륭한 예시, 피보나치 수열

재귀로도 해결할 수 있지만...

피보나치 수열은 f(0) = 0 f(1) = 1 f(n) = f(n - 1) + f(n - 2) (n >= 2) 를 만족하는 수의 집합입니다.

이 수열의 n번째 값을 구하는 fibonacci() 함수의 재귀적인 구현은 표현이 명료한 재귀 알고리즘의 예시로 잘 알려져 있습니다.

public int fibonacci(int n) {
    if (n < 2) 
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

코드가 필요 이상으로 길어진다는 말을 자주 듣는 Java로도 이렇게 짧고 명료한 코드가 나옵니다.

그런데 이 재귀 알고리즘은 n 이 커질 경우 함수 호출이 지수 스케일로 엄청나게 증가하게 됩니다.

가령 4번째 피보나치 수를 구하는 과정에서의 호출 트리입니다. f(1) 과 f(0) 은 상수를 리턴하지만, 계산이 필요한 f(3), f(2) 에 대해 중복 계산이 발생하고 있습니다.

여기에서 n 이 30만 되어도 약 5억의 호출이 발생하며 호출 스택 공간은 이를 고려해서 설계되지 않았으므로 stack overflow 오류를 발생시킵니다.

스택 공간을 임의로 늘린다 하더라도 수행 시간이 폭증하는 점은 변함이 없기에 우리는 다른 해결 방법을 찾을 필요가 있습니다.

이미 나온 결괏값을 어떻게 활용할까?

앞서 필자는 작은 문제의 답을 큰 문제의 정답에 활용하는 것이 다이나믹 프로그래밍이라 하였습니다.

그러면 피보나치 수를 구할 때 작은 문제와 큰 문제는 각각 무엇일까요?

위의 예시에서처럼 f(4) 를 구한다면 f(3), f(2), f(1), f(0) 이 각각 작은 문제가 됩니다.

따라서, n번째 피보나치 수를 저장할 곳을 만들고 따로 계산할 필요 없이 계산된 결괏값을 활용하면 중복 계산 없이 빠르게 계산할 수 있게 됩니다.

이렇게 계산한 값을 저장하고 필요할 때 다시 꺼내 쓰는 기법을 메모이제이션이라 합니다.

bottom-up 방법

int[] dp = new int[n + 1];
dp[1] = 1;

if (n < 2)  // n이 2보다 작으면 f(0) = 0, f(1) = 1
    return n;
else {
    // f(n) = f(n - 1) + f(n - 2)
    // 배열에 결괏값을 집어넣는다
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2]; 
    return dp[n];
}

top-down 방법

혹은 아래와 같이 풀 수도 있습니다. (로직만 간단하게 보여드리기 위해 작성한 코드로 실제 동작하는 코드와는 차이가 있습니다.)

public static int[] result = new int[n + 1];

public int fibonacci(int[] dp, int n) {
    // 이미 저장된 값이면 해당 값을 리턴
    if (dp[n] != 0)
        return dp[n];
    // 초깃값
    if (n < 2)
        return n;
    // 계산된 값을 저장하고 리턴
    return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

이처럼 이전 결괏값을 어떻게 활용할 수 있을지 발견하는 것이 다이나믹 프로그래밍의 핵심!

🤦‍♀️ 하지만 이렇게 쉽기만 하다면 얼마나 좋겠어요

아마 이 글을 검색해서 들어오신 많은 분들은 위 예시보다는 훨씬 난도가 높은 문제를 맞닥뜨리고 오셨을 것입니다.

하지만 다이나믹 프로그래밍은 알고리즘이 아닌 하나의 패러다임으로, 문제를 어떻게 잘게 분해하고 연관성을 찾는지는 풀이하는 사람의 몫입니다.

이 글을 읽고 계신 분들의 표정 상상도...jpg

안타깝지만 다이나믹 프로그래밍에 왕도는 없습니다. 많은 문제를 풀어 보시면서 점화식을 세우는 연습이 답입니다.

저도 다이나믹 프로그래밍에 무지하게 약한 만큼 머리를 싸매다가 풀이를 본 적이 많았습니다. 그리고 단순명료한 점화식과 풀이를 보고는 이불을 걷어찹니다

연습, 그리고 연습

작정하고 어렵게 만들면 사경을 헤매게(?) 만들 수도 있고, 방향을 잘못 잡으면 정말 밑도 끝도 없이 사고의 나락으로 빠져드는 게 다이나믹 프로그래밍입니다. 그렇기에 시간을 정해 두고 도저히 풀리지 않는다면 풀이를 참고하면서 자기 것으로 만드는 것도 좋습니다.

언제나 그렇듯 Problem solving은 연습... 연습만이 살 길입니다.

여담, 그냥 헛소리

이름은 참 거창한 "다이나믹" 프로그래밍인데, 사실 딱히 다이나믹하지는 않습니다. 그렇기에 전공자의 시각에서 보면 대체 이 알고리즘의 어디가 다이나믹하다는 거야? 라고 생각하기 쉽습니다.

그런데 다이나믹 프로그래밍이라는 기법을 만든 리처드 벨만도 단순히

dynamic이라는 단어 너무 멋지지 않냐?!

같은 생각으로 명명했다는 우스갯소리가 있는데, 믿거나 말거나.

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

✏️ 문제

강을 사이에 두고 다리를 놓을 수 있는 지점이 주어졌을 때 다리를 놓는 방법의 개수를 구하는 문제입니다.

다리는 서로 겹칠 수 없습니다.

🧠 접근

먼저 문제를 단순화해 봅시다.

다리를 서로 겹치게 놓을 수 없으므로 강 왼쪽에 3개의 사이트, 오른쪽에 4개의 사이트가 있다고 하면 다리를 놓는 방법은 아래 4가지가 있습니다.

1, 2, 3 1, 2, 4 1, 3, 4 2, 3, 4

여기서 다리를 겹치게 놓을 수 없다는 점이 힌트로, 다리 왼쪽의 사이트 개수가 m, 오른쪽의 사이트 개수가 n이라고 하면 다리를 놓는 방법의 개수는 n개 중에서 m개를 순서 상관 없이 뽑는 방법의 개수와 같습니다.

이를 수식으로 표현하면 $$ \binom{n}{m} = \frac{n!}{(n-m)!m!} $$ 이고, 수식에 대입만 하면 됩니다!

팩토리얼이 너무 커요

하지만 뭔가 이상합니다. 수식에 팩토리얼이 포함되어 있어 만약 n = 30 이라면 $$30!$$ 을 계산해야 하는데, $$20!$$ 만 되더라도 64비트 정수형의 범위를 넘어서기 때문에 Java의 BigInteger 와 같은 편법을 쓰거나 조합의 성질을 활용할 필요가 있습니다.

그런데 $$n$$ 과 $$m$$ 이 클 때 굉장히 유용한 조합의 성질이 있습니다.

$$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$$, $$\binom{n}{1} = n$$

두 성질을 이용하면 조합을 일일이 계산할 필요 없이 구할 수 있게 됩니다.

즉, 아래와 같은 형태가 됩니다.

final int MAX = 30;

int[][] dp = new int[MAX + 1][MAX + 1];

// 초깃값을 채움 (m개 중에 하나만 고를 때)
for (int i = 1; i <= MAX; i++) 
    dp[i][1] = i;

for (int j = 2; j <= MAX; j++) 
     for (int k = 2; k <= MAX; k++) 
         dp[j][k] = dp[j - 1][k - 1] + dp[j - 1][k];

위 배열에 1에서 30까지에 해당하는 모든 조합의 값이 들어가므로 배열에서 적절히 출력해 주면 끝납니다.

📄 전체 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    private final static int MAX = 30;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(reader.readLine());
        int[][] dp = new int[MAX + 1][MAX + 1];

        for (int i = 1; i <= MAX; i++) {
            dp[i][1] = i;
        }

        for (int j = 2; j <= MAX; j++) {
            for (int k = 2; k <= MAX; k++) {
                dp[j][k] = dp[j - 1][k - 1] + dp[j - 1][k];
            }
        }

        for (int i = 0; i < testCase; i++) {
            int[] input = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int n = input[1];
            int r = input[0];

            System.out.println(dp[n][r]);
        }
    }
}

주의: 본 포스트는 저자가 학습하면서 작성한 글이므로 잘못된 내용이 있을 수 있습니다. 지적과 제언은 언제든지 환영입니다.

✏️ 들어서며

비슷하면서도 다른 배열과 연결 리스트

많은 언어가 배열과 연결 리스트를 언어 차원이나 언어 내장 라이브러리를 통해 지원하고 있습니다. 관계가 있는 데이터를 연속적으로 저장하는 차원에서 배열과 연결 리스트는 굉장히 유사하지만, 세부적인 구현엔 큰 차이가 있습니다.

배열은 연속적이고 고정된 메모리 공간을 할당받으며 자료형이나 크기를 변경하기 곤란하며 중간에 원소를 끼워넣기 힘든 대신 인덱스를 통한 무작위 탐색에 큰 강점을 보입니다. 반면 연결 리스트는 원소의 삽입과 삭제가 잦은 환경에 강하지만 탐색에 약합니다.

왜 그런지 연결 리스트를 살펴보면서 이해해봅시다.

🖇 연결 리스트는 무엇?

연결 리스트는 각 노드가 데이터와 주소를 가지고 서로 연결되어 있는 자료 구조입니다. 노드는 각자의 고유한 데이터와 다음 노드의 정보를 갖게 됩니다.

일부 연결 리스트는 head 와 tail 이라는 특별한 정보를 갖고 있기도 합니다. head 와 tail 은 각각 첫 노드와 마지막 노드의 주소 정보를 저장합니다.

연결 리스트는 각 노드의 링크가 어떻게 구성되어 있냐에 따라

• 단일 연결 리스트 (singly linked list)
• 이중 연결 리스트 (doubly linked list)
• 다중 연결 리스트 (multiply linked list)
• 원형 연결 리스트 (circular linked list)

로 나뉘며 여기에서는 다중 연결 리스트를 제외한 나머지를 다루겠습니다.

단일 연결 리스트

단일 연결 리스트는 다음 노드로 향하는 링크 하나만을 갖는 연결 리스트입니다. 첫 노드(head)로부터 일렬로 늘어선 구조이므로 첫 노드의 주소 정보가 필요합니다.

연결 리스트 중 가장 쉽게 구현할 수 있지만 노드가 유실되면 해당 노드의 뒤쪽은 모두 사용할 수 없게 되는 단점이 있습니다.

검색

노드를 하나하나 따라가면서 검색합니다. head 노드로부터 data를 확인하고, 아니면 next에 표시된 다음 노드의 data를 순차적으로 확인합니다. 시간 복잡도는 최선의 경우 O(1) , 최악의 경우 모든 노드를 탐색해야 하므로 O(n) 입니다. (tail 노드 정보를 가지고 있는 경우 n-1의 시간이 걸림)

삽입

검색과 마찬가지로 삽입할 위치까지 하나하나 따라간 다음 새로운 노드를 생성하고 주소 정보를 바꿉니다. 시간 복잡도는 최선의 경우 첫 노드로 삽입하는 경우이므로 O(1) , 최악의 경우 O(n) 입니다. (tail 노드 정보를 갖고 있는 경우)

삭제

검색, 삽입과 마찬가지로 삽입할 위치까지 따라간 다음 이전 노드의 next를 삭제할 노드의 next로 변경한 뒤 삭제할 노드의 메모리를 해제합니다. 시간 복잡도는 최선의 경우 첫 노드로 삽입하는 경우이므로 O(1) , 최악의 경우 O(n) 입니다. (tail 노드 정보를 갖고 있는 경우)

원형 단일 연결 리스트

단일 연결 리스트와 크게 다르지 않으나, 마지막 노드의 next가 첫 노드를 가리켜 순환하도록 구성된 것이 특징입니다.

마지막 노드의 next를 설정해 주어야 하는 것 이외에는 단일 연결 리스트와 동일합니다.

이중 연결 리스트

단일 연결 리스트와 다르게 각 노드가 이전 노드도 가리키는 것이 특징입니다. 노드의 유실 방지 대책을 세워 놓은 경우 단일 연결 리스트보다 노드 유실과 같은 돌발 상황에 대처하기 좋습니다.

검색

단일 연결 리스트와 같이 노드를 하나하나 따라가면서 검색합니다. 시간 복잡도는 최선의 경우 O(1) , 최악의 경우 모든 노드를 탐색해야 하므로 O(n) 입니다. (tail 노드 정보를 가지고 있는 경우 n-1의 시간이 걸림)

삽입

검색과 마찬가지로 삽입할 위치까지 하나하나 따라간 다음 새로운 노드를 생성하고 주소 정보를 바꿉니다. 시간 복잡도는 최선의 경우 첫 노드 또는 마지막 노드로 삽입하는 경우이므로 O(1) , 최악의 경우 O(n) 입니다. (거꾸로 따라갈 수도 있으므로 소요 시간 n/2+1)

삭제

검색, 삽입과 마찬가지로 삽입할 위치까지 따라간 다음 이전 노드의 next를 삭제할 노드의 next로 변경한 뒤 삭제할 노드의 메모리를 해제합니다. 시간 복잡도는 최선의 경우 첫 노드 또는 마지막 노드로 삭제하는 경우이므로 O(1) , 최악의 경우 O(n) 입니다. (거꾸로 따라갈 수도 있으므로 소요 시간 n/2+1)

원형 이중 연결 리스트

이중 연결 리스트와 크게 다르지 않으나, 첫 노드와 마지막 노드가 서로를 가리켜 순환하도록 구성된 것이 특징입니다.

마지막 노드의 next와 처음 노드의 prev를 설정해 주어야 하는 것 이외에는 단일 연결 리스트와 동일합니다.

✍️ 연결 리스트의 구현

단일 연결 리스트와 이중 연결 리스트를 구현하였습니다. 구현 언어는 C입니다.

단일 연결 리스트

• 리스트 노드 구조체 및 head 노드 정보

  typedef struct _node {
    int data;
    struct _node *next;
  } node;
  

node *head = NULL;

- 삽입
```c
void insert_node(int i, int pos) {
    // 노드 동적 할당
    node *new_node = (node *) malloc(sizeof(node));
    new_node -> data = i;
    new_node -> next = NULL;

    if (head == NULL) {
        head = new_node;
    } else {
        if (pos == 0) {
            new_node -> next = head;
            head = new_node;
        } else {
            // 삽입될 노드의 이전 노드 지정
            node *prev = head;
            // 삽입될 이전 위치의 주소 정보를 가져옴
            for (int i = 0; i < pos - 1; i++) {
                prev = prev -> next; 
                if (prev == NULL) 
                    return; // 삽입할 수 없는 위치임
            }
            // 새로은 노드로 삽입
            new_node -> next = prev -> next;
            prev -> next = new_node;
        }
    }
}

• 삭제

  void delete_node(int pos) {
    // 처음 노드를 삭제하는 경우
    if (pos == 0) {
        if (head == NULL) 
            return; // 노드 없음
        node *target = head;
        // 첫 노드의 다음 노드가 없을 때 (노드가 하나 뿐)
        if (target -> next == NULL) 
            head = NULL;
        else
            head = target -> next;
        free(target);
    } else {
        node *target_prev = head;
        for (int i = 0; i < pos - 1; i++) {
            target_prev = target_prev -> next;
            if (target_prev == NULL || target_prev -> next == NULL) 
                return; // 리스트 범위를 벗어난 입력 값
        }
        node *target = target_prev -> next;
        target_prev -> next = target -> next;
        free(target);
    }
  }

이중 연결 리스트

• 리스트 노드 구조체 및 head, tail 노드 정보

  typedef struct _node {
    int data;
    struct _node *next;
    struct _node *prev;
  } node;
  

node *head = NULL; node *tail = NULL;

- 삽입
```c
void insert_node(int i, int pos) {
    // 노드 동적 할당
    node *new_node = (node *) malloc(sizeof(node));
    new_node -> data = i;
    new_node -> prev = NULL;
    new_node -> next = NULL;

    // 리스트가 비어 있을 때
    if (head == NULL) {
        head = new_node;
        tail = new_node;
    } else {
        if (pos == 0) {
            // 기존 head와 새로운 노드(head)를 연결하고 head 변경
            head -> prev = new_node;
            new_node -> next = head;
            head = new_node;
        } else {
            // 삽입될 노드의 이전 노드 지정
            node *new_prev = head;
            // 삽입될 이전 위치의 주소 정보를 가져옴
            for (int i = 0; i < pos - 1; i++) {
                new_prev = new_prev -> next;
                if (new_prev == NULL) 
                    return; // 삽입할 수 없는 위치
            }
            // 새로운 노드로 삽입
            new_node -> next = new_prev -> next;
            new_prev -> next = new_node;
            new_node -> prev = new_prev;

            // 마지막 노드이면 tail로 설정, 아니면 이전 노드 정보 연결
            if (new_node -> next == NULL)
                tail = new_node;
            else
                new_node -> next -> prev = new_node; 
        }
    }
}

• 삭제

  void delete_node(int pos) {
    // 처음 노드를 삭제하는 경우
    if (pos == 0) {
        if (head == NULL) 
            return; // 노드 없음
        node *target = head;
        // 첫 노드의 다음 노드가 없을 때 (노드가 하나 뿐)
        if (target -> next == NULL) { 
            head = NULL;
            tail = NULL;
        } else {
            head = target -> next;
            target -> next -> prev = NULL;
            // 노드가 더 없으면 tail과 head의 주소는 같음
            if (head -> next == NULL)
                tail = head;
        }
        free(target);
    } else {
        node *target_prev = head;
        for (int i = 0; i < pos - 1; i++) {
            target_prev = target_prev -> next;
            if (target_prev == NULL || target_prev -> next == NULL)
                return;
        }
        node *target = target_prev -> next;
        if (target -> next == NULL) {
            tail = target_prev;
        } else {
            target -> next -> prev = target_prev;
        }
        target_prev -> next = target -> next;
        free(target);
    }
  }

🧹 마치며

연결 리스트는 크기가 가변적이고 삽입과 삭제 연산이 간단해 배열보다 유리한 점이 많지만, 잦은 탐색에 취약한 모습을 보입니다.

이러한 연결 리스트의 약점을 보완해줄 수 있는 다른 자료구조가 다수 있는데, 이는 추후에 다뤄 보도록 하겠습니다.

🔗 링크

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

✏️ 문제

뿌요뿌요 게임의 필드 상황이 주어졌을 때 몇 번의 연쇄가 발생하는지 구하는 문제입니다.

뿌요가 터지는 조건은 아래와 같습니다.

1. 같은 색의 뿌요가 상, 하, 좌, 우로 4개 이상 연결되어 있으면 한꺼번에 터진다. (연쇄 시작, 1연쇄)
2. 뿌요가 사라진 빈 공간 위에 뿌요가 있다면 바닥으로 떨어진다.
3. 뿌요가 떨어져 재배치되었을 때 1의 조건을 만족한다면 한꺼번에 터지며, 1연쇄를 추가한다.

🧠 접근

자칫 어려워보일 수 있으나 지문에서 제시하는 대로 시뮬레이션하면 되는 문제입니다.

뿌요가 터지는 조건을 만족하는지 어떻게 확인할까?

깊이 우선 탐색으로 간단히 접근할 수 있습니다.

우선 필드를 표현하는 배열의 복사본을 준비합니다. 배열 중 하나는 터질 뿌요를 찾는 데 쓰이며, 다른 하나는 실제 결과물에 반영하기 위해 쓰입니다.

비어 있지 않은 칸을 발견하면 깊이 우선 탐색으로 들어가며, 해당 뿌요의 위치로부터 몇 개의 뿌요가 붙어 있는지 확인합니다.

연결되어 있는 뿌요의 개수를 세기 위해 배열의 복사본을 사용합니다. 중복 계산으로 인한 무한 루프를 막기 위해 체크한 칸은 뿌요 없음으로 바꾸며, 조건을 만족하는 위치를 큐에 추가합니다.

    (...main)
    do {
        // 필드를 순회해 터질 뿌요를 찾음
         for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (!map[i][j].equals(".")) {
                    temp = 0;
                    dfs(i, j, map);
                    if (temp >= 4) {
                        explodedPoint.add(new Point(i, j));
                        isExploded = true;
                     }
                }
            }
        }
        // 터진 뿌요가 하나 이상이면 연쇄 횟수 증가
        if (isExploded)
            currentRen += 1;
    (...)
    } while (isExploded);

    System.out.println(currentRen);
}

private static void dfs(int x, int y, String[][] map) {
    String current = map[x][y];
    map[x][y] = ".";
    temp += 1;

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

        if (nextX < 0 || nextY < 0 || nextX >= 12 || nextY >= 6)
            continue;

        if (map[nextX][nextY].equals(current))
            dfs(nextX, nextY, map);
    }
}

dfs()가 지나온 곳을 빈 곳으로 만들도록 작성되어 있으므로 실제 배열에서 뿌요를 터뜨리는 데도 사용할 수 있습니다.

뿌요를 터뜨리자!

// 터질 뿌요가 없을 때까지 반복
do {
    Queue<Point> explodedPoint = new LinkedList<>(); // 터질 뿌요의 시작점을 저장
    isExploded = false;

    // 필드를 순회해 터질 뿌요를 찾음
    (...)
    // 터진 뿌요가 하나 이상이면 연쇄 횟수 증가
    if (isExploded)
        currentRen += 1;
    // 실제 반영될 필드에서 뿌요를 터뜨림
    while (!explodedPoint.isEmpty()) {
        Point p = explodedPoint.poll();
        dfs(p.x, p.y, mapBak);
    }
    (...)
} while (isExploded);

터질 뿌요의 정보를 큐에 넣어 두었으므로 간단하게 터뜨릴 수 있습니다. 그러나 터뜨린 직후에는 뿌요가 공중에 떠 있게 되므로 이를 바닥으로 떨어트려 주어야 합니다.

뿌요를 바닥으로 어떻게 떨어트리지?

공중에 떠 있는 뿌요를 어떻게 떨어트릴 수 있을까요? 이 질문에 대해 답을 내기 전에, 뿌요가 떨어지는 조건에 대해 생각해 봅시다.

가령, 아래와 같은 예제가 있다고 합시다. (실제로 가능한 형태가 아닐 수 있습니다.)

......
......
......
......
......
......
......
BY....
BY....
RRG...
RRYG..
BBYGG.

이 예제에서 1연쇄가 일어나면 아래와 같이 변합니다.

......
......
......
......
......
......
......
BY....
BY....
..G...
..YG..
BBYGG.

여기서 2열을 주목합시다. .......YY..B 중력에 의해 뿌요가 떨어진다면 빈 칸을 없애기만 하면 됩니다. 필자는 빈 칸을 없애기 위해 .을 제외한 모든 배열의 열 요소를 스택에 집어 넣고 바닥부터 pop하는 방법을 사용하였습니다. 구현하는 방법은 이외에도 여러 가지가 있으니 편한 방법으로 하시면 됩니다.

// 터질 뿌요가 없을 때까지 반복
do {
    (...)
    // 뿌요를 내려 필드를 다시 그림
    for (int i = 0; i < 6; i++) {
        Stack<String> verticalPuyos = new Stack<>();
        for (int j = 0; j < 12; j++) {
            if (!mapBak[j][i].equals("."))
                verticalPuyos.add(mapBak[j][i]);
            }
            int index = 11;
            while(!verticalPuyos.isEmpty()) {
                mapBak[index][i] = verticalPuyos.pop();
            index -= 1;
        }
        for (int j = index; j >= 0; j--) {
            mapBak[j][i] = ".";
        }
    }
} while (isExploded);

이제 currentRen을 출력해 주기만 하면 됩니다!

📄 전체 소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Queue;
import java.util.Stack;
import java.util.LinkedList;

public class Main {
    private static int[] DX = {1, -1, 0, 0};
    private static int[] DY = {0, 0, 1, -1};
    private static String[][] map, mapBak;
    private static int temp;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        boolean isExploded = false; // 각 스캔에서 터졌는지 체크
        int currentRen = 0; // 연쇄 횟수
        map = new String[12][6];
        mapBak = new String[12][6];

        for (int i = 0; i < 12; i++) 
            map[i] = reader.readLine().split("");

        copyArray(map, mapBak); // 원본 배열의 백업

        do {
            Queue<Point> explodedPoint = new LinkedList<>(); // 터질 뿌요의 시작점을 저장
            isExploded = false;

            // 필드를 순회해 터질 뿌요를 찾음
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if (!map[i][j].equals(".")) {
                        temp = 0;
                        dfs(i, j, map);
                        if (temp >= 4) {
                            explodedPoint.add(new Point(i, j));
                            isExploded = true;
                        }
                    }
                }
            }
            // 터진 뿌요가 하나 이상이면 연쇄 횟수 증가
            if (isExploded)
                currentRen += 1;
            // 실제 반영될 필드에서 뿌요를 터뜨림
            while (!explodedPoint.isEmpty()) {
                Point p = explodedPoint.poll();
                dfs(p.x, p.y, mapBak);
            }
            // 뿌요를 내려 필드를 다시 그림
            for (int i = 0; i < 6; i++) {
                Stack<String> verticalPuyos = new Stack<>();
                for (int j = 0; j < 12; j++) {
                    if (!mapBak[j][i].equals("."))
                        verticalPuyos.add(mapBak[j][i]);
                }
                int index = 11;
                while(!verticalPuyos.isEmpty()) {
                    mapBak[index][i] = verticalPuyos.pop();
                    index -= 1;
                }
                for (int j = index; j >= 0; j--) {
                    mapBak[j][i] = ".";
                }
            }
            copyArray(mapBak, map);
        } while (isExploded);

        System.out.println(currentRen);
    }

    // 2차원 배열 복사
    private static void copyArray(String[][] source, String[][] destination) {
        for (int i = 0; i < source.length; i++) 
           System.arraycopy(source[i], 0, destination[i], 0, source[0].length); 
    }

    private static void dfs(int x, int y, String[][] map) {
        String current = map[x][y];
        map[x][y] = ".";
        temp += 1;

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

            if (nextX < 0 || nextY < 0 || nextX >= 12 || nextY >= 6)
                continue;

            if (map[nextX][nextY].equals(current))
                dfs(nextX, nextY, map);
        }
    }
}

class Point {
    int x, y;
    public Point(int x, int y) {
         this.x = x;
        this.y = y;
    }
}

😉 이 문제를 푸는 데 도움이 된 문제

• 백준 #1926 그림

템플릿 리터럴은 ES6의 핵심 스펙 중 하나입니다. 자칫 복잡해질 수 있는 문자열 처리를 몇 가지 구문만으로 간단하게 처리할 수 있습니다. 심지어 줄바꿈을 일반 텍스트로 넣어도 알아서 잘 처리해 줍니다.

const text = `집 가고 싶다.
집에보내줘\n제발`

위 상황은 text 변수에 템플릿 리터럴을 선언한 것입니다. 자바스크립트 파서는 이 템플릿 리터럴을 적절하게 해석하여

집 가고 싶다.
집에보내줘
제발

위와 같은 문자열로 변환합니다. 일반 줄바꿈을 인식하였음은 물론 이스케이프 문자(\n)를 만나 줄바꿈까지 된 모습입니다. 하지만 이스케이프 문자(escape sequence라고도 합니다)를 만나면 파서가 이도 같이 해석하기 때문에 순수한 문자열만을 전달해주어야 할 때 문제가 생기게 됩니다. 위와 같이 리터럴을 별도의 처리 없이 그대로 웹 브라우저에 보여주고 싶은 상황일 때, 템플릿 리터럴을 그냥 사용하면 줄바꿈 이스케이프 문자가 인식되어 아래와 같이 변환됩니다.

✏️ 그럼 어떻게 해결할까?

String.replaceAll()을 사용하면 어떨까?

먼저 필자는 템플릿 리터럴로 처리되기 전 문자열을 이스케이프 문자로 인식할 수 없도록 변환하는 방법을 생각했습니다.

\n을 \\n으로 변환하면 문제가 없지 않을까?

그러나 이 방법은 이스케이프 문자의 종류만큼의 replaceAll()을 사용해야 해 코드가 지저분해짐은 물론, 파서가 템플릿 리터럴을 처리한 후에는 이스케이프 문자가 모두 변환되어 있어 replaceAll() 변환 과정을 처리하는 함수의 인자로도 사용할 수 없다는 문제가 있었습니다.

문자열을 보이는 그대로 사용할 방법은 없는 걸까? 있다!

생각을 조금 바꾸어 문자열을 그대로 사용할 수 있는 방법을 고민한 결과, 템플릿 리터럴의 태그 함수로 String.raw()가 있음을 알았고, 적용해 보았습니다.

const code = String.raw`if (array[i])
  builder.append(Integer.toString(i) + "\n");
`
console.log(code)

드디어 원하는 결과물을 얻었습니다.

📄 결론

몇 시간을 싸매고 고민하다 포기할 뻔한 문제가 MDN에서 찾은 자바스크립트 내장 함수로 허무하게 해결되니 시원섭섭한 기분을 지울 수 없었습니다. 번역이 잘 되어 있지 않다는 이유로 MDN을 잘 찾아보지 않는 습관이 있었는데, 이 습관을 고칠 동기가 하나 생겼습니다.

https://programmers.co.kr/learn/courses/30/lessons/62048

✏️ 문제

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

🧠 접근

문제의 예시 그림에서 생각해야 할 것은 크게 두 가지입니다.

1) 빨간 사각형으로 표시된, 반복되는 사용 불가능 격자를 둘러싸는 조각의 개수. 2) 조각에서 사용할 수 없는 격자의 개수.

접근 1

예시의 그림을 상하 반전하고, 전체 직사각형의 왼쪽 아래 꼭짓점을 좌표평면의 원점이라고 가정하면 절취선은

y = ax (단, 0 ≤ a ≤ w)

와 같은 일차함수 형태가 됩니다. 그림으로 나타내면 아래와 같습니다. 그러면 조각의 개수는 0 < x ≤ w 일 때 (w는 전체 사각형의 가로 길이) x 와 y = ax 가 모두 자연수인 점의 개수가 됩니다.

# 나누어 떨어지는 단위를 찾음
while y <= h:
    x += 1
    y = h * x / w

    if y.is_integer():  # x 좌표와 y 좌표가 모두 정수이면 하나의 단위(조각)가 됨
        break

pieces = int(h / y)  # 나누어 떨어지는 조각 수 (예시 입력에서는 4개 조각)

접근 2

접근 1에서의 그림과 같이 절취선을 일차함수라고 할 때 x 값을 점차 증가시키면 격자와 만나게 됩니다. 이 때 격자와 만나는 점을 기준으로 사용할 수 없는 다음 정사각형과 만납니다. 하나의 조각 안에서 만나는 점을 직사각형 위에 표시하면 아래와 같습니다.

즉, 점의 개수는 다음 사용할 수 없는 정사각형으로 넘어가는 횟수이므로 작은 사각형에서 사용할 수 없는 정사각형의 개수는 (조각 내에서 절취선과 격자의 교점의 개수 + 1) 과 같습니다. 절취선과 격자의 교점은 x 나 y 의 값이 하나 이상 자연수인 점이므로 조각의 폭과 높이에서 각각 1을 뺀 값이 해당 점의 개수가 됩니다.

unable_parts = int(x - 1) + int(y - 1) + 1

예시에서 조각 내의 사용할 수 없는 정사각형의 개수는 (2 - 1) + (3 - 1) + 1 = 4가 됩니다.

마무리

접근 1에서 구한 '조각의 개수'와 접근 2에서 구한 '사용할 수 없는 정사각형'의 개수를 이용하면 사용할 수 있는 정사각형의 개수를 구할 수 있습니다.

answer = w * h - pieces * unable_parts

그런데 문제가 있다?

이 방법은 대부분의 상황에서 빠르지만 전체 직사각형의 한 변이 지나치게 길 경우, 가령 w = 100000000, h = 1일 때에는 조각의 개수를 찾는 방식의 특성상 조각의 크기가 하나 뿐이므로 직사각형 전체를 스캔해 매우 긴 시간이 소요되게 됩니다.

그러나 조각이 하나일 때에는 대각선이 전체를 가로지르므로 사용할 수 있는 정사각형의 개수가 0임을 쉽게 알 수 있습니다.

따라서 아래와 같이 예외 처리를 하여 문제를 해결하였습니다.

# w = 100000000, h = 1인 경우와 같이
# 한 축이 너무 길 때 시간 초과 방지
if w == 1 or h == 1:
    return 0

문제에 대해 검색해 보니 조각의 개수가 직사각형의 높이와 폭의 최대공약수라는 설명이 많았고 이 방법을 사용하면 상기한 문제가 발생하지 않지만, 왜 그런지 이해하기 힘들어 조금 더 직관적인 해결 방법을 찾게 되었습니다.

📄 전체 소스 코드

import math

def solution(w,h):
    x = 0
    y = 0

    # w = 100000000, h = 1인 경우와 같이
    # 한 축이 너무 길 때 시간 초과 방지
    if w == 1 or h == 1:
        return 0

    # 나누어 떨어지는 단위를 찾음
    while y <= h:
        x += 1
        y = h * x / w

        if y.is_integer():  # x 좌표와 y 좌표가 모두 정수이면 하나의 단위가 됨
            break

    pieces = int(h / y)  # 나누어 떨어지는 조각 수 (예시 입력에서는 4개 조각)
    ''' 
    하나의 단위공간에서 쓸 수 없는 정사각형의 수는 
    직사각형의 시작과 끝, 다음 조각으로 이어지는 점을 제외하고
    x = n 또는 y = n (n은 자연수) 을 만족하는 n의 개수 + 1과 같음
    '''
    unable_parts = int(x - 1) + int(y - 1) + 1
    answer = w * h - pieces * unable_parts

    return answer