분류 전체보기
-
[백준]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 풀이 문제는 구현 문제로 쉽게 이해할 수 있는 문제였다. 빗물이 고이기 위한 조건들을 살펴보쟝. 아래와 같다. 현재 블록의 높이보다 높은 블록이 왼쪽에 있어야 한다. 현재 블록의 높이보다 높은 블록이 오른쪽에 있어야 한다. 첫, 마지막 블록에는 빗물이 고일 수 없다. 인덱스 별로 모이는 빗물의 정보를 더해준 다음 출력해주면 된다. 현재 인덱스를 기준으로 ..
-
[백준]16174: 점프왕 쩰리 - JAVA문제풀이/백준 2021. 5. 20. 11:20
[백준]16174: 점프왕 쩰리 https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 풀이 약간 변형된 BFS문제로 탐색을 하면서 오른쪽, 아래 방향 중에서 이동할 수 있는 방향으로 점프할 수 있는 칸 만큼 점프하며 이동한다. 최소 값을 구하는 것이 아니기 때문에 DFS, BFS, 브루트포스 등 다양하게 풀 수 있다. 이동할 수 있는 방향 만큼 이동할 수 있다면 큐에 담아 이동하도록 구현하였다. 한 번 이동할 때마다 점프를 해서 이동하기 때문에 중간에 ..
-
[백준]1013: Contact - JAVA문제풀이/백준 2021. 5. 19. 14:20
[백준]1013: Contact https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 풀이 이번 문제는 문자열 중에서도 정규식을 잘 알고있는지에 대한 문제이다. 나는 이전에 프로그래머스의 "불량사용자" 문제를 풀면서 정규식을 처음 접했고, 공부했기 때문에 어렵지 않게 접근할 수 있었다. 정규식을 사용하지 않고도 풀 수 있겠지만 정규식을 사용하는 것이 훨씬 간편하당. 이 문제에서 사용된 정규 표현식을 간단하게 정리해보자. str.matche..
-
[백준]11779: 최소비용 구하기2 - JAVA문제풀이/백준 2021. 5. 17. 14:45
[백준]11779: 최소비용 구하기2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 최소 비용을 구하면서, 최소 비용 경로까지 함께 구하는 문제였다. 출발 노드가 정해져 있으므로 다익스트라 알고리즘을 사용하여 출발 노드로 부터 모든 노드까지의 최소 비용을 구해주었다. 처음에는 다익스트라 알고리즘 내부에서 우선순위 큐(최소 힙)에 노드를 넣어 주는 것을 최소 비용 경로로 계산해 주었다. 하지만 이는 정답이 ..