분류 전체보기
-
[백준] 1949번 우수마을문제 풀이 2020. 8. 23. 17:34
1949 우수마을 풀이)백준 2533번 사회망서비스 문제랑 똑같이 dp를 사용해서 풀면 된다.사회망 문제 설명) https://comyoung.tistory.com/41 +)트리는 사이클이 없는 무방향 그래프이므로 어느 정점에서 시작하든 상관없다. 나같은 경우는 1번 마을을 트리의 root라고 생각하고 시작해줬다. 주의사항처음에 트리 구현할 때무조건 번호 작은 노드가 번호가 큰 노드의 부모이게 만들어, 양방향으로 마을을 연결되지 않게 했었다.이렇게 풀면 트리가 제대로 구현되지 않아 틀리게 된다.반례) 1-3, 2-3 코드) 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include us..
-
CCW알고리즘 2020. 8. 23. 16:43
CCW(CounterClockWise) Algirothm - 개념: 반시계 방향 알고리즘 평면 위에 놓여진 세 개의 점을 벡터의 외적을 이용해서 방향 관계를 찾는 알고리즘. 자세한 설명) https://degurii.tistory.com/47 - 2차원 평면상에 각각 x, y 좌표를 갖고 있는 세점 (p1, p2, p3)가 존재한다고 했을 때, CCW 공식 s = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x) 만일 결과값 s가 0보다 작다면(s 0) p1, p2 벡터를 기준으로..
-
[백준] 4386번 별자리 만들기문제 풀이 2020. 8. 22. 17:44
4386 별자리 만들기 문제도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것다. 별자리의 조건은 다음과 같다-별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.-모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. 입력첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다. 출력첫째 줄에 정답을 출력한다...
-
[백준] 1197번 최소 스패닝 트리문제 풀이 2020. 8. 22. 17:28
1197 최소 스패닝 트리 문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 ..
-
[백준] 1717번 집합의 표현문제 풀이 2020. 8. 21. 18:43
1717 집합의 표현 문제초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오. 입력첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a..
-
LCA알고리즘 2020. 8. 21. 18:36
LCA(Lowest Common Ancestor) - 개념: 트리에서 두 개의 정점를 선택하였을 때 최소 공통 조상(가장 가까운 공통 조상)을 찾는 알고리즘 - 구현방법 정점의 깊이를 저장하는 배열 depth[i] = i번 정점의 깊이 각 정점의 부모를 저장하는 배열 parent[i] = i번 정점의 부모 있다고 할때 1. 간단한 방법 : ① 두 정점 중 깊이가 더 깊은 정점를 찾아, 깊이가 같아질 때까지 그 정점의 부모로 계속 이동한다. ex) 정점 A, 정점 B if depth[A] > depth[B] // A정점이 깊이가 더 깊음 while(depth[A] != depth[B]) A = parent[A] ② 높이가 같아졌다면, 두 정점이 같아질 때까지 두 정점을 동시에 부모로 이동한다. while(..
-
[백준] 2263번 트리의 순회문제 풀이 2020. 8. 20. 22:22
2263 트리의 순회 문제n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.입력첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.출력첫째 줄에 프리오더를 출력한다. 풀이)순회방법을 미리 알았어야 풀기 쉬운 문제이다. 다음과 같은 트리가 있을 시 1. inorder : 중위순회 - left→root→right순으로 읽는다. - 위의 그림을 읽는 순서 : 2→1→3 2. postorder : 후위순회 - left→right→root 순으로 읽는다. - 위의 그림을 읽는..
-
[백준] 13913번 숨바꼭질4문제 풀이 2020. 8. 19. 17:18
13913 숨바꼭질4 문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.둘째 줄에 어떻게 이동해야 하는지 공백으로 구..