1. 💎 문제 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 2. 🤔 어떻게 풀까 이 문제는 점점 물들이는 문제로 익숙한 BFS문제로 느껴졌다. 그래서 BFS로 풀기로 하였고 출력 결과를 봤을 때 시작 점을 기준으로 거리가 늘어나는 것을 보아 시작점부터 탐색을 진행하며, depth을 관리하면서 풀면 되겠구나 생각했다. 3. 💡로직 1. 지도를 입력 및 시작점 받기 이중 for문으로 지도를 입력받는 형태에서 stream을 이용한 형태로 바꿨는데 시간이 훨씬 단축되는 ..

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 흐름 이 문제는 테스트 케이스의 제한이 없는데 N은 100,000이다. 그러므로 최대한 O(n)으로 풀어야 겠다고 생각했다. 어떻게 최대값을 찾는냐! 스티커는 총 2줄이고 인접한 스티커는 뜯으면 안된다. 만약 열의 수가 짝수이면 지그재그 방법뿐이다. 그래서 2개의 경우의 수 밖에 없지만 문제는 열의 수가 홀수일 때 이다. 예제를 분석해보면 현재 위치에서 갈 수 있는 방법은 2가지이다. 인접한 변으로 못가니, 대각선으로만 이동이 가능하다. 대..

문제 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 풀이 생각 n을 5와 2로만 채울 때 가장 최소 동전의 개수를 구해야 하므로, 5를 기준으로 5 동전의 크기를 줄여나가면서 구한다. 코드 1. input() n을 입력 받는다. public void getInput() throws Exception { n = Integer.parseInt(br.readLine()); } 2. solution() 예를 들어 18일 때 18 ÷ 5 = 3이므로 최대 5 동전의 개수는 3이다. 그 후 18 - (5 X 3) = 3(나머지수)을 2 동전으로 채울 수 있는지 확인한다. 만약 나머지 수를 2로 채울 수 있다면 결과에 3 ÷ 2 = 1 의 ..

문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 어떻게 풀것인가? 트리 형태를 만든 다음 삭제 노드를 부모 노드와 끊어준다. 노드의 부모는 무조건 1개이기 때문에, 끊어주면 탐색을 할 수 없다. 트리를 DFS 탐색으로 탐색을 진행한다. BFS나 DFS 둘다 되겠지만 구현이 쉬운 BFS를 선택했다. 문제 알고리즘 parent 배열에 각 노드의 parent 값을 저장한다. parent 배열 이용하여 삭제할 노드를 부모 노드에서 제거 한다. BFS 탐색을 진행하면서 leaf 노드를 찾는다. 주의할 점 루..

문제 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근 방법 수의 개수 제한은 천 만으로 많은 편에 속하지만 수의 크기는 만으로약 4자릿수가 최대. 이때는 자릿수에 따라 시간 복잡도 결정되는 기수 정렬이 좋은 방법. 기수 정렬 기수 정렬 값을 비교하지 않는 특이한 정렬으로 자릿수를 정한 다음 해당 자릿수만 비교한다. 기수 정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를말한다. 기수 정렬 알고리즘 10개(0~9)의 큐를 이용하여 값의 자릿수를 대표한다. 일의 자릿수부터 10개의 큐에 넣어가며 정렬을 한다. 큐..

문제 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 접근 방법 버블 정렬의 이동은 한 번에 한칸씩만 이동할 수 있다. swap의 횟수를 찾기 위해서는 부분 리스트가 1개가 될 때까지 쪼개고 점점 합병해가면서 합치는 합병 정렬이 알맞다고 생각했지만 합병 정렬은 가까운 요소끼리 먼저 정렬을 하기 때문에 기준 요소와 모두 비교를 진행하고 swap하는 버블 정렬과는 다른 결과가 나올 것이라 생각했다. 책을 보며 풀이법을 봤지만 사실 아직도 이해가 안간다. 버블 정렬은 현재 위치가 정렬이 완료..

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 접근방법 어떻게 하면 최솟값을 구할 수 있을까 생각을 했을 때, 누적시켜 더하는 특징에서 앞에 나오는 값들이 작을 때 최소가 될 것이다 생각을 했다. 그래서 오름차순 정렬을 이용하기로 하였다. 풀이 입력 입력의 수가 최대 1001개 이므로 비교적 구현이 쉬운 스캐너로 구현하였다. // 입력 받기 Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int [] num =..

문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근법 N은 최대 10자리 숫자로 매우 큰 메모리 공간을 차지함. 하지만 이 문제는 자릿수의 숫자들을 뽑아 정렬하는 것이므로 String 객체로 입력을 받아 쪼개 Int형 배열로 만드는 것이 효율적이라 생각이 들었다. 그 후 최대 10개의 숫자를 정렬하는 것은 아무 정렬법이나 쓰면 된다. 풀이 코드 public class Main { public static void main(String[] args) throws IOException { // 문자열로 입력 받기 Scanner..

https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 문제 버블 정렬 알고리즘을 빠삭히 알고 있어야 풀 수 있는 문제였다. 나는 못 풀었다. 핵심은 정렬이 완료된 시점을 찾아 내는 것! 우선 나의 알고리즘 풀이 생각은 다음과 같았다. 버블 정렬은 한 번 루프가 돌면 마지막 리스트 자리에는 정렬이 완료된 요소가 1개씩 추가된다. 이를 이용하여 정렬 전과 정렬 후를 비교해 정렬이 되지 않은 요소의 개수를 찾아내면 되지 않을까! 생..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 수의 개수가 1000개이고 시간 제한이 1초이므로 O(n^2)써도 충분한 문제이다. 그러므로 구현이 간단한 정렬 중 하나인 버블 정렬을 선택하여 풀었다. 입력 // 입력 Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int [] nums = new int[N]; for(int i=0; i< N;i++){ nums[i] = sc.nextInt..