알고리즘/백준

13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net > 의식의 흐름 dfs를 써서 모든 경우에 대해 비용을 구하고 그 중 최소를 뽑으면 되지 않을까? => 시간초과 옆 사람과의 키 차이가 얼마인지 구한 뒤에 차이가 큰 부분을 잘라서 조로 나눠버리면 될 것 같은데..? => 성공 > 풀이 과정 1. 원생의 수(N), 조의 개수(K)를 입력 받는다. 2. 모든 원생의 키를 배열(heights)에 저장한다. 3. 옆 원생과의 키 차이를 배열(gap)에 저장한다. 4. 배열 gap을 오름차순으로 정렬한 후 `N-K`..

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net > 의식의 흐름 연산자가 +, -만으로 이루어져 있으니까 -를 기준으로 각각의 합을 구해서 빼면 최소가 나오지 않을까.. > 풀이 과정 1. 식을 입력 받는다. 2. i번째 문자(ch)가 숫자인지 아닌지 판단한다. 숫자인 경우 num에 담아둔다. num *= 10; num += Integer.parseInt(Character.toString(ch)); 문자인 경우 '-' 전까지 나온 수들의 합을 구한 후 deque에 담아둔다. 3. 문자열 길이만큼 2번 반..

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net > 의식의 흐름 트리 만들구 후위 순회하면 되겠징,,, > 풀이 과정 1. 첫번째 입력값을 루트노드로 지정한다. 2. 이후 입력값들에 대해 루트노드를 기준으로 트리를 생성한다. 왼쪽, 오른쪽 Node를 담는 Node 클래스 이용 3. 입력 없을 때까지 2번 과정 반복한다. while((input=br.readLine()) != null && !input.isEmpty()){ // 2번 과정 } 4. 후위 순회 후 결과 출력한다. 후위 순회 시, 왼쪽..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net > 의식의 흐름 > 풀이 과정 > 코드 import java.io.*; import java.util.StringTokenizer; public class Main { public static int N; // 노드의 개수 public static Node[] nodes; public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public stat..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net > 의식의 흐름 > 풀이 과정 1. 연결된 노드 담기 2. 1번 노트부터 시작 (트리의 루트를 1이라고 정했기 때문) 3. 현재 노드(nowIdx)와 연결된 노드들의 부모 설정하기 (parents[]) 4. 2번 노드부터 부모 출력 > 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; imp..

14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net > 의식의 흐름 간선은 끊으면 어떤 경우여도 그래프가 2개로 나뉘니까 yes일거고 정점은 다른 정점 한 개랑 연결된 애만 아니면 되겠지..? > 풀이 과정 1. 각 정점에 대해 연결된 정점 번호를 담을 ArrayList 생성 ArrayList links = new ArrayList(); for(int i=0;i 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import..

7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net > 의식의 흐름 시간 제한이 6초인 것을 보고 시간이 너무 널널한데? 생각했다가 T(테스트케이스의 수) 범위가 없는 것을 보고 PriorityQueue 2개를 쓰면 위험할 수도 있겠다는 생각을 했다. PriorityQueue 하나만 쓰는 방법을 생각하다가 TreeSet + PriorityQueue -> TreeMap 순으로 코드를 계속 수정했다,, > 시간복잡도 # PriorityQueue - 삽입, 삭제 : O(logN) # Treemap - 삽입, 삭제 ..

4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net > 의식의 흐름 해시맵 써서 정렬하고 어찌저찌,, > 풀이 1. HashMap(key = 종 이름, value = 입력된 횟수)을 이용하여 종 이름이 몇 번 입력되었는지 저장한다. 2. 1번 과정을 입력 끝날 때까지 반복 // 입력 끝날 때까지 반복 while((type=br.readLine())!=null && !type.isEmpty()){ //... } 3. HashMap의 키값들(종 이름)을 사전순으로 정렬한다. 4. 정렬된 순서대로 해당 종이..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net > 의식의 흐름 한 칸에 대한 주변 8칸에 겹치는 수가 있으면 안되는 것이라고 착각하고 풀었다가 틀렸습니다가 잔뜩,,, 한 칸에 대한 주변 8칸이 아니라 특정 영역의 정사각형 내에 겹치는 수가 있으면 안된다는 것을 깨닫고 로직을 고쳤더니 통과했다 > 풀이 1. map[][] 입력 받는다. 이때, 빈 칸의 위치를 ArrayList에 담아둔다. 2. 백트래킹 활용 Location loc = blanks.get(idx); for(int i=1;i 코드 import j..