boj, 백준) 15681. 트리와쿼리 ( C/ C++)
1. 문제 링크 www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 2. 문제 개요 간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자. - 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 3. 문제 힌트 정점의 개수가 100,000개. 쿼리의 개수도 100,000개. 쿼리를 입력 받을 때, O(n^2)의 시간으로 처리했다가는 제 시간 안..
boj, 백준) 1637. 날카로운 눈 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/1637 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 2. 문제 개요 정수더미 속에서 날카로운 눈을 이용해 홀수개 존재하는 정수를 찾아야 하는 문제이다. 근데, 정수더미 안에 정수가 적게 있으면 문제가 너무 쉬워지게 된다. 그래서, 정수더미안에 정수를 무지막지하게 많이 넣기로 했다. 정수더미가 주어졌을 때, 그 안에 홀수개 존재하는 정수를 찾는 프로그램을 작성해보자. 3. 문제 힌트 정말 간단하..
boj, 백준) 2166. 다각형의 면적 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 2. 문제 개요 2차원 편명상에 N개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오. 3. 문제 힌트 외적을 사용하자. 두 벡터를 외적한 것은 두 벡터로 만들어지는 평행사변형의 넓이를 나타냄. 4. 문제 풀이 (다른 블로그에서도 좋은 풀이가 있었으나, 중요한 기초 개념인 것 같아 업로드 합니다.) 우선, 다각형은 엄청 찌그러질 수 있기 때문에... 크기를 쪼개고 쪼개서 넓이를 구한 뒤 ..
최소 공통 조상 (LCA, Lowest Common Ancestor)(C/C++)
여러 자료를 참조하면서 LCA를 공부했는데, 어떤 자료는 너무 쉽고 깔끔하지 못하고, 어떤 자료는 난이도가 있고 깔끔하게 설명된 자료였습니다. 그래서 여러 자료를 찾아보며 이해하고, 또 이해하느라 조금 복잡했는데, 하나의 블로그에서 LCA의 개념부터 구현까지 공부할 수 있으면 어떨까 해서 기록을 합니다. 개념에 대해서 알아보고, 백준(BOJ)의 간단한 LCA문제를 풀어보면서 글을 마치겠습니다. 다른 분들에게 도움이 되었으면 좋겠습니다. 1. LCA란? 참조(en.wikipedia.org/wiki/Lowest_common_ancestor) 'In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w i..
boj, 백준) 11779. 최소비용 구하기2 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 문제 개요 간선이 주어지고 출발지, 도착지의 정점 번호가 주어질 때, 출발지, 도착지까지의 최단거리, 경로를 구하는 프로그램을 작성하시오. 3. 문제 힌트 (1) 인접 리스트로 나타낼 것. -> 한 정점에서 다른 정점까지의 간선이 1개라면 행렬로 나타내어도 괜찮다. 그런데 한 정점에서 다른 정점까지 간선이 여러 개 있을 수 있으니 인접 리스트로 나타내어야 한..
boj, 백준) 5022. 연결(C/C++)
1. 문제 링크 www.acmicpc.net/problem/5022 5022번: 연결 A1과 A2, 그리고 B1과 B2를 연결하는데 필요한 전선의 길이의 최솟값을 출력한다. 만약, 불가능한 경우에는 "IMPOSSIBLE"을 출력한다. www.acmicpc.net 2. 문제 개요 전기 회로에서 두 점을 전선으로 이을 때, 길이는 짧을수록 좋다. 크기가 N x M인 비어있는 회로판에서 두 점 A1, A2, 그리고 B1, B2를 전선을 이용해서 이으려고 한다. 전선은 항상 그리드의 수직, 수평선 위에 있어야 한다. 또, 두 직선은 접하면 안 된다. 이 경우에 필요한 전선의 길이의 최솟값을 구하는 프로그램을 작성하시오. 전선은 회로판 바깥으로 나갈 수 없다. 3. 문제 힌트 (1) (A1--A2) (B1--B2..