우주의 IT 소행성

비트 마스크 (Bitmask)

- 0 부터 N - 1 까지 정수로 이루어진 집합을 나타낼 때 사용

- 공간을 매우 절약할 수 있음

- 각종 연산을 조금 변형해서 사용해야 함

- 집합 값의 검사, 추가, 제거의 모든 복잡도가 O(1)임

A << B -> 비트를 왼쪽으로 한 칸 씩 미는 작업으로, A * 2^B과 같은 뜻

A >> B -> 비트를 오른쪽으로 한 칸 씩 미는 작업으로, A / 2^B과 같은 뜻

집합의 값을 검사, 추가, 제거 할 수 있음.

비트마스크 S에 X가 있는지 검사 ( AND 연산 )

- S & (1 << X) == 0 이면 없음, 0이 아니면(1<<X)이면 있음

비트마스크 S에 X를 추가 (OR 연산)

- 이미 있는 수를 또 추가할 때는 무시. (1 OR 1 = 1이기 때문)

-  S | (1 << X) 하는 것

비트 마스크 S에 X를 제거

- AND 연산일 경우 지우려는 값만 0으로 대조시키면 무조건 0으로

- S & ~(1 << X)

토글 연산

- 0 < - > 1 SWAP 연산

- S ^ (1 << X)

전체 집합

- (1 << N) - 1

공집합

- 0

비트 연산의 연산자 우선 순위를 잘 생각해야 한다.

- 비트 연산은 사칙연산보다 후순위 연산 순위를 가진다.

def check(index):
    s = 0
    for i in range(index, -1, -1):
        s += ans[i]
        if sign[i][index] == 0:
            if s != 0:
                return False
        elif sign[i][index] < 0:
            if s >= 0:
                return False
        elif sign[i][index] > 0:
            if s <= 0:
                return False
    return True

def go(index):
    if index == n:
        return True
    if sign[index][index] == 0:
        ans[index] = 0
        return check(index) and go(index + 1)

    for i in range(1, 11):
        ans[index] = i * sign[index][index]
        if check(index) and go(index + 1):
            return True
    return False


n = int(input())
s = input()
sign = [[0] * n for _ in range(n)]
ans = [0] * n
cnt = 0
for i in range(n):
    for j in range(i, n):
        if s[cnt] == '0':
            sign[i][j] = 0
        elif s[cnt] == '+':
            sign[i][j] = 1
        else:
            sign[i][j] = -1
        cnt += 1
go(0)
print(' '.join(map(str, ans)))

"""
-10 ~ 10 까지 N개의 정수로 이루어진 수열 A (N <= 10)
S[i][j] = A[i] ~ A[j] 까지의 합,
S[i][j]가 0보다 크면 +, 작으면 -, 같으면 0을 출력
S가 주어졌을 때, 가능한 A를 찾는 문제

각 자리마다 21가지의 수를 구해 넣어주저야 함
O(21^10)은 너무 큰 수로 BRUTE FORCE로는 해결이 어려움


----시간초과를 해결 할 방법 첫번째----
s[i][i] = A[i]의 부호
s[i][i] > 0 1~ 10
        = 0 0
        < 0 -10 ~ -1
로 경우의 수를 10^10로 줄일 수 있다.
하지만 10^10은 100억으로 시간초과.

----두번째----
i번째의 수를 정하면 S[j][i]의 부호를 모두 검사할 수 있다.
"""

• 정보·통신 생성 시스템에서, 문제의 해답을 구하기 위한 추론 제어 방식의 하나. 규칙을 적용하여 얻은 결과가 틀리면 그 규칙을 적용한 다음부터 현재까지의 결과를 무시하고 처음으로 돌아가서 다른 규칙을 선택하여 다시 시도한다.

-표준 국어 대사전에서 발췌-

일반적으로 재귀함수에서 더 이상의 호출이 의미 없을 때, 중간에 재귀함수를 중단시키는 알고리즘을 의미한다.

백준 14889번, 15661번 스타트 링크 문제를 통해 백트래킹에 대해 알아보자.

1 ~ N까지의 번호 중 2개의 팀을 각 N/2명으로 나누어야 한다.

2. 이때 S[I][J] = i번 사람과 j번 사람이 같은 팀일 때 팀에 더해지는 능력치이다.

3. 팀의 능력치 : 팀에 속한 모든 s[i][j]쌍의 합이다.

4. 문제 요구 사항 : 두 팀의 능력치를 구하고 차이의 최소를 구하라

해당 문제를 요구 사항에 맞게 코딩하면

def go(index, first, second):
    if index == n:
        if len(first) != n // 2:
            return -1
        if len(second) != n // 2:
            return -1
        t1 = 0
        t2 = 0
        for i in range(n // 2):
            for j in range(n // 2):
                if i == j:
                    continue
                t1 += s[first[i]][first[j]]
                t2 += s[second[i]][second[j]]
        diff = abs(t1 - t2)
        return diff
    ans = -1

    t1 = go(index + 1, first + [index], second)
    if ans == -1 or (t1 != -1 and ans > t1):
        ans = t1
    t2 = go(index + 1, first, second + [index])
    if ans == -1 or (t2 != -1 and ans > t2):
        ans = t2
    return ans


n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
print(go(0, [], []))

이런 코드가 나오게 된다.

index : 사람을 어떤 팀에 넣을지 (스타트 팀, 링크 팀)

first : 1번 팀, second : 2번 팀

index == n 일 경우 함수 종료

first나 second의 팀 수가 n//2를 넘어가게 되면(딱 절반이어야 하는데 넘어갈 때)  -1 반환

하지만 index == n 일때 

first나 second가 n//2가 아님을 검사하게 되면

결국 index는 n 만큼의 재귀를 실행하게 된다. 

만약 first나 second가 (n이 8일 때) 5를 넘었을 때 바로 종료한다면 더 시간을 단축할수 있을 것이다.

이때를 위해 백트래킹 방법이 사용된다.

재귀 중간에, 특정 상황(의미 없는 재귀가 반복된다고 판단)에서 재귀를 종료시키는 구문을 넣어준다.

def go(index, first, second):
    if index == n:
        if len(first) != n // 2:
            return -1
        if len(second) != n // 2:
            return -1
        t1 = 0
        t2 = 0
        for i in range(n // 2):
            for j in range(n // 2):
                if i == j:
                    continue
                t1 += s[first[i]][first[j]]
                t2 += s[second[i]][second[j]]
        diff = abs(t1 - t2)
        return diff
    ans = -1
    if len(first) > n // 2:
        return -1
    if len(second) > n // 2:
        return -1

    t1 = go(index + 1, first + [index], second)
    if ans == -1 or (t1 != -1 and ans > t1):
        ans = t1
    t2 = go(index + 1, first, second + [index])
    if ans == -1 or (t2 != -1 and ans > t2):
        ans = t2
    return ans


n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
print(go(0, [], []))

따라서 중간에

if len(first) > n // 2:
    return -1
if len(second) > n // 2:
    return -1

를 넘어줌으로써, 시간을 절약시킬 수 있다.

DFS (Depth First Search, 깊이 우선 탐색)

- 그래프에서 깊은 부분을 우선 탐색하는 알고리즘

그래프란?

- 노드와 간선(정점)으로 표현된 자료구조

- 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 그래프 탐색이라고 한다.

- 두 노드가 간선으로 이어져 있으면 '두 노드는 인접(Adjacent) 하다'라고 표현한다.

그래프의 표현 방식

- 그래프를 프로그래밍에서 표현하는 방식은 크게 2가지이다

1. 인접 행렬 방식 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현

표로 표현했을 때

INF = 999999999 # 무한

# 2차원 리스트의 인접 행렬 표현
graph = [
	[0, 3, 5],
    [3, 0, INF],
    [5, INF, 0]
}

print(graph)

파이썬 코드로 표현했을 때

- 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리의 낭비가 심함

- 인접 행렬 방식이 인접 리스트 방식보다 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠름

2. 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현

graph = [[] for _ in range(3)]

graph[0].append((1, 5))
graph[0].append((2, 3))

graph[1].append((0, 5))

graph[2].append((0, 3))

print(graph)

- 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용함

- 인접 리스트 방식은 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림 (데이터를 하나씩 확인)

# DFS
def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
dfs(graph, 1, visited)

BFS (Breadth First Search, 너비 우선 탐색)

- 가까운 노드부터 탐색하는 알고리즘

- DFS와 반대(가장 가까운 노드부터 / 가장 먼 노드부터)

- 선입선출의 큐 자료구조를 사용

- 재귀로 DFS를 구현하면 수행 시간이 느려질 수 있음

- 스택을 사용하여 DFS구현을 빠르게 동작시킬 수 있음

- 일반적인 경우 DFS보다 BFS의 동작이 빠름

# BFS
from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    while queue:
    	v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
bfs(graph, 1, visited)