https://leetcode.com/problems/move-zeroes/ Move Zeroes - LeetCode Move Zeroes - Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array. Example 1: Input: nums = [0,1,0,3,12] Output: leetcode.com 문제 설명 배열에 있는 0들을 오른쪽으로 모두 보내면 된다. 주의할 점은 요소들의 순서가 바뀌면 안 된다는 것이다. ..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 설명 첫 칸에서 마지막 칸까지 갈 수 있는 모든 경로의 수를 구하면 된다. 단, 항상 높이가 더 낮은 지점으로만 이동한다. 풀이 방법 1. DFS -> 시간 초과 보자마자 DFS로 풀면 되겠다고 생각했고 바로 코딩에 들어갔다. 코딩하면서 이게 왜 정답률이 27%밖에 안 되지? 생각했었는데 왜 그런지 코드를 제출해보고 알게 되었다. private static void dfs(int x, int y)..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 설명 기본적인 DFS 문제이다. 1번 노드에서 2번 노드까지 얼마나 간선을 거치는지를 구하면 된다. 조심할 점은 가족이 아닌 경우 -1을 출력해야 한다는 점이다. 풀이 방법 1. DFS public static void main(String[] args) throws IOException { // ... dfs(targets[0], 0); // ... } private s..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 제목이 트리의 부모 찾기라서 트리를 구현해야 하나 싶지만 인접 리스트 그래프로 복잡하지 않게 해결할 수 있다. 트리도 그래프의 부분집합이다. 사이트 예제 1을 활용하여 그려보면 다음과 같다. 각 노드의 부모를 구하는 게 문제이기 때문에 DFS나 BFS로 루트(1)부터 연결된 노드들을 탐색해 나가면 된다. 위 그림을 토대로 코드의 흐름을 그려보면 다음과 같다. DFS(1) DFS(6) DFS(3) DFS(5) DFS(4) DFS(2) DFS(7) 풀이..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 설명 DFS 문제를 살짝 응용한 문제이다. 풀이 방법 핵심이 되는 DFS 함수는 다음과 같다. private static void dfs(int r, int c, int count) { if (isDuplicated[board[r][c]]) { MAX = Math.max(MAX, count); return; } else { isDuplicated[board[r][c]] = true; ..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 설명 기본적인 DFS 문제이다. 크게 설명할 것은 없으며 주의할 점은 대각선까지 하나의 섬으로 따지는 것이다. 풀이 방법 기본적인 DFS 방식으로 해결할 수 있다. package baekjoon.dfs_bfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..