Knowledge Foundation

아이디어graph에서 연결 요소(Connected Component)란, 연결되어있는 군집의 개수와 같다예를 들면 그래프가1-2-3 4-5 6-7-8 9위와 같이 구성되어 있다면, 연결 요소는 (1-2-3), (4-5), (6-7-8), (9)의 4개이다. 일반적인 bfs나 dfs는 하나의 연결 요소에 대해서만 탐색할 수 있으므로boolean[] visited가 모두 true가 되기 전까지 반복하여 탐색을 진행하면 연결 요소의 개수를 구할 수 있다. bfs나 dfs를 이용해서 우선 하나의 노드에 대해 인접 노드를 탐색하고, 탐색을 할 때마다 연결 요소의 개수를 1개씩 추가한다. 그렇게 하나의 연결 요소 탐색이 끝나면 visited가 false인 노드에 대해 다시 탐색을 시작하고, 이를 반복한다. 이를 코..

아이디어최대 힙 문제이다. 우선순위 큐, 그 중 최대 힙은부모 노드가 항상 자식보다 큰 완전 이진 트리이다. 새로운 노드를 넣을 때, 가장 마지막 노드에 넣고, 힙의 조건(부모 >= 자식)을 만족할 때까지 교환한다.삭제할 때에는 root를 꺼내고, 마지막 노드를 root로 올린 뒤 힙의 조건을 만족할 때까지 교환한다. 이를 코드로 구현하면 다음과 같다.import java.io.*;import java.util.Collections;import java.util.PriorityQueue;public class N11279 { public static void main(String[] args) throws IOException { BufferedReader br = new Buffere..

아이디어이진 탐색 문제이다.나무의 개수 N, 필요한 나무의 길이 M을 입력받고N개의 나무의 길이를 입력받아 배열로 저장한다.그 중 가장 긴 나무의 길이를 탐색할 높이 H의 최대값으로 설정한다. 정석적인 이진 탐색 알고리즘과 같이, 초기 중앙값으로 H를 설정하여 나무를 잘랐을 때자른 나무의 길이의 합인 sum이 M 이상이면 중앙값을 정답에 저장한다.그 후 sum이 M보다 큰 경우 sum을 줄여야 하므로 H를 높여아하니 left를 mid + 1로 설정한다. 다시 mid를 구한 후 sum이 M 이상인지 아닌지 확인한 후M 미만이라면 right를 mid - 1로 설정한다.이 과정을 right가 left 이하가 되기 전까지 반복한다. 이를 코드로 구현하면 다음과 같다.import java.io.*;public c..

아이디어처음 풀어보는 분할 정복 문제이다. 처음 풀어보는 알고리즘이라 pseudo code만 찾아서 풀었다.분할 정복 알고리즘의 pseudo code는 다음과 같다.function DivideAndConquer(problem): if problem의 크기 우선 main 함수에서 전체 색종이에 대한 입력을 받고, 그 색종이를 분할 정복 메서드로 보낸다.보낼 때는 색종이와 색종이의 사이즈를 매개변수로 한다.public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = ..

아이디어이진 탐색을 쓰는 문제이다.입력된 랜선 중 가장 긴 랜선에서 한 토막의 길이를 결정해서다른 랜선들도 그 토막의 길이만큼 나눈 다음 그 모든 토막들의 개수를 합해서 N개 이상인지를 확인할 것이다.이진 탐색으로 진행하면 다음과 같은 알고리즘을 따른다. init: left = 1, right = 제일 긴 랜선의 길이 while(left {mid = (left + right) / 2mid로 모든 랜선들을 나눈 몫의 합이 N 이상이면 -> mid를 정답에 저장, left = mid + 1아니면 -> right = mid - 1} 이 방법대로 예제 입력대로 코드를 실행하면 다음과 같이 진행된다 mid = 401 -> left = 1, right = 400 mid = 200, ans = mid -> left ..

아이디어입력된 수식을 "-"를 기준으로 분할하면예컨데 입력된 수식이 15+93-12+35-45라면15+9312+3545로 세 수식으로 분할되게 된다. 첫번째 수식을 연산하여 sum에 더하고나머지 수식들은 연산 후 sum에 감하면 된다. 이를 코드로 구현하면 다음과 같다.import java.io.*;public class N1541 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWri..

아이디어DFSDFS는 깊이 우선 탐색으로, 트리 혹은 그래프에서 한번 나아갔던 방향대로 쭉 탐색하다가더이상 탐색할 것이 없으면 다시 갈림길로 돌아와서 다른 방향으로 쭉 탐색하는 것을 반복하는 탐색법이다.psuedo code는 다음과 같다.dfs(node) { visited[node] = true for(next in neighbor of node) { if (!visited[next]) { dfs(next) } }} BFSBFS는 너비 우선 탐색으로, 트리 혹은 그래프에서 이웃한 노드들을 먼저 탐색하는 방법이다.예를 들어, 이진 트리를 BFS로 탐색한다 하면, 시작 노드(1)의 왼쪽 노드(2)로 가서 이웃이 누가 있는지 탐색하고시작 노드의 오..

아이디어대체 이 문제 점화식을 어떻게 구하라는거야...하고 풀다가dp를 쓰는데 greedy하게 풀었다. 그래서 처음에는 모두 넷 이하의 숫자로 표현이 되길래잘 풀었다! 싶었는데 오답이란다그래서 gpt한테 이런 문제 점화식 어떻게 찾냐 하니 동전 교환 문제와 같다 하더라대체 이런 알고리즘들은 어떻게 알고 다 짜나 모르겠다.그냥 많이 풀어보면서 익혀야하나... 이를 코드로 구현하면 다음과 같다.import java.io.*;public class N17626 { public static void main(String[] args) throws IOException { BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System...

아이디어HashMap을 써서 푸는 문제로 생각했는데, 예시 입력처럼 꼭 Map에 을 넣을 필요는 없다.옷의 이름과 옷의 종류를 입력으로 주는데, 우리가 이름을 쓸 일은 없다. 중요한 것은 옷의 종류가 몇 벌씩 있냐이다.그래서 Map의 Key에 옷의 종류가 없으면 (옷의 종류, 1)을 저장하게 하고만약 들어가있다면 (옷의 종류, 기존 개수 + 1)을 저장하게 했다 그렇게 해서 저장된 HashMap에 예를 들어Headgear가 3개, eyewear가 2개, face가 1개 있다면해빈이가 옷을 입는 경우의 수는 (3+1) x (2+1) x (1+1)이다.Headgear가 3개라면 (입지 않는 경우(0), 1번째 옷 입는 경우, 2번째 옷을 입는 경우, 3번째 옷을 입는 경우)의4가지 경우가 있을 수 있기 때문..

아이디어동전이 여러개가 주어지니, 가장 큰 동전을 쓸 수 있는 만큼 쓰고계속해서 동전의 크기를 줄여나간다. 이를 코드로 구현하면 다음과 같다.import java.io.*;public class N11047 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String[] input = br.readLine().split(" "); ..