Partially Committed

최근 풀었던 문제 중에 가장 재밌었던 것 같아서 오랜만에 백준 포스팅 😊 9019번: DSLR (acmicpc.net) 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제를 간단하게 요약하자면 초기값 A 목표값 B 가 주어지면 아래 4가지 연산을 통해서 B로 도달할 수 있는 경로를 출력하는 것이다. D 연산: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S 연산: S 는 n..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 재귀는 항상 어려운 것 같다.. 🥺 위 문제는 조금 특이한데, InOrder Traverse 와 PostOreder Traverse 가 주어졌을 때 PreOrder Traverse 를 출력하는 것이 요구 사항이다. 음.. 일단 Tree 의 순회에서 기준이 되는 것은 Root 노드이다. InOrder 와 PostOrder 는 주어지는데, 이로부터 Root 노드를 어떻게 찾을 수 있을까? PostOrder 는 left - ri..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 상황은 되게 단순하다. 가중치가 존재하는 트리 구조가 주어졌을 때, 임의의 A 노드부터 B 노드까지의 경로가 존재할 것이고 그 중 최장 경로를 트리의 지름이라고 정의한다. 트리의 지름을 반환하면 된다. 음.. 어떻게 풀지? 일단 시간 제한은 2초로 평범한 편이고, 데이터를 보니까 노드의 개수는 100000 개이다. 에지의 개수는 주어지지 않았으나, 최대 100000 - 1 개..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net N 명의 선수가 선분을 번갈아가면서 그리는 게임을 M 차례까지 진행했을 때, 중간에 사이클이 생긴다면 사이클이 생겼던 회차를, M 번 진행하는 동안 사이클이 발생하지 않았다면 0 을 출력하면 된다. 예제를 통해 생각해보자. 0 과 1 을 선택하여 0-1 선분을 긋는다는 것은 0 과 1 은 같은 집합으로 Clustering 된다는 것이다. m 번의 회차마다 주어지는 두 포인트를 같은 집합으로 ..