백트래킹 문제를 연습하다 백준 문제 1987문제를 시간복잡도를 만족시키지 못하여 골머리를 썩던 중 문제점을 하나씩 찾기 시작했다. 집합 관계(포함 관계)의 문자열을 처리하기 위해 컴퓨터는 사실 10진수로 다시 변환하여 저장한다는 것을 깨닫고 문자열 대신 숫자로 표현하는 방법을 찾기로 했다.
그러다 찾은게 비트마스킹이라는 방법인데, 집합관계를 비트단위로 표현한 값들로 처리할 수 있게 도와주는 방법이다. (참고 : https://mygumi.tistory.com/361)
간략히 설명하면 0부터 5까지 다음 집합 A = {1,2,5}에 속한 숫자만 골라내기 위해 1,2,5를 비트단위로 변환 후 0부터 5까지의 비트 단위과 1,2,5 비트단위와의 교집합을 통해 존재하는지 안하는지 확인할 수 있는 방법이다.
위의 예를 들면
# 1,2,5 를 비트단위로 표현하자면 0부터 시작하는 파이썬은 100110이 되어야한다.
a = [1,2,5]
bit_a = 0
for value in a:
tmp += 1 << x
print(x)
# 38
print(bin(x))
# '0b100110'a에 있는 원소의 합을 bin으로 처리하게 되면 다음과 같이 예상대로 100110이 나오게 된다. 따라서 0부터 5는 000001, 000010, 000100, ... , 100000이 될 것이고 각자 100110과의 교집합을 통해 없으면 0 있으면 1로 표현할 수 있도록 포함관계를 나타내면 가능하다는 뜻이다.
for i in range(6):
if tmp & 1 <<i :
print(i)
# 1
# 2
# 5그럼 이제 원래의 문제의 코드로 넘어가서 풀어보도록 하자, 본래 시간복잡도에서 걸린 코드는 다음과 같다.
r, c = map(int, input().split())
pan = [input().strip() for _ in range(r)]
answer = 0
dx, dy = [1,-1,0,0], [0,0,1,-1]
def find(now, cnt, status):
global answer, dx, dy
x,y = now
if pan[x][y] in status :
answer = max(cnt, answer)
return
status += pan[x][y]
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= int(r) or ny < 0 or ny >= int(c):
continue
cnt += 1
find([nx,ny], cnt, status)
cnt -= 1
find([0,0], 0, "")
print(answer)비트마스킹을 할 수 있는 부분이 보이는가?
if pan[x][y] in status :
answer = max(cnt, answer)
return
#...
if nx < 0 or nx >= int(r) or ny < 0 or ny >= int(c):이 두 부분이 문자열로 구성되어있는 것을 비교연산자를 사용하기 때문에 병목이 생기는 구간일 수 있다. 따라서 우린 이걸 비트마스킹으로 변환해서 풀어보고자 하면 다음과 같은 코드로 작성될 수 있을 것 같다.
r, c = map(int, input().split())
pan = [input().strip() for _ in range(r)]
answer = 0
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
def find(x, y, cnt, bitmask):
global answer
answer = max(cnt, answer)
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
idx = ord(pan[nx][ny]) - ord('A')
if not (bitmask & (1 << idx)):
find(nx, ny, cnt + 1, bitmask | (1 << idx))
initial_bitmask = 1 << (ord(pan[0][0]) - ord('A'))
find(0, 0, 1, initial_bitmask)
print(answer)실제로 시간 계산을 해봐도 0.00048 sec > 0.00040 sec 개선이 되었다 (물론 하나의 백준 예제 case에 대해서만 측정). ChatGPT에게 물어봐도 int()와 ord()의 변환 과정 에서의 시간 복잡도도 차이가 많이 큰걸로 보인다. 신이 말하기로는 다음과 같은 차이가 있다고 한다.
[!int()와 ord()의 차이]
int()와ord()함수의 시간 복잡도는 다음과 같습니다.
int()함수:
int(x)함수는 문자열x를 정수로 변환합니다. 여기서 시간 복잡도는 문자열의 길이에 따라 달라집니다. 일반적으로 문자열의 길이가 n일 때, 이 함수의 시간 복잡도는 O(n)입니다.- 이는 각 문자에 대해 10진수 값을 계산하고 이를 합산하는 과정이 필요하기 때문입니다. 문자열의 각 문자를 순회하면서 해당 문자의 10진수 값을 계산해야 하므로, 문자열의 길이에 비례하는 시간이 소요됩니다.
ord()함수:
ord(c)함수는 단일 문자c의 유니코드 값을 반환합니다. 이 함수는 항상 단일 문자에 대해서만 작동하므로 시간 복잡도는 상수 시간, 즉 O(1)입니다.- 단일 문자의 유니코드 값을 반환하는 작업은 매우 단순하여, 입력 길이에 관계없이 일정한 시간이 소요됩니다.
따라서,
int()함수는 변환할 문자열의 길이에 따라 시간 복잡도가 O(n)인 반면,ord()함수는 상수 시간 O(1)을 가집니다.
'알고리즘' 카테고리의 다른 글
| 백준 14889 스타트와 링크 (Python / 파이썬) (0) | 2023.07.18 |
|---|---|
| 백준 1325 효율적인 해킹 (Python / 파이썬) (0) | 2023.07.16 |
| 백준 1926 그림 (Python / 파이썬) (0) | 2023.07.15 |
| 백준 1065 한수 (Python / 파이썬) (0) | 2023.07.13 |
| 백준 11052 카드 구매하기 (Python / 파이썬) (1) | 2023.06.09 |
