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

어려운 문제 풀이는 스스로 풀이하기 어렵다는 생각이 들어서, 일단 실버 5단계 문제부터 다시 차근차근 풀어보자!!

문제 제한 사항

시간 효율을 고려하지 않아도 될 정도로 넉넉한 문제인 것 같음.

문제 해결 아이디어

- 가로, 세로의 길이가 100인 흰색 도화지와 가로, 세로의 길이가 10인 검은색 색종이가 있다.

- 입력값은 다음과 같다.

색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리, 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리

- 첫번째 숫자의 오름차순으로 정렬이 필요하다.

- 숫자값들을 비교해가면서 값을 빼나가야 한다고 생각했다. => 수학적인 접근이 필요한 문제라고 생각했다.

- 근데 2차원 배열을 어떻게 활용해야 할까?라는 고민이 들면서 확어려워짐..

- 흰색 도화지만큼의 가로, 세로 길이가 100인 2차원 배열을 만든다.

- java는 2차원 배열을 초기화할 때, 별다른 값을 fill하지 않는 이상 false를 채워넣는다.

- 아직 아무런 색종이가 침범하지 않은 영역이라면 true로 변경하고, 넓이값++을 해준다.
여기서 처음엔 겹치는 부분을 구해서 빼줘야 겠다고 생각했는데 그냥 겹치지 않는 부분을 하나씩 더해주는 것도 하나의 방법이라는 걸 깨달았다.

- 만약 다른 색종이가 침범한 영역이라면 이미 true이기 때문에 더해지지 않고, 다음으로 넘어간다.

=> 최종 total의 값이 침범하지 않은 영역의 총합이 된다.

코드

public class Problem01 {
    public static void main(String[] args) throws IOException {
        Problem01 problem = new Problem01();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int total = 0;
        int n = Integer.parseInt(br.readLine());
        boolean[][] result = new boolean[101][101];
        boolean[][] mock = new boolean[3][3];

        for (int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            for (int j=x; j<x+10; j++) {
                for (int k=y; k<y+10; k++) {
                    if (!result[j][k]) {
                        result[j][k] = true;
                        total++;
                    }
                }
            }
        }
        System.out.println(total);
    }
}

배운점

문제 제한 사항

문제 해결 아이디어

맨하탄 거리 구하는 공식

(x1, y1)과 (x2, y2)가 있을 때 |x1-x2| + |y1-y2| 가 맨하탄 거리이다.

거리두기를 올바르게 지킨 경우는 두가지로 분리할 수 있다.

1. 맨하탄 거리가 3 이상일 경우

2. 맨하탄 거리가 2이지만, 파티션으로 막혀있는 경우

거리두기를 올바르게 지키지 않은 경우는

1. 맨하탄 거리가 1일 때

2. 맨하탄 거리가 2이고, 하나라도 빈 책상이 사이에 있는 경우

대기실별로 거리두기를 모두 지키고 있다면 1을, 한 명이라도 지키고 있지 않다면 0을 반환해야 한다.

존재하면 안되는 곳에 있는지만 체크하면 된다. 

안되는 예외 사항을 빠르게 발견해서 return 처리하면 답을 빠르게 구할 수 있을 줄 알았다.

근데 예외 사항이 생각보다 많았다. 일반적인 경우, 즉 일반식을 도출해서 구해야한다는 걸 깨달았다.

코드

input과 같은 2차원 배열을 또 다른 하나의 2차원 배열로 나눌때 사용되는 코드 템플릿

String[][] input = {
    {"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"},
    {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"},
    {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"},
    {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"},
    {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}
 };


// 위와 같은 2차원 배열인데, 또 저기서 나눠줘야 할 때
for (int i=0; i<input.length; i++) {
    String[] place = input[i];
    char[][] room = new char[place.length][];
    for (int j=0; j<room.length; j++) {
        room[j] = place[j].toCharArray();
    }
 }

배운점

너무 오랜만에 코딩테스트 문제를 푸니깐 생각하기가 귀찮아진다.ㅜ,, 아직까지 다시 어떻게 시작해야하는지 감이 안와서 고민하는 시간을 가지고 결국엔 정답 보는 흐름대로만 풀고 있는데, 계속해서 도전은 해봐야할 것 같다.

링크

https://school.programmers.co.kr/learn/courses/30/lessons/68645

문제 제한 사항

정수 n이 매개변수로 주어지고, 최소 1 이상이고 최대10^3 이다.

최대 시간 복잡도는 O(N^2)이다. 

문제 해결 아이디어

n=4 이고, 블록에 들어가는 숫자를 e라고 지칭할 때

e=1 , n=1

e=2, n=2

e=3, n=3

e=4, n=4

e=5, n=4

e=6, n=4

e=7, n=4

e=8, n=3

e=9, n=2

e=10, n=3

위와 같이 들어가게 된다.

처음에는 n값과 e값이 동일하게 증가하다가,

마지막 층인 n이 4일 때, 4개의 블럭이 다 찰 때까지 연속으로 숫자를 넣어준다.

그리고 e값은 증가하면서 다시 블럭이 다 안 찬 층을 찾으면 숫자를 바로 넣어주는 형식이 된다.

멤버변수로 자신의 n값과 어떤 값이 들어가는지 Integer 리스트를 멤버변수로 가질 수 있도록 하려고 했다.

 private static class Level {
    public int n;
    public List<Integer> elements;

    public Level(int n) {
        this.n = n;
        this.elements = new ArrayList<>();
    }
}

연속된 숫자와 맨마지막 구간에서 차례대로 숫자를 넣는 부분까지는 구현하기 쉬웠으나, 그 이후 순서부터 조금씩 꼬이기 시작했다.

코드

> 기존 코드(오답) .. 너무 별로인 코드ㅜ

조건 처리하는 데 예외 사항에 대한 처리가 명확하지 않았고,

'층 수가 줄어드는 경우 / 층 수가 증가하는 경우 / 층 수가 유지되는 경우'에 대한 조건을 마구잡이 형식으로 넣어줘서 정답이 제대로 나오지 않았다.

논리 단위로 동작 흐름을 나누는 부분에 대해 부족하게 느껴졌다.

    private static class Level {
        public int n;
        public List<Integer> elements;
        public boolean canPutElement;

        public Level(int n) {
            this.n = n;
            this.canPutElement = true;
            this.elements = new ArrayList<>();
        }

        private void addAllElements(int elementNum) {
            int number = elementNum;
            while (elementNum <= number + (number-1)) {
                elements.add(elementNum++);
            }
            this.canPutElement = false;
        }

        private void addElement(int elementNum) {
            if (canPutElement) {
                elements.add(elementNum);
                if (elements.size() == n) {
                    canPutElement = false;
                }
            }
        }
    }


public static void main(String[] args) {
//        int n = 4;
        int n = 5;
//        int n = 6;

        Map<Integer, Level> levelMap = new HashMap<>();

        for (int i=1; i<=n; i++) {
            Level level = new Level(i);

            if (i==n) {
                level.addAllElements(i);
            } else {
                level.addElement(i);
            }

            levelMap.put(i, level);
        }

        int flag = n-1;
        for (int element=2*n; ; element++) {
            Level level = levelMap.get(flag);
            if (flag == n && !level.canPutElement){
                break;
            }

            if (flag == n) {
                level.addElement(element);
                continue;
            }

            if (level.canPutElement) {
                level.addElement(element);
                flag--;
            } else {
                flag++;
                level = levelMap.get(flag);
                level.addElement(element);
            }
        }

        for (Level level : levelMap.values()) {
            System.out.println(Arrays.toString(level.elements.toArray()));
        }
    }

> 정답은 다른 블로그에 찾아보면 많이 나오기 때문에 따로 첨부하지는 않으려고 한다.

배운점

시작한지 얼마 되지 않아서, 일단 지금 형식처럼 풀어보고 기록하려고 한다. 

계속 연습해서 코딩테스트 준비에 차질이 없도록 해야겠다.

링크

https://school.programmers.co.kr/learn/courses/30/lessons/87377

문제 해결 방식

[제한 사항]

2 <= line의 행 길이 <= 10^3  ➡ 시간 복잡도는 O(n^2) 이하여야 한다.

line의 열 길이 = 3 

행의 형식은 (A, B, C) => Ax + By + C = 0

행의 원소는 정수이며, -10^4 이상 10^4 이하

별이 한 개 이상 그려지는 입력만 주어진다.

문제 해결 아이디어

Ax + By + C = 0

Dx + Ey + F = 0 이 있다고 가정할 때,

1. -B/A와 -D/E가 다르다면 기울기가 다르기 때문에 교점이 한 개 발생할 수 있다.

2. 교점 좌표를 구하는 공식은 x = (BF-EC)/(AE-DB), y = (DC-AF)/(AE-DB) 이다.

3. 정수 좌표라면 저장하고, 아니라면 건너뛴다.

4. 저장된 좌표 중에서 x의 최댓값과 y의 최댓값을 저장해야 한다.

코드

교점을 구하는 과정

ArrayList<Point> points = new ArrayList<>();
    for (int i=0; i< lines.length; i++) {
	    for (int j=i+1; j< lines.length; j++) {
			Point intersection = intersection(lines[i][0], lines[i][1], lines[i][2],
                                                lines[j][0], lines[j][1], lines[j][2]);
			if (intersection != null) {
     	       points.add(intersection);
            }
        }
    }

private Point intersection(long a1, long b1, long c1, long a2, long b2, long c2) {
    double x = (double) (b1 * c2 - b2 * c1) / (a1 * b2 - a2 * b1);
    double y = (double) (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);

    if (x % 1 != 0 || y % 1 != 0) {
        return null;
    }
    return new Point((long)x, (long)y);
}

별점을 찍는 코드

Point minimum = getMinimumPoint(points);
Point maximum = getMaximumPoint(points);

int width = (int) (maximum.x - minimum.x + 1);
int height = (int) (maximum.y - minimum.y + 1);

char[][] arr = new char[height][width];
for (char[] row : arr) {
    Arrays.fill(row, '.');
}

for (Point p : points) {
   int x = (int) (p.x - minimum.x);
   int y = (int) (maximum.y - p.y);
   arr[y][x] = '*';
}

String[] result = new String[arr.length];
for (int i=0; i<result.length; i++) {
    result[i] = new String(arr[i]);
}
return result;

배운 점

너무 오랜만에 하는 거라, 구현 능력이 많이 떨어진다는걸 알게 되었다.

기울기가 다른지 굳이 더블체크할 필요가 없었다. 교점만 체크하면 되기 때문에 궁극적으로 구해야하는 부분, 구해야 하는 값을 위해 최소한으로 계산을 해야하는 부분만 체크해야 한다.

미리 코드의 템플릿을 만들어둬야겠다.

카카오 코테를 풀어보면서, DFS로 인해 복잡한 코드를 비트마스크를 통해서 간단하게 구현한 코드를 보게 되었습니다.
이전에 알고리즘 스터디를 할 때 스터디원 한 분이 비트마스크를 활용해서 풀었다고 했을 때, 배워봐야지 생각은 했는데 이제서야 학습하네요. 처음 개념 공부를 할 때에는 블로그를 찾기보다는 책으로 공부하는 편이기 때문에 '알고리즘 문제 해결 전략' 책을 읽고 정리한 것입니다.
처음 읽었을 때 이해가 안되서 두 번 계속 읽어본 결과, 여전히 낯설고 어려운 개념입니다 ㅎ
초반에는 읽고 바로 기초 문제들을 풀 수 있겠지 싶어서 호기롭게 도전했는데, 쉽지가 않네요..
아직도 약간은 기초 문제를 풀기조차 힘든 부족한 부분이 있는 것 같아요.
그래서 일단 정리를 해두고 다음주(~2023.03.21)까지의 목표는 비트마스크 문제를 집중적으로 공략해보기로 정했어요.

개념 정리

비트마스크의 도입 배경

현대의 모든 CPU는 이진수를 이용하여 모든 자료를 표현합니다.
덕분에 내부적으로 이진법 관련 연산을 빠르게 할 수 있는데요. 이런 특성을 활용해서 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 부릅니다.

비트마스크를 도입함으로써 얻을 수 있는 장점에는,
1. 더 빠른 수행 시간
비트마스크 연산은 O(1)에 구현되는 것이 많습니다. 그래서 적절히 사용한다면, 훨씬 빨리 동작할 수 있어요.
그러나, 비트마스크를 사용할 수 있다는 건 원소의 수가 많지 않다는 뜻이기 때문에 눈에 띄는 속도 향상을 기대할 수는 없다고 합니다.
비트마스크 연산을 굉장히 여러 번 수행해야 할 경우에는 작은 최적화도 큰 속도 향상을 가져올 수 있습니다.
저는 이 부분에서 비트마스크 연산은 원소의 수가 많지 않을 때 사용할 수 있다는 인사이트를 얻을 수 있었습니다.

2. 더 간결한 코드
3. 더 작은 메모리 사용량
4. 연관 배열을 배열로 대체
이렇게 4가지의 장점을 제시할 수 있어요.

비트 마스크 용어 정리

비트(bit)란 이진수의 한 자리 말합니다. 

비트는 0 혹은 1의 값을 가질 수 있고, 컴퓨터가 표현하는 모든 자료의 근간이 됩니다.

부호없는 8비트 정수형은 8자리의 이진수로서 표시할 수 있는 모든 정수를 표현할 수 있습니다.

최소값(0)부터 최대값(1111 1111(2) = 255)까지 값을 가질 수 있습니다. 

위의 부호없는 8비트 정수형 예시처럼, 부호 없는 N비트 정수형 변수는 N자리의 이진수로 사용할 수 있습니다. 

각 비트가 표현하는 값은 맨 오른쪽부터 2^0 ~ 2^(n-1)까지입니다. 

2^(n-1)에 해당하는 비트를 최상위 비트(MSB, Most Significant Bit)라고 부르고,

2^0에 해당하는 비트를 최하위 비트(LSB, Least Significant Bit)라고 부릅니다.

정수를 이진수로 표현했을 때, 비트의 위치가 1이라면 해당 비트가 "켜져있다"라고 말하고,

비트의 위치가 0이라면 해당 비트가 "꺼져있다"라고 말합니다. 

비트 연산자(AND, OR, XOR, NOT, 시프트)

두 정수 변수(a,b)를 비트별로 조작할 수 있는 비트 연산자를 사용해야 합니다.

AND는 모두 켜져있을 때만(=비교하는 비트들이 모두 1일 때만) 결과로 나타낼 비트를 킵니다. - a & b

OR은 두 비트 중 하나라도 켜져 있을 때만(=비교하는 비트들 중 최소 하나가 1일 때만) 비트를 킵니다. - a | b

XOR은 하나는 켜져있고, 하나는 꺼져있는 특수한 상황에서 비트를 킵니다. - a ^ b

NOT은 꺼져있는 비트는 켜고, 켜져있는 비트는 끕니다(1 -> 0, 0 -> 1) - ~a

시프트(shift)는 정수 a의 비트들을 왼쪽 또는 오른쪽으로 c비트만큼 움직입니다.

그래프란? 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조를 말한다.

G = (E,V)라고 표현할 수 있다. 아래는 그림으로 노드(정점)와 간선을 나타낸 그림이다.

그래프는 인접행렬과 인접리스트로 구현 가능하며 이번 게시글에서는 인접행렬로 구현한 그래프에 대해서 설명할 것이다. 인접행렬이란 2차원 배열과 동일하다고 보면 된다.

노드의 개수가 많을수록 인접리스트로 구현하는 것이 효율적이다.

그래프의 종류에는 (1)무방향 그래프, (2)방향 그래프, (3)가중치 방향 그래프 가 있다.

(1) 무방향 그래프 - 이동하는 방향이 정해져 있지 않다.

이동하는 방향이 정해져 있지 않아서,

'1에서 2로' 라고 말할 수 있고, '2에서 1로' 라고도 말할 수 있다.

이 그래프에서 연결된 케이스를 모두 적어본다면 아래와 같다.

1 - 2

1 - 3

2 - 4

2 - 5

3 - 4

이를 그래프 인접행렬(2차원 배열)에 넣는다면 왼쪽의 그림에서 확인할 수 있다. graph[a][b] = 1은 노드a와 노드b가 연결되어있다는 것을 의미하게 된다. 반대로 값이 0이라면 연결되어 있지 않다는 것을 의미한다. 

노드a와 노드b를 연결한 간선 정보를 담기 위해서는,

graph[a][b] = 1

graph[b][a] = 1 

위의 코드들을 구현해줘야 한다. 

(2)방향 그래프 - 이동하는 방향이 정해져 있다.

이동하는 방향이 정해져있기 때문에 지정된 방향으로만 이동이 가능하다. 연결된 이동 경로의 케이스를 모두 적으면 아래와 같다.

1 - 2

1 - 3

2 - 5

3 - 4

4 - 2

설명은 무방향 그래프와 동일하고, 다른 점이 있다면 지정한 방향에 대해서만 연결이 가능하다.

노드a와 노드b를 연결한 간선 정보를 담기 위해서는,

graph[a][b] = 1

한 줄의 코드만 구현하면 된다.

(3) 가중치 방향 그래프

방향 그래프에서 이동에 대한 가중치가 더해진 그래프이다.

연결된 이동 경로의 케이스에서 가중치 정보를 더해주면 된다.

1 - 2 : 2 (이동경로 : 가중치)

1 - 3 : 4

2 - 5 : 5

3 - 4 : 5

4 - 2 : 2

방향 그래프와 설명이 동일하다.

노드a와 노드b를 연결한 가중치 c인 간선의 정보를 담기 위해서는

graph[a][b] = c

와 같은 코드를 구현하면 된다.

BFS는 층별로 탐색을 한다. 각 층을 탐색하면서 말단 노드인 것을 확인하면 탐색하던 층을 반환한다. 그래서 DFS보다 최단 거리를 찾는 것에 더 효율적인 것이다.

이전 글에서 설명을 충분히 했다고 여겨서 바로 코드로 구현해볼 것이다.

말단 노드란 어떠한 자식 노드도 없는 노드를 말한다. 

보통 최단 거리, 경로를 찾는 문제는 BFS를 사용하는 것이 좋다. 그러나 DFS와 BFS를 배우는 입장에서 이번 게시물은 DFS를 사용해서 가장 짧은 경로를 구해볼 것이다.

먼저 왼쪽의 트리로 DFS와 BFS를 비교해보자면,

DFS의 경우에는,

자식노드가 null일 때까지 거리를 1씩 더해가면서 재귀함수를 호출한다. 말단노드에 이르면 거리를 반환한다. 이 때 재귀함수에서는 반환된 거리 중 최솟값을 반환하게 구현한다. 

BFS의 경우에는,

이전 게시물에서도 언급했듯이 층별로 자식노드가 null인 노드를 찾아서 바로 반환하기 때문에 DFS보다 더 효율적으로 문제를 해결할 수 있다.

이제 Tree말단 노드까지의 가장 짧은 경로를 DFS코드로 구현할 것이다.

재귀 함수의 종료 조건은 말단 노드인 경우이다.(왼/오른쪽 자식 노드가 모두 없는 경우에 종료된다)

스택 프레임을 그려서 DFS 작동방식을 더 깊게 알아볼 것이다.