백준

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 사용한 알고리즘 : LCA(Lowest Common Ancestor, 최소 공통 조상) 풀이 전략 위 문제에서 주어진 첫 번째 입력을 그래프로 나타내면 아래와 같다. 문제에서는 16과 7의 가장 가까운 공통 조상인 LCA를 구하라고 주어졌다. 결론부터 말하면 눈에 보이듯 4인데, 이를 알고리즘적으로 어떻게 구할 수 있을지 생각해보자. 먼저 LCA..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 사용한 알고리즘 : BFS 풀이전략 모든 경우의 수를 BFS를 사용해 완전탐색하는 문제이다. 물통에서 물을 옮길 수 있는 경우의 수는 총 6가지로, 1. A물통-> B물통 2. A물통-> C물통 3. B물통 -> A물통 4. B물통 -> C물통 5. C물통 -> A물통 6. C물통 -> B물통 이 있다. 그런데 물을 옮길 때 조건으로 한 물통이 빌 때까지 물을 다른 물통에 쏟거..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 사용한 알고리즘 : 세그먼트 트리 풀이전략 만약 완전 탐색을 통해 문제를 푼다고 생각해보자. 그러면 최악의 경우, 수의 개수 N = 1,000,000 , 수 변경 횟수 M = 10,000, 구간 곱 구하는 횟수 K = 10,000으로 1,000,000 * (10,000+10,000) = 20,000,000,000(200억)번의 연산이 ..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 사용한 알고리즘 : 위상정렬(Topological Sorting) 풀이전략 문제들을 주어진 이전 단계를 거쳐가야만 풀 수 있으므로 위상 정렬 알고리즘을 사용해야한다. https://chaechaeros.tistory.com/199 [BOJ 1766] 문제집 - JAVA, Gold2 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 사용한 알고리즘 : 위상정렬(Topological Sorting) 풀이전략 위상정렬에 대해 먼저 알아야하는데 아래 유튜브 링크를 참조하여 개념을 작성했다. https://www.youtube.com/watch?v=xeSz3pROPS8 위상정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 위와 같은 방향 그래프가 주어졌을 ..

https://www.acmicpc.net/problem/17205 17205번: 진우의 비밀번호 진우는 비밀번호 조합을 a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaab, aaaaac, ..., azzzzx, azzzzy, azzzzz, b 순서로 시도한다. www.acmicpc.net 사용한 알고리즘 : 수학, 중복순열 풀이전략 3 ca 위와 같은 입력이 주어졌다고 생각해보자. 그러면 비밀번호 시도 순서는 아래와 같을 것이다. a aa aaa ~ aaz - 26개 ab aba ~ abz - 26개 ... az aza ~ azz - 26개 b ba baa ~ baz ~26개 bb bba ~ bbz - 26개 ... bz bza ~ bzz - 26개 c ca -------------..

https://www.acmicpc.net/problem/1354 1354번: 무한 수열 2 첫째 줄에 5개의 정수 N, P, Q, X, Y가 주어진다. www.acmicpc.net 사용한 알고리즘 : Map 데이터 구조를 사용한 풀이 풀이 전략 Map 데이터구조를 이용하여 이미 구해놓았던 값은 다시 연산하지 않도록 했다. static Map map = new HashMap(); // 전역 변수로 선언되어있음 map.put(0L,1L); // main 함수에서 정의되었음 static long func(long num){ if(map.containsKey(num)) return map.get(num); if(num

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 사용한 알고리즘 : LIS(Longest Increasing Subsequence), 이분 탐색 풀이전략 LIS를 구하기 위한 전략은 아래와 같다. 위 그림처럼 입력받은 수가 수열의 최우측 원소와 비교했을 때 더 작다면 기존에 입력된 수열에서 같거나 더 크지만 가장 작은 수와 교체한다. 만약 입력받은 수가 수열의 최우측 원소보다 크다면, length의 길이를 1 늘리고 수열 최우측 바로 옆 인덱스..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 사용한 알고리즘: DP 풀이전략 펠린드롬수는 쉽게 말해서 앞으로 읽으나 뒤로 읽으나 같은 수를 뜻한다. 문제 해결 접근 방식으로 질문이 주어질 때마다 해당 수가 펠린드롬 수인지 파악하려고 한다면 최악의 경우 1,000,000번의 펠린드롬 수 판단 연산을 수행해야 한다. 수열의 크기가 최대 2000까지 가능하므로 최악의 경우 2000 * 1,000,000 = 2,000,000,000(20억)번 연산이 필요하다. 이는 JAVA가 초당 1억..

https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 사용한 알고리즘: 모노톤 스택(Monotone Stack) 풀이전략 https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/ monotone stack monotone stack은 몇몇 문제들의 시간 복잡도를 O(n)정도로 줄어주는 강력한 테크닉입니다. justicehui.github.io 먼저 문제를 풀기위해서는 mo..