문제풀이
-
[백준]5582: 공통 부분 문자열 - JAVA문제풀이/백준 2021. 6. 1. 10:53
[백준]5582: 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 문제 이름에 맞게 "공통 부분 문자열"을 구하는 문제이다. LCS랑 비슷해 보이지만 약간 다르다. LCS는 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 것이고, 이 문제는 공통 부분 문자열 중에 가장 긴 수열을 찾는 것이다. 두 이론의 차이는 예를 들어 다음과 같다. str1이 ABC이고 str2가 AC일때 LCS를 구하면 2가되며 LCS는 ..
-
[백준]6479: 전력난 - JAVA문제풀이/백준 2021. 5. 31. 11:36
[백준]6479: 전력난 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 풀이 방향성이 없는 n개의 간선으로 연결된 m개의 노드 중에서 MST를 비용을 찾는 문제이다. MST를 찾아야 하는것은 맞지만 결과로 반환하는 값은 MST값이 아니다. 문제를 읽어보면 결국 최소 비용을 가질 수 있는 불이 켜진 길로만 이동할때 절약할 수 있는 최대 비용을 찾는것이다. 즉, 전체 비용에서 최소비용을 뺀 값이 우리가 구하려고 하는 값이 된다. 그러므로 prim이나 kru..
-
[백준]16234: 인구 이동 - JAVA문제풀이/백준 2021. 5. 30. 15:37
문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 구현 능력에 더불어 탐색 알고리즘을 활용할 수 있는지 묻는 문제이다. 구현 문제들은 문제가 길고 복잡한 경우가 많아 세분화 하여 구현해 주기 위해 먼저 어떤 순서대로 구현할지 작업을 분류하고 시작하는 것이 좋다. 나는 아래와 같은 순서로 구현해 주었다. 1. 순회를 하며 방문하지 않은 노드를 방문한다. 이 과정은 모든 노드를 방문할 때까지 반복된다. 2. 노드를 방문할 때..
-
[백준]13908: 비밀번호 - JAVA문제풀이/백준 2021. 5. 28. 13:03
[백준]13908: 비밀번호 https://www.acmicpc.net/problem/13908 13908번: 비밀번호 첫 번째 예제의 경우 가능한 비밀번호의 조합은 07, 17, 27, 37, 47, 57, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 87, 97이다. 두 번째 예제의 경우 가능한 비밀번호의 조합은 34, 43이다. www.acmicpc.net 풀이 이 문제의 입력 조건에서 n의 범위를 보면 1
-
[백준]17417: 게리맨더링 - JAVA문제풀이/백준 2021. 5. 26. 12:59
[백준]17417: 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 구현능력 + 완전탐색 + DFS/BFS 개념을 모두 활용해 볼 수 있는 문제이다. 우선, 문제의 조건을 구현 순서에 맞게 정리해보자. 지역에 두 개의 선거구 중에 하나를 할당한다. (1 또는 2로 표현) 나눠진 지역들이 두개의 구역으로 연결되는지 확인한다. (DFS/BFS 탐색으로 구함) 두 지역의 차이 값 중에서 최소값을 찾아준다. 하나하나씩 살펴보쟝. 1. 지역에 두 개의 선거구..
-
[백준]1516: 게임 개발 - JAVA문제풀이/백준 2021. 5. 25. 11:13
[백준]1516: 게임 개발 풀이 이전에 지어야할 건물들을 모두 건설하며 모든 건물을 짓는데 걸리는 시간을 반환하는 문제로 위상정렬 알고리즘을 활용하였다. 입력받는 정보는 진입간선이 되는 정보가 아닌, 진출간선이 되는 정보이므로 입력 받은 건물의 번호에 현재 건물 정보를 add해서 위상정렬 알고리즘을 사용할 수 있도록 적절하게 입력해 주었다. 각각의 건물들의 비용을 저장하는 cost, 각각의 건물을 완성하여 짓는데 걸리는 최소 비용 result, 진입 간선을 기록하는 indegree와 간선의 정보를 저장하는 list를 사용하였다. 건물을 짓는데 걸리는 총 비용을 계산하는 부분에서는 다음과 같이 계산해 주었다. result[next] = Math.max(result[next], result[currnet]..
-
[백준]5972: 택배 배송 - JAVA문제풀이/백준 2021. 5. 24. 10:53
[백준]5972: 택배 배송 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 출발지 헛간에서 목적지 헛간으로 가는 최소 거리를 찾는 문제로 다익스트라 알고리즘을 활용하여 풀었다. 다익스트라를 사용하여 출발지에서 다른 모든 헛간으로 가는 최소 거기를 찾아준 다음, 목적지까지의 거리를 반환해 주었다. 헛간 사이에는 방향성이 없으므로 헛간간의 거리를 입력받을때, 입력받는 두 개의 헛간에 모두 정보를 입력해 주었다. 또한 dist의 default값은 입력..
-
[백준]14719: 빗물 - JAVA문제풀이/백준 2021. 5. 21. 13:47
[백준]14719: 빗물 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 문제는 구현 문제로 쉽게 이해할 수 있는 문제였다. 빗물이 고이기 위한 조건들을 살펴보쟝. 아래와 같다. 현재 블록의 높이보다 높은 블록이 왼쪽에 있어야 한다. 현재 블록의 높이보다 높은 블록이 오른쪽에 있어야 한다. 첫, 마지막 블록에는 빗물이 고일 수 없다. 인덱스 별로 모이는 빗물의 정보를 더해준 다음 출력해주면 된다. 현재 인덱스를 기준으로 ..