본문 바로가기

전체 글

 (386)
백준 15681번 트리와 쿼리 (C++) https://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 접근법 - 먼저 그래프가 주어지고 이것의 루트가 주어진다. 그리고 트리를 구성하게된다. 그래프가 주어지고서 이것을 트리로 바꾸어야하기 때문에, 이것을 문제의 그림으로 표현하면 다음과 같다. 이 그래프에서 5를 루트라고 하였으므로 아래처럼 트리를 구성할 수 있다. 그리고 각 노드들의 서브트리의 노드 개수를 출력하면 된다. 이해하기는 쉽지..
백준 11438번 LCA 2 (C++) https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net LCA 공부를 열심히 하고서 풀이한 문제이다. LCA는 https://tigerfrom2.tistory.com/186 여기서 자세히 설명해두었다. 이 문제는 LCA1과 같은 문제지만 주어지는 노드의 수가 늘어났고, 시간이 더 타이트해졌다. LCA1은 조상을 탐색할 때 1씩 올라가며 탐색해도 AC를 받을 수 있었다. 그러나 이 문제는 dp를 활용하여 LCA를 개선하는 테이블을 미리 만들어둬..
최소 공통 조상 LCA: Lowest Common Ancestor LCA: Lowest Common Ancestor 트리의 노드들 중 공통 조상을 찾는 알고리즘이다. DFS, BFS를 통해 한 노드에서 시작해 모든 간선을 확인해볼수도 있겠지만 이 방법을 사용하면 더 빠르게 찾아낼 수 있다. 위의 상황에서 12번노드와 6번노드의 최소 공통 조상을 찾아보자. 최소 공통 조상은 누가봐도 3이다. 그렇다면 알고리즘으로 어떻게 풀어낼 수 있을까? 레벨을 맞춘다. LCA에서 중요한 것은 레벨을 맞춰야한다. 즉 LCA(6, 12) = LCA(6, 7) 과 같다. 이처럼 레벨(깊이)를 맞춰준 후 동시에 하나씩 조상을 탐색하는 것이 LCA이다. DFS 전처리 LCA를 위해서는 각 노드가 조상의 정보와 레벨의 정보를 가지고 있어야한다. 이를 위해 dfs 전처리가 필요하다. 만들어진 노드..
백준 16562번 친구비(C++) https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 문제 해석을 잘못해서 어렵게 생각하고 있었다. 친구의 친구는 친구라고 해서 인접한 관계만 가능하고 한 칸 이상 떨어지면 안되는 것이라고 생각했다. 그래서 트리에서 다이나믹 프로그래밍을 진행했는데 정답이 아니었다..!! 이 문제는 유니온 파인드였다. 맨 처음 생각난 건 유니온 파인드였는데 문제 해석을 잘못했다. 결국 구해야하는 것은..
DeadLock (교착상태) DeadLock이 무엇이고 언제 발생하는지 저번 포스팅에서 이야기 했지만 복습해보면 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 무한정 대기하는 상태를 교착상태라고 한다. 현실 세계에서 두 차량(프로세스)이 하나의 도로(자원)에 들어가려고 할 때, 둘 중 하나가 양보하지 않는 이상 이 자원에는 누구도 도달할 수 없다. 교착상태의 해결법 예방 교착상태를 예방하려면 어떻게 해야할까? 교착상태는 4가지 필요조건이 있다. 그렇다면 이 조건 중 하나라도 만족하지 않으면 교착상태는 일어나지 않을 것이다. 상호 배제 부정 : 하나의 자원을 여러 프로세스가 접근 가능 → 현실성 X 점유대기 부정 : 프로세스가 실행 전 모든 자원을 할당, 식사하는 철학자의 경우 수저를 한 번에 듦 선점 가능 : 이미 실행..
백준 10282번 해킹 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 처음 문제를 보고 그냥 dfs 풀이하면 된다고 생각했다. 왜냐면 그냥 모든 노드를 돌며 시간을 더하면 된다고 봤다. 그러나 이런 케이스를 생각해야한다. 1 | \ 2 - 3 여기서 1 - 2 는 8초 1 - 3은 2초 2 - 3은 1초라 하자. 그렇다면 1이 감염되었을 때, 2초후 3이 감염되고 3이 감염되고 1초 후 3이 감염되므로 3초면 모두가 감염된다. 그러나 그냥 dfs를 돌아서 2에 먼저 방..
백준 3584번 가장 가까운 공통 조상 (C++) https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 우선 이 문제를 처음 접했을 때, 난 LCA알고리즘의 존재를 모르고 풀었다. 때문에 이 풀이가 100퍼센트 맞는 정답이라고는 말할 수 없다. 하지만 코딩테스트에서 모르는 알고리즘이 나와도 풀이할 수 있어야한다. LCA에 대해서는 다음 포스팅에 할 예정이다. 각 자식들은 단 하나의 부모를 가지고 있다. 먼저 A의 조상을 타고 올라간다. 그렇다면 루..
백준 1107번 리모컨 (C++) https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 내 접근 - Greedy 문제라고 생각했다. 만약 4987 인데 9가 금지라면 9대신에 가장 근접한 8을 배치하고 49XX보다 48XX가 더 작으므로 격차를 최소로 하기 위해 사용할 수 있는 가장 큰 값을 배치하여 4888로 지정하고 4987 - 4888 + 자리수 = 103 이렇게 생각했다. 그러나 이러면 자리수가 바뀔 때를 계산할 수 없다. 예를 들어 9998 이고 9가 금지..

티스토리툴바