[Java] 백준 1987 (알파벳) Gold 4

Problem : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net Approach 이미 지나온 알파벳은 지날 수 없는 DFS 문제이다. 이미 지나온 알파벳은 지날 수 없다는 것을 확인하기 위해 visited 배열과 더불어 alpha 배열을 따로 두었다. 풀이 방법은 다음과 같다. 좌측 상단(0, 0)에서 시작하여 DFS를 수행한다. DFS 를 수행하며 지나온 알파벳을 기록한다. 이미 지나온 알파벳이라면 그 칸으로는 더이상 탐색하지 않는다..

→2021.04.20

Algorithm/Baekjoon Online Judge

Head First: Design Patterns - 이터레이터 패턴(Iterator Pattern)

디자인 패턴: 이터레이터 패턴(Iterator Pattern) 이 포스팅은 Head First: Design Patterns 책을 보고, 개인적으로 정리한 포스팅입니다. Iterator Pattern 이란? 이터레이터 패턴(Iterator Pattern: 반복자 패턴)은 컬렉션 구현 방법을 노출시키지 않으면서도 그 집합체 안에 들어있는 모든 항목에 접근할 수 있게 해주는 방법을 제공해준다. 이 패턴을 이용하면 집합체 내에서 어떤 식으로 일이 처리되는지에 대해서 전혀 모르는 상태에서 그 안에 들어있는 모든 항목들에 대해 반복작업을 수행할 수 있다. 또한, 이터레이터 패턴을 사용하면 모든 항목에 일일이 접근하는 작업을 컬렉션 객체가 아닌 반복자 객체에서 맡게된다는 것이 중요한 점인데, 이는 집합체의 인터페이..

→2021.04.20

Algorithm/Baekjoon Online Judge

[Java] 백준 1967 (여행 가자) Gold 4

Problem : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net Approach 유니온 파인드(Union-Find) 를 활용한 문제였다. 플로이드 와샬 알고리즘으로도 풀이가 가능하다고 한다. (여기서는 다루지 않는다.) 주어진 여행 경로가 어떤 형식으로든 서로 연결되어 길이 존재한다면 가능한 여행경로라고 볼 수 있다. 따라서 입력데이터를 받아 도시 사이에 길이 있다면 같은 집합으로 묶는 작업을 진행한다. 그런 뒤에 여행경로에 있는 모든 도시들..

→2021.04.19

Algorithm/Baekjoon Online Judge

[Java] 백준 1967 (트리의 지름) Gold 4

Problem : https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net Approach 트리를 가장한 DFS/BFS문제이다. 트리의 지름은 가장 먼 두 노드 사이의 길이를 구하면 된다. 가장 먼 두 노드 사이의 길이는 다음과 같이 구할 수 있다. 임의의 점에서 가장 먼 노드 A를 구한다. A에서 가장 먼 노드 B를 구한다. A - B 사이의 길이가 가장 먼 두 노드 사이의 길이가 된다. 머릿속에서나 잠깐 생각해보면 쉽게 이해가 갈..

→2021.04.19

Algorithm/Baekjoon Online Judge

[Java] 백준 1918 (후위 표기식) Gold 4

Problem : https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net Approach Stack을 이용하여 풀이하는 문제이다. 입력으로 주어진 문자열을 하나씩 읽으면서 각 문자에 대해 우선순위를 매겨서 하나씩 뽑는 형태이다. 다음과 같이 4개의 경우가 발생한다. 참고로 스택엔 여는괄호와 연산자만 들어가게끔 구현한다. 스택의 문자들은 각각 우선순위가 매겨져 있으며, (가 0, +-가 1, */가 2로 숫자가 높을수록 우선이 된다. stack..

→2021.04.18

Algorithm/Baekjoon Online Judge

[Java] 백준 1937 (욕심쟁이 판다) Gold 3

Problem : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net Approach 어느 한 지점으로부터 시작하여 최대 몇개의 지점을 방문할 수 있는지를 판단하는 DFS문제이다. DFS는 인접행렬의 경우 O(n^2)의 시간복잡도를 가지고 있어, n의 크기가 크다면 모든 지점을 시작지점으로 하여 DFS하기에는 시간초과가 뜰 것이다. (O(n^2 * n^2)) 따라서 위와 같이 시간초과를 피하기 위하여, 모든 점을 시작지점으로 DFS를 수행..

→2021.04.18

Algorithm/Baekjoon Online Judge

[Java] 백준 1865 (웜홀) Gold 4

Problem : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net Approach 문제에서 음수 사이클이 있는지를 물어보기에, 당연스럽게 벨만-포드 알고리즘을 시도해봤다. 벨만-포드 알고리즘은 시간복잡도가 O(VE) 인데, 간선의 개수가 V^2에 근사할 수 있으므로 최대 O(V^3)의 시간복잡도를 가진다. 이는 다익스트라 알고리즘의 시간복잡도인 O(V^2)보다 크지만, 음수 사이클을 판별해야 하는 문제에서는 다익스트라를 사용할 수 ..

→2021.04.17

Algorithm/Baekjoon Online Judge

[Java] 백준 1799 (비숍) Gold 2

Problem : https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net Approach 백트랙킹(Backtracking) 문제이다. 시간제한 10초이고, 체스판의 크기가 n x n 이라고 하여, N-Queens 문제와 같이 백트랙킹을 시도하면 시간초과가 날 것이다. N-Queens 에서는 임의의 행에 퀸을 하나 놓았다면, 그 행의 다른 열에 대해서는 검사를 하지 않았기에 가능하였다. 하지만, 여기서는 체스판의 요소가 모두 1이고(모든 곳에 비숍을 놓을 수 있..

→2021.04.17

Algorithm/Baekjoon Online Judge

[Java] 백준 1202 (보석 도둑) Gold 2

Problem : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net Approach 우선순위 큐를 활용한 Greedy 문제이다. 접근법을 떠올렸다면 쉽게 구현할 수 있다. (PriorityQueue 이용하여) 먼저 보석과 가방을 각각 무게 기준 오름차순으로 정렬한다. 각 가방에 대하여 가방의 무게보다 작은 보석들을 pq에 넣는다. (pq는 보석의 가치 기준 내림차순의 우선순위를 가진다...

→2021.04.17

Algorithm/Baekjoon Online Judge

[Java] 백준 2098 (외판원 순회) Gold 1

Problem : https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net Approach 대표적인 외판원 문제 (TSP: Traveling Salesman Problem) 이다. 어떤 지점 A에서 모든 지점을 돌아 다시 A로 오는 최소 비용 경로를 찾으면 된다. (완전탐색) 시작 지점은 아무 곳에서 시작해도 된다. 어디서 시작하든 최소 비용 사이클은 동일하기 때문이다. 코드의 주석처럼 도시가 4개일 때, 1001이..

→2021.04.16

티스토리툴바