목록백준 (142)
mojo's Blog
임의의 실수 x에 대하여 factorize 하는 방법 [2, N^(1/2)] 의 수들로 나눠 볼 때 나누는 수가 소수인지 확인할 필요가 없다!!! 만약에 N이 2로 나눠 떨어진다면 N값을 2로 나눠서 다시 2로 나눠 떨어지는지를 확인하고 그렇지 않은 경우 3으로 나눠 떨어지는지 확인하고 ... 반복한다. 이 과정을 반복하면 소수가 아닌 인수는 자연스럽게 없어지는 것을 확인할 수 있다. 따라서 Time Complexity O(N^(1/2)) 이 나온다. factorize 하는 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #defi..
[백준 1761] 정점들의 거리
문제 링크 => 1761번: 정점들의 거리 (acmicpc.net) 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 정점과 정점사이의 거리를 구하는 문제이다. 이 문제 역시 LCA 문제인데 다음과 같은 그림을 통해 해당 수식을 이해하기 전에 간단하게 배열들에 대한 설명을 하자면 다음과 같다. parent[x][y] => x 노드의 2^y 의 부모 depth[x] => x 노드의 깊이, 보통 1을 0으로 잡는다. path[x] => 1부터 x까지 연결된 노드의 길이 그렇다면 두 노드를 LCA를 통해 어..
[백준 11438] LCA 2
문제 링크 => 11438번: LCA 2 (acmicpc.net) 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 트리를 이용한 최소 공통 조상을 찾는 문제이다. 이문제는 LCA 11437번: LCA (acmicpc.net) 이 문제와 다르게 N 값이 100,000으로 주어졌다. 따라서 1차원 배열로 해결할 경우 시간 초과가 발생한다. 따라서 부모배열을 1차원 배열이 아닌 2차원 배열로 변경하여 parent[x][y] 로 수정해준다. parent[x][y] => x의 노드에서 2^y 위에 존재하는 부모..
[백준 11437] LCA
문제 링크 => 11437번: LCA (acmicpc.net) 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 트리에서 최소 공통 조상을 구하는 문제이다. 아이디어는 1을 최상단 노드로 잡아서 각 노드들의 부모 노드, 깊이등을 설정한 후, 임의의 두 노드의 가장 가까운 공통 조상을 찾도록 하는 것이다. 부모 노드를 표현하기 위한 배열 parent[x] 와 깊이 배열 depth[x] 을 먼저 살펴보면 다음과 같다. parent[x] : x의 부모 노드 depth[x] : x의 깊이 (0, 1, 2, 3, ...
[백준 2146] 다리 만들기
문제 링크 => 2146번: 다리 만들기 (acmicpc.net) 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 전형적인 BFS 문제이다. 먼저 대륙별로 숫자를 매기도록 하였다. (1번 대륙, 2번 대륙, ..., i번 대륙) 그리고 각 육지별로 BFS 를 돌려서 바다로 이동이 가능하며 다른 대륙을 발견한 경우 거리를 return 하도록 하여 그 거리들 중에 최솟값이 정답이 된다. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #include #include #includ..
[백준 16947] 서울 지하철 2호선
문제 링크 => 16947번: 서울 지하철 2호선 (acmicpc.net) 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net BFS + DFS 짬뽕 문제이다. 이 문제는 역과 역 사이의 방향이 양방향으로 주어졌고 핵심은 순환이 되는 순환선 즉, 한 역에서 출발해서 계속 가다가 다시 출발한 역으로 돌아올 수 있는 노선을 구분짓는 것이다. 1. 순환선은 DFS 를 활용하여 판별하였다. 판별 방법은 한 역에서 출발해서 계속 가다가 다시 출발한 역으로 돌아올 수 있다는 점을 다음과 같이 해결하..