본문 바로가기

전체 글

 (336)
최소 공통 조상 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가 금지..
백준 11000번 강의실 배정 (C++) https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 이전에 풀었던 BOJ문제 공주님의 정원 문제와 비슷하다고 하여 풀어봤다. 공주님 문제를 어렵게 느꼈고 깨달은 것이 많은 문제여서 비장한(?) 마음으로 임했다. 먼저 최대한 수업시간들이 이어져있도록 꼬리물기를 시켜야한다. 그러므로 한 수업이 끝나고 다음 수업들의 수업을 스캔하는 과정이 필요하다. 1 2 1 2 2 7 2 4 3 7 이라고 가정하자. 그렇다면 먼저 1~2 수업을 할 것이다. 그리고 다음 수업시간의 시작 시간과 이전 수업 시간의 끝나..
백준 2457번 공주님의 정원 (C++) https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 처음 문제를 보고 투포인터 이분탐색이 생각났다. 처음 꽃은 반드시 3월 1일 이하부터 피어야하고 마지막 꽃은 12월 1일 이하에 져야한다. 그러므로 각 포인터들을 이동시켜서 최적의 조건을 만든 후 checking 절차를 하면 된다고 생각했다. 결론적으로 말하면 위 방법이 완전히 틀린 것은 아니지만 이렇게할 필요도 없고 문제의도와 맞지 않다. 이 문제의 의도는 Greedy 이다...

티스토리툴바