Algorithm/Baekjoon Online Judge

    [Java] 백준 12886 (돌 그룹) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 12886 (돌 그룹) Gold 5

    Problem : https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net Approach DFS를 사용하여 풀이한 문제이다. BFS로도 풀이가 가능한 것 같다. 새로 만든 숫자와 기존 숫자를 이용하여야 하기 때문에 DFS가 먼저 생각이나서 DFS로 풀이하였다. 먼저 처리할 수 있는 예외를 보자. (a + b + c) % 3이 0이 아니라면 세 숫자를 어떻게 선택하더라도, 서로 같게 만들 수 없다. 문제 풀이 로직은 다음과 같다. 숫자 a, b, c..

    [Java] 백준 14502 (연구소) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 14502 (연구소) Gold 5

    Problem : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net Approach 완전탐색(BruteForce)과 BFS를 함께 사용하는 문제이다. 문제 풀이 주요 로직은 다음과 같다. 0인 곳들 중 3군데를 골라서 벽을 세운다. 벽을 3개 세웠으면 그 상태에서 BFS를 수행하여 바이러스를 전파시킨다. 전파 시킨 뒤에 0의 개수를 찾는다. 모든 경우를 다 탐색하여, 안전한 구역의 최대 개수를 구한다. Code import java.io.*; import j..

    [Java] 백준 6087 (레이저 통신) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 6087 (레이저 통신) Gold 4

    Problem : https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net Approach BFS + DP 문제라고 볼 수 있다. 특정 위치 (x, y)를 방문하는 방법은 여러 방법이 있는데, 그 중 방향 전환을 최소로 하는 방문을 찾는 문제이다. 문제에서 거울이라는 개념이 나오는데, 쉽게 말하여 방향이 변하는 곳엔 거울을 놓을 수 밖에 없다. 따라서, 목표 위치 (x, y)를 방문하는 방법 중, 방향 전환이 최소인 방문을 찾으면 된다. cha..

    [Java] 백준 1963 (소수 경로) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1963 (소수 경로) Gold 4

    Problem : https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net Approach 소수를 찾는 알고리즘과 BFS 개념으로 풀 수 있는 문제이다. 문제 풀이의 주요 로직은 다음과 같다. 먼저 간단하게 에라토스테네스의 체 개념을 이용하여 1 ~ 9999 사이의 숫자들 중 소수를 판별한다. 그리고 난 뒤 현재 숫자에서 숫자 하나만 변경하며 BFS를 수행한다. 숫자를 하나씩 바꾸는 부분을 구현하는게 꽤 까다로울 수 있다. String을 사용할까도 생각해봤지만,..

    [Java] 백준 14395 (4연산) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 14395 (4연산) Gold 5

    Problem : https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net Approach BFS문제이다. 하지만 배열을 사용하여 풀이한다면, 메모리초과를 만날 것이다. Set 에 방문한 곳들만 추가하여, 메모리를 절약하여야 한다. 이것이 가능한 이유는 1 ~ t범위 안에 실제로 방문할 수 있는 숫자는 전체 숫자 대비 몇개 안되기 때문이다. 문제 풀이에 앞서 입력에 따라 간단히 처리할 수 있는 부분과, 필요한 로직을 단순화 시켜보자. s == t..

    [Java] 백준 1062 (가르침) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1062 (가르침) Gold 4

    Problem : https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net Approach 조합(Combination)을 이용한 완전탐색(BruteForce)문제이다. 처음에는 조합을 list로 구현하였으나, 시간초과를 받았다. 그래서 총 알파벳의 개수인 26 크기의 배열을 가지고 사용 여부를 체크하며 조합을 구성하였다. 조합을 구현하기 전에 입력에 따라 간단히 처리할 수 있는 부분들을 짚어보자. N은 주어진 단어의 개수, K개 만큼 문자를 배울..

    [Java] 백준 16198 (두 동전) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16198 (두 동전) Gold 4

    Problem : https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net Approach 백트랙킹(Backtracking)을 이용한 완전탐색(BruteForce)문제 이다. BFS로도 풀이가 가능할 것 같다. 먼저 두개 동전의 위치를 찾는다. (입력으로 map을 구성하면서 찾을 수 있다.) 그리고 다음 작업을 반복한다. 두 동전을 상하좌우 방향으로 굴려본다. 굴렸을 때 3가지 상황이 발생한다. 두 동전이 모두 떨어지면 더 이상 굴려보지 않는다. (돌..

    [Java] 백준 2250 (트리의 높이와 너비) Gold 2
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2250 (트리의 높이와 너비) Gold 2

    Problem : https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net Approach 트리에서의 순회 문제였다. 문제만 보고는 순회를 생각하기에 어려웠다. 짜놓고 보니 중위순회 였다는 느낌. 주의할 점은 루트 노드가 항상 1인 것은 아니라는 점이다. 따라서 루트 노드를 찾는 과정이 포함되어야 한다. levelMin[i] 는 레벨 i에서의 가장 왼쪽 노드의 인덱스이다. levelMax[i] 는 레벨 i에서의 가장 오른쪽 노드의 인덱..

    [Java] 백준 16940 (BFS 스페셜 저지) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16940 (BFS 스페셜 저지) Gold 4

    Problem : https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net Approach 그래프 정보와 BFS 방문 순서가 주어졌을 때, 주어진 방문 순서가 유효한지를 판단하는 문제이다. 현재 노드 기준으로, 방문하지 않은 인접한 노드들을 모두 set에 넣는다. 그리고 다음 방문 순서가 올바른 BFS 순서인지를 판단한다. 주어진 방문 순서의 끝까지 검사하며, 다음 방문 순서가 set에 없다면 올바르지 않은 방문 순서인 것이다. 주의할 점은, 주어진 방문 순서가 1부터 시작하는지를 검사하여 예외처리를 해주어야 한다. (시작점이 1이라고 가정하고 문제를 푸는데, 주어진 ..

    [Java] 백준 16964 (DFS 스페셜 저지) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 16964 (DFS 스페셜 저지) Gold 5

    Problem : https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net Approach 그래프 정보와 DFS 방문 순서가 주어졌을 때, 주어진 방문 순서가 유효한지를 판단하는 문제이다. 현재 노드 기준으로, 방문하지 않은 인접한 노드들을 모두 set에 넣는다. 그리고 다음 방문 순서가 올바른 DFS 순서인지를 판단한다. 주어진 방문 순서의 끝까지 검사하며, 다음 방문 순서가 set에 없다면 올바르지 않은 방문 순서..

티스토리툴바