한학기 알고리즘 정리

두서없이, 다시 블로그 시작할 겸

With

• 수업 Assignment
• 스터디 BaekJoon

모든 걸 정리하는 것이 아니라, 최근 유용했던 것을 정리해보려 한다.

 

Bitwise 연산 활용

알고리즘 문제를 풀다 적절한 풀이 방법이 떠올라도, 데이터 구조 구현에서 막혀 방황했었다. 그러다 만난 좋은 친구였다.

첫 만남

학교 과제로 TSP를 풀다가 이미 방문한 노드에 대해서 check를 할 필요가 있었다.

하지만, recursive한 방법으로 시작 node부터 차례로 살펴보는 알고리즘 특성 때문에, 그리고 shallow copy라는 파이썬 친구의 특징 때문에 무언가 최적화된 방법을 떠올리기 힘들었다.

그러다가 노트의 수 만큼 2진수 bits로 표현하고 값을 전달하는 방식으로 해보았는데, (인터넷을 참고하다가 만난 좋은 방식) 이 친구 참 활용될 여지가 많은 친구였다.

컴퓨터 구조를 배워서 그런지 전산수학을 배워서 그런지 bit 연산 친구는 정말 매력적이었다.

""" TSP 문제에서 활용하기 """

visited = 0 

# 전체 노드 방문 기준
visit_all = (1 << N) - 1

# 3번 노드 방문 시
visited |= (1 << 3)

전체 코드는 여기서

또 만남

백준 문제 중 3096번 영화제 문제를 풀다가 또 만나게 되었다.

문제를 설명하기에는 너무 길고, 두 도시와 강 건너 두 도시가 상호 모두 연결되어 있으면, 네 도시를 한 쌍의 조합으로 생각하는 문제였는데,

각 도시에 연결된 강 건너 도시들을 bit로 표현하고, and 연산을 통해 공통으로 연결되 강 건너 도시들의 수를 구해 이를 조합식으로 모든 쌍을 구하는 방식인데, 아주 예쁜 방법이었다.

전체 코드는 여기서

 

Deep copy

mutable한 객체 list 친구라서 당연히 기본적인 대입 및 참조에 있어서 shallow copy가 당연하지만 가끔 기본 함수로 다차원 함수를 만들 때 Deep copy를 유용하게 사용한다.

학교 과제로 나온 3-SAT 문제를 풀면서, 각 변수가 가지는 값에 대한 조합 경우의 수 변수 check를 만들고 싶었다. 각 변수는 True or False를 가질 수 있기에 모든 경우의 수는 2^n이 된다.

즉, 이를 표현하는 다차원 변수는, 만약 변수가 3개라면, check[0][0][0]부터 check[1][1][1]까지 총 3차원이지만 8개의 값을 가지는 변수로 만들고자 했다.

checked = [-1, -1]

# 방법 1 - 이렇게 만들면 당연히 안되고,
for _ in range(N - 1):    
    checked = [checked, checked]
    
# 방법 2 - 이렇게 만들면 된다.
checked = [-1, -1]
for _ in range(N - 1):
    temp = deepcopy(checked)
    checked = [temp, checked]

원래 두번째 방법으로 했을 때, 3차원 이상부터는 값 하나만 바꾸면 다 바뀌었는데, 다시 테스트 해보니 잘 동작하네...

아무튼 실제 코드는 두번째 방법도 안되길래 아래처럼 했다~

from itertools import product

checked = {}
for i in product((-1, 1), repeat=N):
	checked[i] = 0

 

이어서 작성할 예정