✔ 개미굴[백준 14725]코드 구현하기/* * 문제 분석하기 * : 단어 정보에 따라 트라이를 구한 후, 개미굴 입구인 루트 노드를 제외하고 트리를 탐색하여 개미굴의 구조를 출력하도록 함 * 예) APPLE, KIWI 중 APPLE → APPLE, BANANA 중 APPLE, BANANA 순 → KIWI * KIWI → APPLE, BANANA 중 APPLE, BANANA 순 * 그러므로 * APPLE * --APPLE * --BANANA * ----KIWI * KIWI * --APPLE * --BANANA *//* * 손으로 풀어보기 * 1. 단어 정보에 따라 트라이 자료구조에 모든 먹이 정보 저장 * 2. 저장해둔..
✔ 도시 분할 계획[백준 1647]코드 구현하기/* * 문제 분석하기 * : 크루스칼 알고리즘을 이용해 각 집들을 연결하는 최소 신장 트리를 찾고 두 마을로 분리하여 최소 유지비의 합을 찾도록 함 * 이 집들을 두 개의 마을로 분리할 때, 마지막 집을 기준으로 두 개의 마을로 분리하여 가장 큰 유지비를 제외하도록 함 *//* * 손으로 풀어보기 * 1. 크루스칼 알고리즘을 이용해 사용하지 않은 엣지 중 가중치가 가장 적은 간선을 선택 * 2. 선택한 간선을 연결했을 때 사이클이 발생하는지 판단 * 3. 간선을 더한 횟수가 정점의 개수 -1이 될 때까지 반복 * 4. 마지막 유지비의 경우, 두 마을로 분리하면 사라지게 되므로 이는 합산하지 않음 * 4. 두 마을로 분리하며 집들을 연결하는 길의 최소 ..
✔ 친구비[백준 16562]코드 구현하기/* * 문제 분석하기 * : 친구의 친구들을 모두 모아 같은 집합으로 합치도록 한 후, 집합의 대표 노드에 해당하는 친구와 친구를 하도록 함 *//* * 손으로 풀어보기 * 1. 친구 관계에 따라 친구비가 더 적은 친구를 대표 노드로 하여 집합으로 묶도록 함 * 2. 집합의 대표 노드에 해당하는 친구와 친구를 하도록 하여 비용을 증가 * 3. 가지고 있는 돈으로 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력 * 4. 만약 친구를 다 사귈 수 없다면 Oh no를 출력 *//* * 16562) 친구비 */public class Main { static BufferedReader br = new BufferedReader(new I..
✔ 줄 세우기[백준 2252]코드 구현하기/* * 문제 분석하기 * : 각 키를 비교한 학생들을 저장한 후, 진입 차수의 개수가 0개인 학생부터 위상정렬하도록 함 *//* * 손으로 풀어보기 * 1. 인접 리스트에 학생 데이터와 진입 차수를 저장 * 2. 진입 차수의 개수가 0인 학생을 큐에 저장 * 3. 위상 정렬 알고리즘을 수행 * 4. 위상 정렬한 결과를 출력 *//* * 2252) 줄_세우기 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int N, M; static ArrayList> arr = new ArrayList>();..
✔ 최단경로[백준 1753]코드 구현하기/* * 문제 분석하기 * : 다익스트라 알고리즘을 이용해 시작점에서 다른 모든 정점으로의 최단 경로를 구하도록 함 *//* * 손으로 풀어보기 * 1. 인접 리스트에 정점에 대한 간선 정보를 저장 * 2. 시작점을 큐에 넣고 다익스트라 알고리즘을 수행 * 3. 각 정점까지 가는 최단 경로의 값을 출력 * 경로가 존재하지 않을 경우 INF를 출력 *//* * 1753) 최단경로 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int V, E, K; static ArrayList[] list; /..
✔ 파일 탐색기[백준 20210]코드 구현하기/* * 문제 분석하기 * : 정렬 규칙에 맞춰 조건을 세워 정렬하도록 함 *//* * 손으로 풀어보기 * 1. 문자열의 문자를 비교해 둘 다 숫자일 경우, 수를 비교해 더 작은 것이 앞에 오도록 함 * 이때 두 수가 같다면 0의 개수가 적은 것이 앞에 오도록 함 * 2. 둘 다 문자일 경우, 알파벳의 순서대로 더 작은 것이 앞에 오도록 함 * 이때 두 알파벳이 같은 알파벳이라면 대문자가 앞에 오도록 함 * 3. 하나는 문자, 하나는 숫자일 경우, 숫자가 앞에 오도록 함 * 4. 두 문자열을 비교한 후 뒤에 문자가 더 붙어있는 문자열이 있다면, 뒤에 오도록 함 *//* * 20210) 파일탐색기 */public class Main { sta..
✔ 나머지 합[백준 10986]코드 구현하기/* * 문제 분석하기 * : 수들끼리의 누적합을 구한 후, 이들이 M으로 나누어 떨어지는지 확인하여 구간의 개수를 증가시키도록 함 * 또한 나머지가 같은 구간을 이용해 M으로 나누어 떨어지는지 확인하도록 함 * 예) A = {1, 2, 3, 1, 2}, M = 3 * S[1] = 1 + 2 = 3 -> M으로 나누어 떨어짐 * S[0] = 1 -> 나머지 1이 발생 * S[3] = 1 + 2 + 3 + 1 = 7 -> 나머지 1이 발생 * 그러므로 S[1] ~ S[3] = 2 + 3 + 1 -> M으로 나누어 떨어짐 *//* * 손으로 풀어보기 * 1. 수들끼리의 누적합을 구함 * 2. 누적합을 확인해 M으로 나..
✔ 트리[백준 4256]코드 구현하기/* * 문제 분석하기 * : 후위 순회에서는 왼쪽-오른쪽-루트 순서로 이동하므로, 전위 순회와 중위 순회 값을 이용해 순회하도록 함 * 예) 전위 : 3, 6, 5, 4, 8, 7, 1, 2 / 중위 : 5, 6, 8, 4, 3, 1, 2, 7 * - 루트 노드 : 3 / 왼쪽 서브트리 : 5, 6, 8, 4 / 오른쪽 서브트리 : 1, 2, 7 * * - 루트 노드 : 6 / 왼쪽 서브트리 : 5 / 오른쪽 서브트리 : 8, 4 * - 루트 노드 : 5 -> [5] * - 루트 노드 : 4 / 왼쪽 서브트리 : 8 -> [5, 8, 4] * - [5, 8, 4, 6] * * - 루트 노드..
