[BOJ]

[JAVA] 11725 트리의 부모 찾기

문제 더보기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 더보기 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 더보기 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력 풀이과정 트리에서 각각 노드의 부모 노드를 출력하기 위해선 너비우선탐색을 사용 너비우선 탐색을 위해 Queue 사용 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeq..

[JAVA] 1149 RGB거리

풀이과정 이렇게 각 집마다 색깔을 겹치지 않게 색칠해줘야 한다. 그렇다면 2,2를 파랑으로 색칠할때 이미 최소값 계산이 다 되었다고 가정한 주황색중에 작은 값을 고른다. (색이 겹치면 안되기 때문에 [1][2]는 제외시켰다.) 주황색중 작은 값을 파랑에 더하면 최소값이 나온다. 그렇다면 이걸 sudo코드로 바꾸자면 [2][2] += min([1][0], [1][1])이다. 맨 초반 고정값은 그대로 넣어주고 그 값을 토대로 각 배열의 최소값들을 식으로 표현한다면 사진과 같이 나온다. 맨 아래 나온 N번째 식을 점화식을 토대로 최소값을 구해준다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..

[JAVA] 11726 2×n 타일링

풀이과정 1. 2*1 타일과 1*2 타일을 고정으로 값이 정해져 있고 작은 값을 통해서 큰 값을 구해야하므로 DP로 풀었다. f[n] = f[n-1] + f[n-2]라는 점화식을 세웠다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class backJoon11726 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

[JAVA] 21939 문제 추천 시스템 Version 1

문제 : https://www.acmicpc.net/problem/21939 풀이 과정 1. 중복된 KEY값을 저장 못하므로 TreeSet 사용 2. 정렬 기준 : 특정 treeSet과 한번만 비교하면 되므로 Comparable 사용 Comparable은 "자기 자신과 매개변수 객체를 비교"하는 것이고, Comparator는 "두 매개변수 객체를 비교"한다 자세한건 내 블로그에 정리했다. https://jasonoh22.tistory.com/35 [JAVA] Comparable 과 Comparator 비교 Comparable과 Comparator는 모두 인터페이스이다. 고로 둘중 하나를 사용하고자한다면 인터페이스에 선언된 메소드를 무조건 구현해야 사용할 수 있다. [Comparable] : Comapre..

[JAVA] 11286 절대값

풀이 과정 1. PriorityQueue 사용. 대신 정렬 기준을 바꿔서 사용한다. 정렬 기준을 어떻게 바꿀까... 맨처음엔 함수를 만들어서 PriorityQueue에 넣을라고 했다. -> 밖에선 정렬하는 의미가 없다. 이미 PriorityQueue 안에서 정렬하기 때문이다. 그럼 이 정렬기준을 바꾸면 되지 않을까? 그래서 PriorityQueue의 정렬기준을 바꾸려면 어떻게 해야할까? 일단 PriorityQueue.java를 살펴봤다. PriorityQueue안에서 정렬을 시켜주는 인터페이스 Comparator가 있었다. 비교기 또는 null(우선 순위 대기열이 요소의 자연 순서를 사용하는 경우) (2023-03-26 추가) 자기 자신과 비교하는게 아닌 절댓값이 가장 작은 값이 여러개일때 가장 작은 값..

[JAVA] 4358 생태학

풀이 과정 1. 데이터 저장할 Map 2. 만약 Map에 포함 되어있으면 value 꺼내서 ++ 후 다시 저장 -> 함수 mapContains 3. 백분율 계산 -> 함수 speciePercent 사용 4. 문제 틀림 이유 분석 4-1. while문을 나오지못해서 무한루프가 되는가? -> notBlank로 해결 4-2. mapContains 함수에서 값이 제대로 저장되지 않는가? -> 잘 저장됨. 4-3. speciePercent 에서 소수점 계산이 잘못되었는가? math.round() 와 String.format 중 math.round를 선택했는데 String.format을 사용하니 맞았다. 그럼 String.format과 math.round()의 차이점을 뭘까 맨처음엔 speciePercent 만들어..

[BOJ] 2075 N번째 큰 수

풀이 과정 1. N번째 가장 큰 수를 구하는 문제 -> Max Heap으로 만든 후 N번 pop 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQueue; public class backJoon2075 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt..

[Java] 최대 힙

힙, 우선순위 큐 정리 : https://jasonoh22.tistory.com/43 풀이 과정 1. 각 시점마다 큰값 출력 요구 하므로 자바에서 제공하는 priorityQueue 사용 2. 연산의 개수 N(1 ≤ N ≤ 100,000) 이므로 시간을 단축하기 위해 BufferedReader, StringBuilder 사용 3. 만약 Queue가 비였다면 0 출력 아니면 poll() 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQueue; public class backJoon112..