공작소

>> 문제 바로가기 (https://www.acmicpc.net/problem/3584) 문제 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다. 예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다. 루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을..

도입 이 글은 재귀 알고리즘에 대한 설명을 담고 있습니다. 프로그래밍 언어를 공부하다보면, 함수 혹은 메소드에 대해 배우면서 접할 수 있는 알고리즘이 바로 재귀입니다. 사실 재귀는 반복문을 실행하는 것보다 메모리 측면에서 비효율적이라는 의견도 존재하지만 (함수를 종료시키지 않은 채로 계속 실행하기에) 잘 사용하면 문제를 다른 시선으로 바라볼 수 있으며, 복잡한 문제 상황을 간결한 코드로 해결할 수도 있는 알고리즘입니다. 재귀 알고리즘을 학습하고 여러 문제 상황에 대응할 수 있는 능력을 기르는 것이 이 글의 목적입니다. 본 글은 C를 기반으로 작성되었습니다. 접근 https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로..

문제 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자. 1. -가 3N개 있는 문자열에서 시작한다. 2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다. 3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다. 예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다. --------------------------- 여기서 가운데 문자열을 공백으로 바꾼다. ---------..