우주의 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

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

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

https://www.acmicpc.net/problem/10819

"""
1. 수를 변경할 수는 없음
2. 주어진 수의 순서를 변경해 최대 차이를 만들기
방법의 수 : N!, 최대 8, 40320 가지 수

"""
def next_permutation(a):
    i = len(a) - 1
    while i > 0 and a[i - 1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a) - 1
    while a[j] <= a[i - 1]:
        j -= 1

    a[i - 1], a[j] = a[j], a[i - 1]
    j = len(a) - 1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True

def calc(a):
    ans = 0
    for i in range(1, len(a)):
        ans += abs(a[i] - a[i - 1])
    return ans
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
while True:
    temp = calc(a)
    ans = max(ans, temp)
    if not next_permutation(a):
        break
print(ans)

재귀를 이용한 방법

from itertools import permutations
n = int(input())
data = list(map(int, input().split()))
ans = 0

for a in permutations(data, n):
    tmp = 0
    for i in range(1, len(a)):
        tmp += abs(a[i] - a[i - 1])
    ans = max(tmp, ans)
print(ans)

itertools의 permutations를 이용한 방법

STL을 사용할 수 있다면 사용하는게 가장 빠른 시간을 얻을 수 있는 것 같다.

다이나믹 프로그래밍, 메모이제이션을 사용하여 풀어야 하는 문제이다.

2xN 직사각형을 1x2, 2x1, 2x2 타일로 채우는 경우의 수를 구를 2X(최대 1000)까지 구한다.

즉 반복되는 작업을 한다 -> 수열이 형성된다 라는 점을 기억해야한다.

1*2 -> A

2*1 -> B

2*2 -> C

라고 생각해보자

1) N이 1일 때

- B 한가지만 들어갈 수 있다.

- F(1) = 1

2) N이 2일 때

- AA, BB, C

- F(2) = 3

3) N이 3일 때

- AAB, BAA, CB, BC, BBB

- F(3) = 5

4) N이 4일 때

- AAAA, BBBB, AABB, BBAA, BAAB, AAA, CAA, BBC, CBB, BCB, CC 

- F(4) = 11

이 떄, N이 4 이상일 경우, F(N) = F(N - 1) + (F(N - 2) * 2)

의 일반항을 도출할 수 있고 이를 메모이제이션하여 출력해주면 된다.

문제의 반복성과 규칙성을 찾아내 일반항을 도출하는 것

-> 다이나믹 프로그래밍으로 해결할 수 있다.

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    visited[x][y] = True
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

    for i in range(2):
        nx = dx[i] + x
        ny = dy[i] + y

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        if not visited[nx][ny]:
            queue.append((nx, ny))
            visited[nx][ny] = True

print("Hing")

https://universe-lee.tistory.com/34

점프왕 쩰리 (small)의 다음편 large이다. 주어진 맵의 크기가 2에서 64로 올라가는데,

이를 메모리나 시간 초과 없이 푸는게 관건이다.

따라서 bfs시에 이미 갔던 길을 계속해서 가게 된다면 결국 도착 하기 전에 시간초과나 메모리 낭비가 생길것이니

이미 갔던 길을 표시하여, 아 여기는 안 갈래! 하면 되는것이다.

visited 라는 리스트를 만들고, bfs시마다 현재 좌표에 일종의 flag를 꽂는다 (방문, 미방문)

나중에 queue에 새로운 위치를 넣을 때 이미 방문한 위치라면 (visited == True) 재 방문하지 않는다.,

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    visited[x][y] = True
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

    for i in range(2):
        nx = dx[i] + x
        ny = dy[i] + y

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        if not visited[nx][ny]:
            queue.append((nx, ny))
            visited[nx][ny] = True

print("Hing")