BOJ

    [Java] 백준 1261 (알고스팟) Gold 4
    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 두 가지 방법으로 풀이를 해봤다. 두 방법 모두 풀이가 가능하다. 주의할 점은, 큐에 동일한 ..

    [Java] 백준 1238 (파티) Gold 3
    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 ..

    [Java] 백준 1197 (최소 스패닝 트리) Gold 4
    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알고리즘은 간선 중심 알고리즘이다. 간선을 오름차순으로 정렬한..

    [Java] 백준 1167 (트리의 지름) Gold 3
    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를 수행하여 가장 먼 정점까지의 거리가 트리의 ..

    [Java] 백준 1043 (거짓말) Gold 4
    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로 초기화를 한다. 각 파티마..

    [Java] 백준 1016 (제곱 ㄴㄴ 수) Gold 1
    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 ..

    [Java] 백준 1005 (ACM Craft) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1005 (ACM Craft) Gold 3

    Problem : https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net Approach 위상정렬(Topological Sort)의 연습문제이다. 위상정렬 자체에 대해서는 간단히 설명하겠다. 알고리즘에서 꽤나 자주 나오는 개념이므로 숙지해두면 좋을 것이다. DAG(Directed Acyclic Graph: 방향성이 있고 싸이클이 없는 그래프)에 순서가 곁들여져 있는 경우, 위상정렬을 사용해 볼 수 있다. 위상정렬에서는 중요한 개념 하나가 있다. ..

    [Java] 백준 1107 (리모컨) Gold 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1107 (리모컨) Gold 5

    Problem : https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net Approach BruteForce 문제이다. 우선 0부터 목표 채널 * 2 까지 만들 수 있는 숫자인지를 판단하고, 만들 수 있는 숫자라면, 숫자를 만들 때의 클릭 수와 만든 숫자와 목표 채널과의 차이(+-클릭 수)를 더한 것들 중 최솟값을 찾으면 된다. 주의할 점은, 시작 채널이 100이기 때문에 최소 100까지는 숫자를 만들 수 있는지 판단해야 한다. isP..

    [Java] 백준 3344 (N-Queen) Platinum 5
    Algorithm/Baekjoon Online Judge

    [Java] 백준 3344 (N-Queen) Platinum 5

    Problem : https://www.acmicpc.net/problem/3344 3344번: N-Queen 첫째 줄에 N이 주어진다. N은 8, 26, 213, 2012, 99991, 99999중 하나이다. www.acmicpc.net Approach 일반적인 Backtracking 으로 풀면 시간초과가 난다. 입력의 크기가 최대 99999이고, 백트랙킹 기법은 시간복잡도가 O(N^2)이기 때문이다. 나도 구글링 중에 알아낸 풀이법으로, N-Queens의 규칙을 찾아 그대로 구현하는 문제였다. 솔직히 아직 완벽히 이해하진 못했다. 자세한 알고리즘은 밑의 링크에 Existence of solutions 탭을 확인하시면 좋을 것 같다. https://en.wikipedia.org/wiki/Eight_qu..

    [java] 백준 10266 (시계 사진들) Platinum 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 10266 (시계 사진들) Platinum 5

    Problem : https://www.acmicpc.net/problem/10266 10266번: 시계 사진들 상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바 www.acmicpc.net Approach KMP 알고리즘의 실패함수(Failure Function)를 연습할 수 있는 문제이다. KMP 알고리즘의 자세한 내용은 다음 링크를 참조하면 좋을것이다. https://bowbowbow.tistory.com/6#comment5168448 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 ..

티스토리툴바