공작소

문제 링크 : https://www.acmicpc.net/problem/2630풀이 과정분할 정복으로 풀이했다.합치는 과정에서, (1) 특정 색의 색종이가 4등분한 영역에서 각각 1개이고, (2) 다른 색의 색종이가 4등분한 영역에서 각각 0개라면, 특정 색의 색종이 1장으로만 해당 영역이 구성된 것으로 결과를 반환한다.전체 코드# 2630 : 색종이 만들기import sysinput = sys.stdin.readlinen = int(input().rstrip())arr = [list(map(int, input().rstrip().split())) for _ in range(n)]def func(i, j, size): if size == 1: return [1, 0] if arr[i]..

문제 링크 : https://www.acmicpc.net/problem/1074풀이 과정2xN 배열을 4등분 했을 때 어느 방향으로 갈지에 따라 다르게 탐색하는 재귀함수를 작성하여 풀이했다.전체 코드# 1074 : Zimport sysinput = sys.stdin.readlinedef func(size, start, sr, sc, er, ec): if size == 0: print(start) return # -- 4등분 했을 때 # 왼쪽 위에 있다면 if sr

>> 문제 바로가기 (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인 문자열로 시작한다. --------------------------- 여기서 가운데 문자열을 공백으로 바꾼다. ---------..