코딩테스트/[백준] 코딩테스트 연습

최단경로 - 1753번

풀이 방법 전형적인 다익스트라 문제이다. 우선순위 큐를 이용한 다익스트라 알고리즘을 구현해서 풀이했다. 2021.10.01 - [분류 전체보기] - 최단 경로 알고리즘 (다익스트라, 벨만-포드, 플로이드-워셜) 내 코드 package com.company; import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; class Node implements Comparable { private int distance; private int index; public Node(int index, int distance) { th..

동전 2 - 2294번

풀이 방법 동적 계획법으로 bottom-up 방법을 사용했다. 우선 100001로 초기화 시켜주고 만들수 있는 coins 에 넣은 수들로 비교해가며 최소 횟수를 구해주었다. 내 풀이 package com.company; import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(s..

1로 만들기 - 1463번

풀이 방법 생각 DP 문제로 점화식을 생각해야 했다. 일단 0과 1은 0번으로 고정이라서 값을 넣어주었다. Bottom-up 방식으로 2부터 n까지 계산해 주었다. 이전 수에서 1을 더하는 경우를 생각해서 이전 수의 횟수에서 1을 더해주는 경우 2로 나누어 떨이지기 때문에 2로 나눈 수의 횟수에 1을 더하는 경우 3으로 나누어 떨어지기 때문에 3으로 나눈 수의 횟수에 1을 더하는 경우 이 세가지를 비교해서 최솟값을 만들어 주었다. 내 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Mai..

트리의 부모 찾기 - 11725번

트리의 부모 찾기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 27396 11727 8664 42.697% 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 입력 1 7 1 6 6 3 3 5 4 1 2 4 4 7 예제 출력 1 4 6 1 3 1 4 예제 입력 2 12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12 예제 ..

나는야 포켓몬 마스터 이다솜 - 1620번

나는야 포켓몬 마스터 이다솜 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 26947 8852 6287 32.421% 입력 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 포켓몬 이름의 최대 길이는 20이야. 그 다음 ..

요세푸스 문제 - 1158번

요세푸스 문제 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 50463 24503 17494 48.004% 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, )-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ ..