복습 정리 노트

이 포스트에서는 LCA, 최소 공통 조상 알고리즘에 대한 구현과 예시 문제 풀이를 다루고 있습니다. 예시 문제로는, 프로그래밍 문제 사이트 백준 Online Judge의 11438번 : 'LCA 2' 문제에 대한 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum V에 해당합니다. 11438번 : LCA 2 문제 자체가 LCA 알고리즘을 설명하기에 최적화 되어있는 문제이기에, 그냥 문제를 풀이하면서 설명해보도록 하겠습니다. 첫째 줄에 노드의 개수 N이 주어지고, N-1개의 트리 사이에 연결된 간선에 대한 정보가 주어져 트리가 입력됩니다. 이후 M개의 두 노드 쌍에 대해, 각 노드 쌍이 가지는 최소 공통 조상을 구해 출력해주는 문제입니다. 이 문제는 문제의 이름 그..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 Bronze III 난이도에 해당하는 문제들의 풀이 코드와 간략한 해설을 다룰 것입니다. 풀 문제의 수는 총 20문제이고, 포스트 길이가 길어질 수 있기 때문에 간단하게만 설명을 언급하고 넘어가도록 하겠습니다. 5217번 : 쌍의 합 #include using namespace std; int main() { int T, n; scanf("%d", &T); for(int i=0; i= y && a >= c*2) printf("%d", 2*c*x); else if(x = c*2) printf("%d", 2*c*y); else if(a+b

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 Bronze III 난이도에 해당하는 문제들을 풀이할 것입니다. 문제의 난이도가 아주 쉬우므로, 풀이 코드와 함께 간단한 설명만 언급하고 넘어갈 것입니다. 또한 이 포스트에서는 20문제를 풀이할 예정입니다. 2863번 : 이게 분수? #include using namespace std; int main() { double a, b, c, d, Max = 0; int i, idx = 0; scanf("%lf %lf %lf %lf", &a, &b, &c, &d); for(i=0; i Max) Max = a/c + b/d, idx = i; int temp = a; a = c, c = d, d = b, b = temp; } printf("%d..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 Bronze III 난이도의 문제들에 대한 풀이 코드와 해설을 다루고 있습니다. 10824번 : 네 수 #include #include using namespace std; int main() { string a, b, c, d; cin >> a >> b >> c >> d; string N = a+b, M = c+d; cout > a >> b; for(int i=1; i

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 Bronze IV 문제들 중 외국어 문제들을 위주로 풀이할 것입니다. 난이도가 Bronze IV로 풀이가 매우 간단하기에 풀이 코드와 간단한 해설만 첨언할 것입니다. 20353번 : Atrium #include #include using namespace std; int main() { double a; scanf("%lf", &a); printf("%.7lf", sqrt(a)*4); } 정사각형의 면적이 주어질 때 정사각형의 둘레를 출력하는 문제입니다. 20232번 : Archivist #include using namespace std; int main() { int n; scanf("%d", &n); if(n == 1996 || ..

백준 Online Judge의 Bronze 문제들을 간략하게 풀이만 정리해두도록 하겠습니다. 풀이할 문제들의 번호는 20499번, 19698번, 18408번, 19602번, 21598번, 18411번, 18414번, 20673번, 20976번, 18330번입니다. (풀이한 문제 수가 적어서 랭킹을 위해 브론즈 문제들을 풀이할 것입니다.) Ctrl-F로 번호에 대응되는 코드를 찾으면 조금 더 수월합니다. 20499번 : Darius님 한타 안 함? 1 2 3 4 5 6 7 8 9 10 #include using namespace std; int main() { int K, D, A; scanf("%d/%d/%d", &K, &D, &A); if(K+A= Ans) printf("%d", Ans); else p..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 1516번 : '게임 개발' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Gold 티어에 해당하며, 문제를 풀이하기 위해 위상 정렬(Topological Sort)의 개념을 다룰 것입니다. 1516번 : 게임 개발 위와 같이 N개의 건물에 대해, 각 건물을 짓는 시간이 주어지고 그 건물을 짓기 위해 먼저 지어져야 하는 건물의 번호가 주어질 때, 각 건물이 완성되기까지 걸리는 최소 시간을 각각 출력하는 문제입니다. 건물의 번호들을 각 노드로 만들고, 선행 건물들을 연결하여 위상 정렬 알고리즘을 이용하여 해결할 수 있는 문제입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

최근 한 2주동안 백준 문제를 열심히 풀었더니 Platinum 티어를 달성할 수 있었습니다. 플레티넘 티어를 달성하면서 느낀 것은, 확실히 티어 제도가 문제를 열심히 푸는 데에 도움을 주는 것 같습니다. 특히 그동안은 쉬운 문제를 많이 풀기도 했는데, 어려운 문제가 티어를 빨리 올려주다 보니 어려운 문제에 대한 접근도 많이 하게 해주는 것 같습니다. 다만 특정 알고리즘의 경우 한 번 공부만 해놓으면 살짝만 응용해서 쉽게 풀이가 가능하기 때문에 꼼수 아닌 꼼수가 존재하기도 하는 것 같습니다. 그래도 그렇다고 해서 어려운 알고리즘을 사용하는 문제의 난이도를 낮게 할 수 없으므로 어쩔 수 없는 것 같습니다. (이 부분이 아마 패치가 된다면 문제 분야의 다양성과 균등성을 티어 기준에 추가할 것 같기도 합니다.)..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 2699번 : '격자점 컨벡스헐', 6194번 : 'Building the Moat', 10903번 : 'Wall construction' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum에 해당하며, 문제를 풀이하기 위해 Convex Hull 알고리즘이 응용되므로, 이에 대해 알고 있으면 좋습니다. 2699번 : 격자점 컨벡스헐 먼저 테스트케이스의 수가 입력되면, 해당 테스트케이스 수만큼의 아래의 처리를 수행해야 합니다. N개의 점에 대해 가장 큰 볼록다각형(꼭짓점들로 이어진 볼록다각형이 나머지 점들을 모두 내부에 포함하는 다각형)을 구성하는 꼭짓점들의 수를 출력하고, 이들 중 y좌표가 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 1708번 : '볼록 껍질' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum V에 해당하며, 문제를 풀이하기 위해 Convex Hull, 컨벡스 헐 알고리즘에 대해 다룰 것입니다. 1708번 : 볼록 껍질 2차원 좌표계로 N개의 점이 입력될 때, 이 점들 중 가장 큰 볼록다각형의 해당하는 점의 개수를 찾아서 출력하는 문제입니다. 단순히 보면 어렵지 않을 수도 있을 것이라는 생각이 들 수도 있지만, 기하적인 개념을 좌표계의 계산과 코드로 옮기는 과정이 생각보다 쉽지 않습니다. 점들을 정렬하고, 그 방향성을 정렬하는 데에 생각보다 많은 개념이 필요하며, 이것을 아래에서 다루겠습니다. 1 ..