BOJ

    [Java] 백준 13460 (구슬 탈출 2) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 13460 (구슬 탈출 2) Gold 2

    Problem : https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net Approach 삼성 SW 역량테스트 문제라고 한다. 삼성에서는 이런 구현(시뮬레이션) 문제를 많이 내는 것 같다. BFS 를 사용하여 구현하였다. 이 때 visited 배열이 4차원 배열인 것을 주의하자. visited[blueX][blueY][redX][redY] 의 형태로 구성하였다. 일단 입력 데이터를 처리하면서, 초기 파..

    [Java] 백준 1766 (문제집) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1766 (문제집) Gold 2

    Problem : https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net Approach 위상정렬 + PriorityQueue 를 활용한 문제이다. 위상정렬을 알고 있다면 꽤 쉬운 문제이다. 문제를 풀이하는데 있어 순서가 존재하므로 위상정렬을 떠올릴 수 있었다. 또한, 지금 풀 수 있는 문제가 여러개일 때, 번호가 작은 문제부터 풀어야 하므로 우선순위 큐를 생각할 수 있겠다. 입력을 모두 받을 때까지 inDegree 배열..

    [Java] 백준 12100 (2048 Easy) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 12100 (2048 Easy) Gold 2

    Problem : https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net Approach BruteForce + 단순 구현 문제이다. break 문을 적절하게 넣어서 시간을 절약할 수 도 있겠지만, 그냥 4x4x4x4x4 = 1024 가짓수의 경우를 모두 검사하였다. 배열을 각각 왼쪽, 오른쪽, 위쪽, 아래쪽으로 미는 작업을 하는 메소드를 정의한 뒤, 4방향 중 중복허용하여 5가지 방향을 뽑아 적용하면 된다. 최대 크기 블..

    [Java] 백준 1774 (우주신과의 교감) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1774 (우주신과의 교감) Gold 4

    Problem : https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net Approach MST(Minimum Spanning Tree) 를 응용한 문제이다. 이미 사용된 간선이 존재할 때, 나머지 간선들로 MST를 구성하면 된다. 나는 크루스칼 알고리즘을 사용하였다. 이미 사용된 간선들을 union으로 묶은 뒤, 간선의 길이가 작은 것부터 PQ에서 꺼내 연결하였다. 연결할 때마다 res 변수에 간선의 길이를 저장했고, 모두..

    [Java] 백준 1717 (집합의 표현) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1717 (집합의 표현) Gold 4

    Problem : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net Approach Union-Find(Disjoint Set) 알고리즘을 사용한 기본 문제이다. 유니온파인드를 구현이 다인 문제이다. 입력의 처음이 0 인 경우, union 메소드를 적용하여 하나의 집합으로 묶는다. 입력의 처음이 1 인 경우, 두 숫자의 부모를 검사하여 같은 집합인지를 판단한다. Code import java.io.*; i..

    [Java] 백준 1647 (도시 분할 계획) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1647 (도시 분할 계획) Gold 4

    Problme : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net Approach MST(Minimum Spanning Tree) 의 개념을 응용한 문제이다. MST를 적용한 그래프는 임의의 두 점 사이를 연결하는 경로는 유일하다. 따라서, 그 중 하나의 간선을 제거하면 MST 가 2개로 분리된다. (분리된 각 그래프도 MST이다.) 먼저 MST를 적용한다. (Prim or Kruskal 을 사용하면 된다...

    [Java] 백준 9527 (1의 개수 세기) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 9527 (1의 개수 세기) Gold 2

    Problem : https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net Approach Java에는 Integer.bitCount() 이라는 내장 라이브러리 함수가 있다. 인자로 받은 숫자를 이진수로 나타냈을 때, 1의 개수를 리턴해준다. 이 문제에서는 시간초과가 나서 사용할 수 없지만, 이런 함수도 있긴 하다. 이 문제는 은근히 찾기 힘든 규칙이 존재한다. bit[i]를 i번째 비트까지 모두0인 숫자(0)부터 i번째 비트까..

    [Java] 백준 1600 (말이 되고픈 원숭이) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1600 (말이 되고픈 원숭이) Gold 5

    Problem : https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net Approach BFS 문제이다. 일반적인 BFS 에 이동할 수 있는 추가적인 방향과 이 추가적인 방향을 사용하는데에 있어 제한을 두는 약간의 제약이 추가되었다. 문제에서 언급하는 말 이동은 횟수제한이 있으므로, 해당 지점에 말 이동을 몇 번 사용하여 최소 이동으로 도착하였는지를 저장하여야 한다. (이 때문에 visited 배열을 3차원으로 선언하였다.) 그 이외..

    [Java] 백준 1517 (버블 소트) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1517 (버블 소트) Gold 1

    Problem : https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net Approach 버블 소트를 가장한 머지 소트 문제이다. Merge Sort를 구현하면서 Bubble Sort를 했을 때와 Swap의 관계를 찾아야 한다. 4 5 1 2 를 머지소트를 한다고 가정하자. left = 0, right = 3, mid = 1, [4, 5]의 인덱스 i = 0, [1, 2]의 인덱스 j = 0 이라 할 때, [1 2 4 5] 를 만드려면 4회의..

    [Java] 백준 1516 (게임 개발) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1516 (게임 개발) Gold 3

    Problem : https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net Approach 어떤 작업을 해야할 때 선행되야 하는 작업이 있다면, 위상정렬도 한번 생각해 보는 것이 좋다. 대개 위와 같은 문제 유형이면, 위상정렬을 사용하는 문제인 것들이 많았다.(개인적인 생각) 이 문제도 마찬가지로 위상정렬로 풀이하였다. 위상정렬의 개념은 설명하지 않겠다. 위상정렬의 기본 구조를 크게 벗어나지 않았고, 응용하는 부분도 없기에 조금의 코드설명만 ..

티스토리툴바