3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 풀이 핵심 1. root 노드를 찾기 2. 가장 가까운 공통 노드 찾기 root 노드 찾기 root 노드를 찾기 위해 입력 자식 노드를 체크 해준다. 그리고 입력이 끝난 후에 체크되지 않은 노드가 root 노드이다. 가장 가까운 노드 찾기 LCA(Lowest Common Ancestor) 알고리즘을 이용한다! LCA 알고리즘의 핵심 순서는 3가지이다. 각 노드의 Depth, Parent 리스트를 구한다. ..

문제 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 접근 전체 노드를 탐색하면서 어떻게 부모 노드를 저장할 수 있을까! 생각을 해봤을 때 자식 노드를 탐색하기 위해 재귀 함수를 호출할 때 부모의 값을 넘겨주면 될 것이라고 생각했다! 모든 노드를 탐색해야 하기 때문에 DFS와 BFS 중 고민했고 함수를 호출할 때 부모의 값을 넘겨주면 구현하기 쉬울 것이라 생각해서 재귀함수를 쓰는 DFS를 사용했다. void DFS(int child, int p) { visited[child] = true; // 부모 값을 저장 parent.set(child, p); Iterator i..

문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 접근 방법 1번 노드를 시작으로 그래프가 끊길 때까지 전체 탐색을 하면 되는 문제라서 BFS나 DFS 중 아무거나 써도 될 것 같았다. 그래서 잘 안써본 BFS로 구현해봤다! 알게된 점 큐를 구현할 때 LinkedList를 이용해도 된다. add : 맨 뒤에 요소를 삽입한다. poll : 맨 앞(제일 먼저 삽입된 요소) 요소를 제거 후 반환 한다. 코드 import java.awt.*; import java.io.*; import java.util.*; publ..

DFS DFS는 깊이 우선 탐색으로, 한 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 검색 속도 자체는 BFS에 비해 느리지만 조금 더 간단하다. 스택 혹은 재귀함수를 이용하여 구현한다. class Graph{ private int V; private LinkedList adj[]; Graph(int v){ V = v; adj = new LinkedList[v]; for(int i=0; i

문제 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 접근 방법 맨 앞에는 항상 최솟값을, 맨 뒤는 항상 최댓값을 넣어서 유지 시키면 풀 수 있을 것이라 생각. 그래서 값을 삽입할 때마다 정렬된 순서로 넣어주는 것이 중요하다고 생각 했다. 방법1. 덱 쓰기 앞과 뒤를 넣고 뺴는 것이기 때문에 적합한 자료구조가 덱이라고 생각했다. 하지만 이제 정렬된 순서로 어떻게 넣어줄지를 구현해 보니깐 중간에 넣어줄 수 있는 방법이 없다는 것을 깨달았다!!! 방법2. Linked List 쓰기 삽입할 때 정렬된 순서로 넣..

문제 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 접근 1초의 시간이고, 입력 케이스의 최대는 백만개이므로 최대 O(nlogn) 알고리즘으로 풀어야 겠다고 생각했다. 중복값 입력이 허용되고 그 중 전체 나무 중 차지하는 비율을 찾아야 되기 때문에 한 번 루프가 끝났을 때 그 나무가 나온 횟수를 찾아야 된다고 생각했다! 또한 문제의 핵심은 중복되는 자료가 나왔을 때 얼마나 빠르게 찾아 값을 변경 시키는 것이기 때문에 찾는 것에 시간 복잡도가 O(1)인 해쉬맵을 이용해야겠다고 생각했다. 문제 ..

문제 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 과정 문제의 조건을 봤을 때 A-B-C-D-E 인 관계를 찾으면 되는거라서 탐색을 했을 때 깊이 5까지 파고드는 관계를 찾으면 된다고 생각했다. 그래서 DFS를 이용하였고, 재귀함수를 호출할 때마다 깊이를 1씩 더해주어 깊이가 5가 됐을 때, '찾았다' 라고 표시했다. 하지만 '틀렸습니다.'만 떴다! ㅠ 아직 갈 갈이 멀다. 답이랑 비교했을 때 틀린 점은 2가지가 있었다. 틀린이유 1 : 탐색의 시작을 0번째만 하려고 했다는 것. // 내가 짠 코드 DFS(0, 1); // 답 for(int i=0; i

문제 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 방법 신기한 소수가 되기 위해서는 왼쪽부터 1자리, 2자리, 3자리, 4자리 모두 소수여야 한다. 즉 1자리 부터 소수가 아니면 검사할 필요가 없기에 점점 깊이 파고 드는 재귀함수를 써야 한다고 생각 헀다. => DFS가 적당! 재귀 함수의 깊이가 입력 받은 자릿수가 되면 그 수는 신기한 소수이다. 내가 생각한 알고리즘은 밑과 같았다. 1. 1~9까지 i가 소수이면 findInterestDemical 함수를 호출한다. 인자는 num과 자릿수..

문제 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근 방법 수의 개수 제한은 천 만으로 많은 편에 속하지만 수의 크기는 만으로약 4자릿수가 최대. 이때는 자릿수에 따라 시간 복잡도 결정되는 기수 정렬이 좋은 방법. 기수 정렬 기수 정렬 값을 비교하지 않는 특이한 정렬으로 자릿수를 정한 다음 해당 자릿수만 비교한다. 기수 정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를말한다. 기수 정렬 알고리즘 10개(0~9)의 큐를 이용하여 값의 자릿수를 대표한다. 일의 자릿수부터 10개의 큐에 넣어가며 정렬을 한다. 큐..

문제 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 접근 방법 버블 정렬의 이동은 한 번에 한칸씩만 이동할 수 있다. swap의 횟수를 찾기 위해서는 부분 리스트가 1개가 될 때까지 쪼개고 점점 합병해가면서 합치는 합병 정렬이 알맞다고 생각했지만 합병 정렬은 가까운 요소끼리 먼저 정렬을 하기 때문에 기준 요소와 모두 비교를 진행하고 swap하는 버블 정렬과는 다른 결과가 나올 것이라 생각했다. 책을 보며 풀이법을 봤지만 사실 아직도 이해가 안간다. 버블 정렬은 현재 위치가 정렬이 완료..