💎 개요
코딩테스트 문제를 풀면서 여러번 나온 유형이기도 하면서도 풀지 못했던 문제가 많았다. 파이썬을 이용하며 코테를 풀이하기 시작하면서 붙는 곳도 있었지만 떨어지기도 하는 등 쉬운 문제임에도 풀지 못할 때 체크해보면 유독 유니온파인드, 그래프 탐색 이런 문제들이 많았던 것 같다.
따라서 저번에 올렸던 게시글에 이어서 기억해야할 점들과 유용하게 쓸 수 있는 라이브러리를 좀 더 정리하고자 한다.
💎 정리하기
🍫 순열과 조합
permutations
순열의 경우를 생각해보자. 순열은 중복이 허용되지 않으며, 순서에 따라서 나열할는 경우의 수를 말한다.
itertools를 사용하면 permutations를 불러와 사용할 수 있다!
from itertools import permutations
for i in permutations([1,2,3,4], 2):
print(i, end=" ")
#### (1, 2) (1, 3) ...따라서 위와 같이 사용할 수 있으며 모든 경우의 수를 찾는데에 유용하게 사용할 수 있다.
combinations
조합은 위의 순열의 경우에서 순서를 고려하지 않는 경우이다. 순열과 달리 순서를 고려하지 않고 이미 뽑힌 값은 생각하지 않고 경우의 수를 세준다.
마찬가지로 itertools를 사용하여 combinations를 불러와 사용한다.
from itertools import combinations
for i in combinations([1,2,3,4], 2):
print(i, end=" ")product
중복 순열은 앞선 순열에서 중복을 허용해주는 것이다. 순서에 따라 경우가 달라지면서 중복을 허용하기 때문에 만약 3개의 값을 뽑아야하는 [1,2,3] 리스트가 있다면 중복 순열의 경우 3 * 3 * 3으로 27개의 경우의 수가 올 것 이다.
product는 itertools로 사용해준다.
from itertools import product
for i in product([1,2,3],'ab'):
print(i, end=" ")
for i in product(range(3), range(3), range(3)):
print(i, end=" ")
for i in product([1,2,3], repeat=2):
print(i, end=" ")위와 같은 방식으로 사용해주면서 repeat 매개변수를 통하여 반복을 통해 경우의 수를 계산할 수 있다.
combinations_with_replacement
중복 조합은 순서를 고려하지 않는 순열이면서 중복이 가능하다. 앞서 설명한 조합의 경우의 수에서 중복을 허용한 값들의 경우의 수가 늘어난다고 생각하면 된다.
from itertools import combinations_with_replacement
for c in combinations_with_replacement([1,2,3,4], 2):
print(c, end=" ")
# (1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)🍫 Union Find
흔히 서로소 집합이라고도 불리우면서 그래프 문제에 적용하는 알고리즘이다. 기억해야할 점은 노드들의 루트 노드를 비교할 때나, 두 트리를 합쳐야할 때 사용할 수 있다.
find는 서로 다른 노드가 있을 때 이 노드들의 루트 노드가 과연 서로 같아 연결되어 있을지를 생각할 때 기억하면 되는 알고리즘이다. 따라서 재귀를 반복하면서 노드의 루트들을 계속 거슬러 올라가면서 탐색을 진행한다.
union의 경우에는 두 트리를 합칠 때 트리의 루트가 더 작은 쪽으로 합치는 것이다. 따라서 앞선 find연산을 통하여 루트 노드를 찾았다면 그 루트 노드가 더 작은 쪽으로 합쳐준다.
알고리즘 구현은 다음과 같다!!
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또한 이를 이용한다면 사이클 여부를 확인할 수 있다. 노드들의 부모 노드를 자신으로 초기화한 후 find연산을 진행하면서 루트 노드가 같지 않을 때 합집합을 수행시킨다. 이 때 만약 같을 경우는 사이클이 발생하여 합집합을 수행할 수 없다.
# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기
for i in range(1, v + 1):
parent[i] = i
cycle = False # 사이클 발생 여부
for i in range(e):
a, b = map(int, input().split())
# 사이클이 발생한 경우 종료
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
# 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
else:
union_parent(parent, a, b)
💎 느낀 점
코테를 풀면서 막혔던 문제는 내가 제대로 이해하지 못하고 있는 유형인 경우가 많았다. 단순한 구현이나 그리디, DP는 아이디어의 문제이기 때문에 열심히 많이 풀면서 익혀야하지만 유형에 대한 이해가 부족할 때는 풀기 빡세다는 느낌을 받았다.
특히 위에 정리한 내용은 내가 이해를 제대로 하지 못하였기 때문에 문제에서 언제 적용해야할지 감이 안왔었기 때문에 중복순열이나 중복조합, 그리고 유니온파인드는 꼭 기억하도록 하자!!
앞으로 남은 코테들을 잘 볼 수 있도록 노력하자!!
화팅~
