사이클 판별 알고리즘은 앞선 포스팅인 서로소 집합 알고리즘을 이용한 알고리즘입니다. 그림과 같이 노드 1, 2, 3이 있고 각각의 연결이 서로를 가리키게 되어있다고 가정합시다.
이 경우 앞선 서로소 집합 알고리즘의 find_parent를 이용하면 노드1의 부모는 노드 1, 노드 2의 부모는 노드 1, 노드 3의 부모는 노드 1로 모든 노드의 부모가 각각 노드 1 임을 확인할 수 있습니다. 따라서 사이클이 발생을 했다는 것을 알 수 있습니다. 그러므로 사이클 판별 알고리즘의 경우 두 노드를 확인한 후 부모 노드가 다르다면 union_parent 함수를 수행해주고 부모 노드가 같다면 사이클이 존재한다는 것을 출력한 뒤 함수를 종료하면 되는 것입니다. 소스코드는 다음과 같습니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [0] * (1+ v)
for i inrange(1, 1+ v):
parent[i] = i
cycle =False
for i inrange(e):
a, b = map(int, input().split())
if find_parent(parent, a) == find_parent(parent, b):
이 문제는 재귀 함수와 관련이 된 문제였습니다. 하노이 탑에서 각각의 원판을 이동시킬 때 제약조건에 맞추어서 이동을 시켜야 합니다. 하노이 탑에서 원판을 이동하는 과정을 재귀로 표현하는 것의 핵심은 원판의 이동하는 과정을 점차 점차 작게 줄여나가는 데 있습니다. 먼저 원판이 3개 A, B, C 방식으로 이루어져 있다면 이는 다음과 같습니다.
A를 1번에서 3번으로
B를 1번에서 2번으로
A를 3번에서 2번으로
C를 1번에서 3번으로
A를 2번에서 1번으로
B를 2번에서 3번으로
A를 1번에서 3번으로
이는 다시 말하면 A,B를 2번 기둥으로 옮긴 후 C를 3번 기둥으로 옮기고 다시 A, B를 3번 기둥으로 옮기는 것입니다.
A, B, C, D의 경우도 마찬가지로 A, B, C를 옮기는 경우에 D를 더 옮기는 경우라고 볼 수 있습니다.
A, B, C, D, E의 경우도 마찬가지로 A, B, C, D를 옮기는 경우에 E를 더 옮기는 경우라고 볼 수 있습니다.
이를 일반화 하면 N개를 옮기는 경우 N-1을 옮기는 경우와 1개를 옮기는 과정으로 바꿀 수 있다는 것입니다.
문제 해결을 위한 팁
문제를 살펴보면 N이 20 이하인 경우 출력 예시처럼 출력을 하고 그 외의 경우 즉 20을 초과하는 경우는 단순히 몇 번을 옮겨야 하는지만 출력하라고 하였습니다. 이는 숫자가 너무 커져 메모리 초과를 막기 위한 조건입니다. 따라서 이는 재귀를 통해 횟수를 구하는 것이 아닌 일종의 점화식을 구하라는 것을 문제에서 암묵적으로 힌트를 주는 것임을 알 수 있습니다. 그렇다면 규칙을 파악해봅시다.
이 문제는 상당히 쉬운 문제였습니다. 단순히 입력받은 점수를 반으로 나누어서 좌측 영역의 합을 구하고 우측 영역의 합을 구한 뒤 두 합끼리 비교를 하여 같으면 LUCKY를 다르면 READY를 출력해주면 됩니다.
문제 해결을 위한 팁
팁이라기보다 문법적인 내용이라고 할 수 있겠습니다. 처음에 점수를 입력받을 때 point = int(input())의 형태로 int형으로 입력받는다면 문자열의 길이를 구하는 len()의 매개변수로 point를 사용할 수 없습니다. int형태이기 때문입니다. 따라서 저는 처음에 점수를 입력받을 때 len()를 사용하기 위해 point = input()으로 문자열로 입력받았습니다.
예제 0001100을 보면 연속적으로 이루어진 000, 11, 00 이 존재하는 것을 알 수 있다. 문제를 잘 살펴보면 연속되어 있는 숫자는 모두 뒤집을 수 있기 때문에 연속되어있는 11을 뒤집으면 단 한 번의 행동을 통해 문자열 S의 모든 숫자를 전부 같게 만들 수 있다는 것을 알 수 있다. 따라서 이 문제는 문자열 S에서 연속되어있는 숫자들의 개수를 구한 뒤 그 최솟값을 출력을 하면 되는 쉬운 문제이다. 예시를 들어보자
1) 10101
이 경우 앞에서부터 조회하면서 1의 개수는 3개 0의 개수는 2개임을 알 수 있다. 따라서 둘중 적은 수인 2를 출력한다
2) 100011
이 경우 앞에서부터 조회하면서 연속된 1의 개수는 1, 11 로 2개이고 0의 개수는 000으로 하나이다. 따라서 적은 수인 1을 출력한다.
문제 해결을 위한 팁
이 경우 문자열에 0과 1이 아닌 다른 숫자를 붙여주면 쉽게 해결할 수 있다. num_of_zero와 num_of_one이라는 변수를 이용하여 문자열 S를 조회하며 앞과 뒤가 다른 경우 앞이 속해있는 진영의 숫자를 하나 증가시켜주면 해결할 수 있는데 문자열 S의 마지막 원소인 경우 이 방법을 적용하기 어렵기 때문에 마지막에 다른 숫자(예를 들면 2)를 붙여주어 쉽게 이 문제를 해결할 수 있다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
data = input()
data +="2"# 입력받은 문자열 뒤에 임의의 문자를 붙인다
prev =int(data[0])
num_of_zero =0
num_of_one =0
'''
for문을 수행하면서 prev와 다음 수인 num이 서로 다른 경우 prev가 속한 집단의 숫자를
하나 증가시켜준다. 이 결과를 통해 예시 0001100의 경우 num_of_zero는 2가 num_of_one는 1이 된다.
'''
for i inrange(1, len(data)):
num =int(data[i])
if prev ==0and num != prev:
num_of_zero +=1
elif prev ==1and num != prev:
num_of_one +=1
prev = num
print(min(num_of_zero, num_of_one)) # num_of_zero 와 num_of_one중 최소값을 출력한다
