전체 글

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차원으로 선언하였다.) 그 이외..
→2021.04.02
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회의..
→2021.04.02
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 어떤 작업을 해야할 때 선행되야 하는 작업이 있다면, 위상정렬도 한번 생각해 보는 것이 좋다. 대개 위와 같은 문제 유형이면, 위상정렬을 사용하는 문제인 것들이 많았다.(개인적인 생각) 이 문제도 마찬가지로 위상정렬로 풀이하였다. 위상정렬의 개념은 설명하지 않겠다. 위상정렬의 기본 구조를 크게 벗어나지 않았고, 응용하는 부분도 없기에 조금의 코드설명만 ..
→2021.03.31
Algorithm/Baekjoon Online Judge
[Java] 백준 1261 (알고스팟) Gold 4
Problem : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net Approach 이 문제의 기본 접근법은 갈 수 있는 곳 중 벽이 아닌 곳이 있으면 우선 그 쪽으로 가고, 갈 수 있는 곳이 벽인 곳밖에 없다면 벽을 뚫는다.이다. 이를 구현하는 데에는 여러 방법이 있겠지만, 나는 Deque+BFS, PriorityQueue+BFS 두 가지 방법으로 풀이를 해봤다. 두 방법 모두 풀이가 가능하다. 주의할 점은, 큐에 동일한 ..
→2021.03.31
Algorithm/Baekjoon Online Judge
[Java] 백준 1238 (파티) Gold 3
Problem : https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net Approach 단방향 그래프에서 자신에서 출발하여 자신으로 돌아오는 최단거리를 구하는 문제이다. 모든 정점에서의 최단거리를 구하여야 하므로 플로이드-와샬이 쉽게 떠오르겠지만, 이 문제의 입력 최대 크기가 1000이므로 시간복잡도가 O(N^3) 인 플로이드-와샬 알고리즘은 시간초과가 난다. 그래서 다익스트라를 응용하여 문제를 풀이하였다. 마을이 1 ..
→2021.03.30
Algorithm/Baekjoon Online Judge
[Java] 백준 1197 (최소 스패닝 트리) Gold 4
Problem : https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net Approach MST(Minimum Spanning Tree) 를 구하는 데에는 크게 Prim과 Kruskal알고리즘이 있다. 이 문제는 간단하게 위 두 알고리즘 중 하나를 택하여 구현만 하면 되는 문제였다. 간단한 로직만 설명하고, 자세한 내용은 다루지 않겠다. Prim알고리즘은 간선 중심 알고리즘이다. 간선을 오름차순으로 정렬한..
→2021.03.30
Book/Design Patterns
Head First: Design Patterns - 어댑터 패턴(Adapter Pattern)
디자인 패턴: 어댑터 패턴(Adapter Pattern) 이 포스팅은 Head First: Design Patterns 책을 보고, 개인적으로 정리한 포스팅입니다. Adapter Pattern 이란? 어댑터 패턴(Adapter Pattern)은 한 클래스의 인터페이스를 클라이언트에서 사용하고자 하는 다른 인터페이스로 변환한다. 어댑터를 이용하면 인터페이스 호환성 문제 때문에 같이 쓸 수 없는 클래스들을 연결해서 쓸 수 있다. 어댑터를 사용함으로써 클라이언트와 구현된 인터페이스를 분리시킬 수 있으며, 나중에 인터페이스가 바뀌더라도 그 변경 내역은 어댑터에 캡슐화되기 때문에 클라이언트는 바뀔 필요가 없다. 어댑티를 새로 바뀐 인터페이스로 감쌀 때는 객체 구성(Composition)을 사용한다. 이런 접근법을..
→2021.03.30
Algorithm/Baekjoon Online Judge
[Java] 백준 1167 (트리의 지름) Gold 3
Problem : https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net Approach BFS 나 DFS 를 사용하여 풀 수 있는 문제이다. 상식으로 접근하여 생각하면 쉽게 풀리는 문제였다. BFS나 DFS를 두번 수행하면 풀이가 가능한 문제이다. (나는 BFS를 사용했다.) 아무 정점을 시작으로 BFS를 수행하여 시작 정점으로부터 가장 먼 정점을 구한다. 그 정점을 기준으로 다시 BFS를 수행하여 가장 먼 정점까지의 거리가 트리의 ..
→2021.03.29
Algorithm/Baekjoon Online Judge
[Java] 백준 1043 (거짓말) Gold 4
Problem : https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net Approach union-find라는 알고리즘을 사용하는 문제였다. 같은 집합으로 묶는 개념이며 알고리즘에서 자주 사용하는 방법이므로 숙지해두면 좋다. 다른 union-find에서와 마찬가지로 parent[] 배열을 사용한다. 로직은 다음과 같다. 진실을 아는 사람들은 parent[x] = x로 초기화를 하고, 진실을 모르는 사람들은 parent[x] = -1로 초기화를 한다. 각 파티마..
→2021.03.29
Algorithm/Baekjoon Online Judge
[Java] 백준 1016 (제곱 ㄴㄴ 수) Gold 1
Problem : https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net Approach 에라토스테네스의 체 라는 소수 판별 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제이다.(주관적 생각) 개인적으로 나는 에라토스테네스의 체라는 알고리즘을 사용한다는 것을 바로 생각했고, 구현하는 데에도 큰 어려움이 있지 않았지만 Gold 1이라는 난이도가 매겨져있었다. 조건을 좀 따져야 하긴 한다. 조건을 먼저 살펴보자. (자료형은 무조건 long ..
→2021.03.28

• 이전
• 1
• ···
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• ···
• 34
• 다음