문제풀이
-
[백준]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 풀이 최소 비용을 구하면서, 최소 비용 경로까지 함께 구하는 문제였다. 출발 노드가 정해져 있으므로 다익스트라 알고리즘을 사용하여 출발 노드로 부터 모든 노드까지의 최소 비용을 구해주었다. 처음에는 다익스트라 알고리즘 내부에서 우선순위 큐(최소 힙)에 노드를 넣어 주는 것을 최소 비용 경로로 계산해 주었다. 하지만 이는 정답이 ..
-
[백준]14226: 이모티콘 - JAVA문제풀이/백준 2021. 5. 16. 14:58
[백준]14226: 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 걸리는 시간의 최소값을 구하는 문제 이므로 BFS 탐색을 사용하여 문제를 풀었다. BFS탐색을 하면서 조건에 맞게 1, 2, 3번을 진행하고 현재 개수가 S와 같아진다면 BFS탐색을 종료하고 현재 시간을 출력하도록 하였다. 탐색을 하면서 계속 같은 구간을 반복하지 않도록 visited 배열을 사용하였다. 각각의 인덱스가 의미하는 바는 [clipboard에 현재 복사..
-
[백준]1300: K번째 수 - JAVA문제풀이/백준 2021. 5. 13. 15:05
[백준]1300: K번째 수 풀이 이분탐색 문제이다. 문제의 조건에 따라 직접 배열을 만들고, 정렬하는 것도 방법 중 하나이겠지만 입력 조건에 N은 10의 5제곱 이기 때문에 이를 2차원 배열로 만들면 메모리 소비와 시간도 엄청 걸릴 것 이다. 그러므로 이분탐색으로 풀어야 한다. 문제의 예제입력을 푸는 과정을 살펴보자. 배열 A를 2차원 배열로 표현하면 다음과 같다. 배열A 1 2 3 2 4 6 3 6 9 이때, 6이라는 숫자가 오름차순 정렬되었을때 몇 번째에 오는지 알아보자. 1번열은 모두 6이하 이므로 3을 더해준다. 2번열은 모두 6이하 이므로 3을 더해준다. 3번열은 3, 6 두개의 숫자가 6이하 이므로 2를 더해준다. 즉, 6은 8번째에 오는 숫자가 된다. 진짜인지 확인해 보자. A를 오름차순 ..
-
[백준]16236: 아기 상어 - JAVA문제풀이/백준 2021. 5. 11. 15:53
[백준]16236: 아기 상어 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 BFS + 구현 문제로 조건이 까다롭고 신경써야 할 조건들이 많아 어렵다고 느껴졌던 문제였다. BFS안에서 현재 이동할 수 있는 곳으로 이동하면서 물고기의 크기가 자신의 크기보다 작으면 먹어주도록 하였다. 물고기의 크기가 자신의 크기보다 작거나 같다면 이동시켜 주었다. 자신의 크기보다 작은 물고기를 만나면 모두 ArrayList에 담아준 다음 위쪽 -> 왼쪽 좌표를 비..
-
[백준]1068: 트리 - JAVA문제풀이/백준 2021. 5. 10. 15:27
[백준]1068: 트리 www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 부모 인덱스를 입력받고, 노드를 삭제한 후 리프 노드를 count하는 문제로 깊이 우선 탐색 방법을 적용하여 문제를 풀었다. (약간 변형된 DFS문제라고 생각한다.) 노드를 삭제할 때에는 재귀 함수를 활용하여 현재 노드의 부모 인덱스가 삭제된 노드라면 연쇄적으로 삭제가 일어나도록 구현해 주었다. 리프노드를 카운트 할 때에는 깊이 우선 탐색을 활용하여 현재 노드를 부모로 가지는 ..
-
[백준]2636: 치즈 - JAVA문제풀이/백준 2021. 5. 7. 15:37
[백준]2636: 치즈 www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 BFS 탐색 알고리즘을 사용하여 문제를 풀었다. 우선, 현재 치즈의 개수를 세어 준 다음 치즈 개수가 0이 아닐때까지 BFS 탐색을 하며 치즈의 개수를 줄여나갔다. 탐색은 0,0부터 시작하여 치즈를 만나면 해당 치즈를 없애주고, 치즈가 아니라면 큐에 넣어 근처에 있는 치즈를 탐색하도록 하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2..