문제풀이
-
[백준]1600: 말이 되고픈 원숭이 - JAVA문제풀이/백준 2021. 4. 4. 18:11
[백준]1600: 말이 되고픈 원숭이 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 출발 위치에서 도착위치까지 움직일 수 있는 최소 값을 반환하는 문제이므로 BFS를 사용하였다. 이때 말이 움직일 수 있는 위치와 원숭이가 움직일 수 있는 위치를 따로 배열로 만들어 주었다. 최소값을 계산할 때는 한번 방문한 위치는 재 방문해서 안되기 때문에 visited배열을 선언하여 재 방문을 허용하지 않도록 하였다. 이때 단순히 visited배열을 ..
-
[프로그래머스]풍선 터트리기 - JAVA문제풀이/프로그래머스 2021. 3. 31. 15:47
[프로그래머스]풍선 터트리기 코딩테스트 연습 - 풍선 터트리기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 풀이 이 문제의 조건 중 가장 중요한 조건은 '인접한 두 풍선 중에서 번호가 더 작은 풍선을 터뜨리는 행위는 1번만 할 수 있다'라는 조건이다. 즉, 인접한 풍선의 번호가 모두 더 작다면 마지막까지 남을 수 없다는 것이다. 그럼 이러한 상황에서 마지막까지 풍선이 남기 위한 조건은 무엇일지 생각해보쟝. 임의의 풍선을 중심으로 인접한 풍선의 번호가 모두 더 작으면 안된다. 그럼 모든 원소 값을 기준으로 왼쪽, 오른쪽 풍선 번호의 최소값을 찾고 해당 값보다 현재..
-
[백준]1240: 노드사이의 거리 - JAVA문제풀이/백준 2021. 3. 28. 16:28
[백준]1240: 노드사이의 거리 www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 풀이 두 노드 사이의 최단 경로를 반환하는 문제였다. 다양한 방법이 있겠지만 나는 다익스트라 알고리즘을 사용하여 풀었다. 노드와 간선 가중치의 정보를 입력 받은 후 M개의 개수 만큼 다익스트라 알고리즘을 돌려 M개의 거리를 출력하였다. 다익스트라 알고리즘은 우선순위 큐(최소힙)와 dist배열, visited배열을 사용하여 구현해 주었다. 기본적인 다익스트라 알고리즘을 구현할 수 있는지 묻는 수준의 문제였고 어렵지 않게 풀었..
-
[백준]6593: 상범 빌딩 - JAVA문제풀이/백준 2021. 3. 21. 15:03
[백준]6593: 상범 빌딩 www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 최단거리를 찾는 문제이므로 bfs를 사용하여 탐색하였다. 시작 위치, 도착 위치를 입력 받기 위해 Node 클래스를 정의해 주었다. 이 문제는 좌표를 이용한 bfs문제이면서 일반적인 문제와 달리 3차원 공간에서의 bfs최단거리를 찾는 문제이다. 기존의 x, y방향으로만 이동하여 문제를 풀었던 방식을 살짝 변형하여 문제를 풀어 주었다. 이동 방향이 오른, 왼, 위, 아래 4방향에 위층..
-
[백준]2668: 숫자고르기 - JAVA문제풀이/백준 2021. 3. 14. 15:32
문제 www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 뽑힌 정수의 집합과 뽑힌 정수 바로 아래 정수들이 이루는 집합이 일치하는 숫자들을 뽑는 문제였다. 예제의 숫자들 중에서 뽑힌 숫자들을 보면 싸이클을 이루는 숫자들이라는 것을 알 수 있다. 즉, 싸이클을 이루는 숫자들을 뽑는 문제인 것이다. 예를들어 위의 예제에서 발생한 싸이클은 아래와 같당. 1 -> 3 -> 1 (싸이클) 3 -> 1 -> 3 (싸이클) 5 -> 5 (싸이클) 이때 싸이..
-
[프로그래머스]길 찾기 게임 - JAVA문제풀이/프로그래머스 2021. 3. 14. 13:50
[프로그래머스]길 찾기 게임 programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 입력받은 데이터를 가지고 트리를 만들고, 전위순회/후위순회한 결과를 반환하면 된다. 트리에 대해 잘 알고 있었다면 크게 어려움 없이 풀 수 있는 문제였고 트리에 대해 잘 모르더라도 이 문제를 통해 트리를 이해하는데 도움이 될만한 좋은 문제라고 생각한다. 이 문제에서 요구되는 트리를 x값을 기준으로 생각한다면 이진검색트리라고 볼 수도 있을 것 같..
-
[백준]16432: 떡장수와 호랑이 - JAVA문제풀이/백준 2021. 3. 13. 15:11
[백준]16432: 떡장수와 호랑이 www.acmicpc.net/problem/16432 16432번: 떡장수와 호랑이 동희가 N일동안 호랑이에게 떡을 줄 방법이 있다면 i (1 ≤ i ≤ N) 번째 줄에 동희가 호랑이에게 주어야 할 떡을 출력합니다. 이 떡은 동희가 i번째 날에 만든 떡이어야 합니다. 만약 동희가 떡을 www.acmicpc.net 풀이 전형적인 DFS 탐색 문제로 문제의 조건에 따라 이전에 뽑은 숫자와 다른 숫자를 N만큼 뽑을 수 있다면 뽑은 수를 출력하고, 뽑을 수 없다면 -1을 출력하면 된다. 간단하게 DFS를 사용하여 구현하였다. 그리고 N개를 뽑을 수 있는 방법이 여러개라면 한 개만 출력하면 되므로 N개를 뽑고 출력한 다음 프로그램을 종료시켰다. 만약 DFS를 돌면서 N개를 뽑지..
-
[백준]1405: 미친 로봇 - JAVA문제풀이/백준 2021. 3. 12. 14:27
[백준]1405: 미친 로봇 www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 풀이 DFS + 백트래킹을 사용하여 풀었다. 결국엔 문제에서 구하는 값은 같은 곳을 방문하지 않고 N번동안 이동할 때의 확률을 구하는 것이다. 즉 DFS를 사용하여 N번만큼 이동하되 visited 함수를 사용하여 같은 공간은 방문하지 않도록 처리하면 된다. 이때 이동할 확률을 구하는 방법은 같은 공간을 방문하지 않고 이동하며, 이동할 때매다 이동할 방향의 확률을 곱해서 그 값을 ..