알고리즘/백준(30)
-
[백준] [C++] 11266번 단절점 (dfs)
1. 문제 단절점이란 한 노드와 인접한간선들을 모두 지웠을 때 해당 컴포넌트가 두개 이상으로 나뉘어지는 정점이다. 11266번: 단절점 (acmicpc.net) 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 2. 무향 그래프 단절점 찾기 : dfs dfs 스패닝 트리를 생성하고 나면 모든 간선을 4가지로 분류할 수 있다. 그 중 단절점 찾기에서 중요한 간선은 역방향 간선으로, 자손 노드에서 선조 노드로 연결된 간선이다. 한 노드의 자손노드들이 모두 이런 역방향 간선을 통해 그 노드..
2021.07.21 -
[백준] [C++] 1761번 정점들의 거리 (LCA, segment tree)
1. 문제 1761번: 정점들의 거리 (acmicpc.net) 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 2. 풀이 이 문제는 주어진 입력을 트리로 표현하고 모든 노드를 루트까지 거리를 구해 주어진 질의 a , b 에 대하여 다음을 답해야한다. depth(a) + depth(b) - 2depth(lca) (이 식은 구간합과 유사한 형태로, 증명또한 비슷하게 할 수 있다.) 3. 트리 재구성 : 구간트리 LCA는 최소 공통 조상이다. 특정 구간이 주어질때 그에 대해 질의를 답해줄 수 있는 구간 트..
2021.07.20 -
[백준] [C++] 1708번 볼록 껍질 (geometry)
1. 문제 1708번: 볼록 껍질 (acmicpc.net) 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 2. 풀이 선물포장 알고리즘 1) 가장 왼쪽 아래인 점을 찾아 컨벡스헐에 포함시킨다. 2) 이 점을 기준점으로 삼는다 3) 컨벡스헐에 마지막에 넣은것을 기준으로 가장 왼쪽에 있는 점을 찾아 포함시킨다. 4) 이 점이 처음 정한 기준점이 될때까지 3번을 반복한다. 3번에서 모든점을 검사해야한다. 따라서 점 H개가 컨벡스 헐에 포함되면 O(NH) 의 시간복잡도를 가지게 된다. * hypo..
2021.07.19 -
[백준] [C++] 11689번 GCD(n, k) = 1 (오일러 피 함수)
1. 문제 11689번: GCD(n, k) = 1 (acmicpc.net) 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 오일러 피 함수는 n과 서로소인 1부터 n까지의 정수를 리턴하는 함수이다. 오일러 피 함수 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) 오일러 피 함수 - 위키백과, 우리 모두의 백과사전 오일러 피 함수의 그래프. ϕ(1)부터 ϕ(1000)까지의 값들을 나타낸다. 수론에서 오일러 피 함수(-函數, 영어: Euler’s phi (totient) function)는 정수환의 몫환의 가역원을 세는 함수이다. 즉,..
2021.07.15 -
[백준] [C++] 3015번 오아시스 재결합 (stack)
1. 문제 3015번: 오아시스 재결합 (acmicpc.net) 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 2. 풀이 이 문제의 핵심은 같은 키를 가진 사람들이다. 문제의 정의에의해 같은 키를 가진 사람들이 연속적으로 줄을 서고 있을때 서로를 볼 수 있기 때문이다. 따라서 pair를 사용하여 같은 키인 사람의 수를 따로 저장하여 처리해야한다. 알고리즘은 다음과 같다 1) 앞에서부터 스택에 담는다 2) 스택에 담기전 스택의 top 보다 큰값이면 스택의 top이 더 큰값이 올때까지 p..
2021.07.14 -
[백준] [C++] 2533번 사회망 서비스(SNS) (dfs, greedy)
1. 문제 2533번: 사회망 서비스(SNS) (acmicpc.net) 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 유사한 문제: [그래프] GALLERY 감시 카메라 설치 (tistory.com) [그래프] GALLERY 감시 카메라 설치 1. 문제 모든 방을 감시할 수 있게 감시 카메라를 최소한으로 설치해야한다. 이때 방은 모두 트리 간선을 이루고 있다고 한다. (연결되지 않은 방 또한 있다.) 어떤 방에 카메라를 설치했다고 하 nsgg.tistory.com 2. 풀이 이 문제는 탐욕법으로 문제를..
2021.07.13