데이터를 저장하고 정보를 검색하는건 꽤나 중요한 일이다.
오죽하면 대규모의 데이터 저장 센터같은걸 건설하고 그러겠는가?
하지만 사람이 셀 수 있는 정도를 넘어선, 무지막지한 데이터의 산에서
내가 원하는 정보를 얻는것은 쉽지 않을 것 같다.
특히나 요즘 백준 문제를 풀면서 느낀거는
코드 한줄 두줄 바꾼거가지고 시간초과가 나던게 풀이시간 1/n토막나서 바로 풀리는 경우도 많다.
이처럼 수많은 데이터 중에서 원하는 정보를 빨리 얻기 위해서
똑똑한사람들은 자료구조를 변형하는것으로 효율을 극한으로 올렸다.
b-tree
장점
- 미친듯이 빠르다(O(logn))
- 균등한 검색 속도
단점
- 데이터 삽입/삭제 시 연산이 엄청나게 복잡함
- 낭비하는 메모리가 많음(1/2일때 분할,2/3일때분할...)
- 순차탐색할때 중위순회가 매우 비효율적임 -> b+트리 사용
trie
장점
- 문자열 찾는속도가 엄청 빠름
- 문자열 탐색 추가 모두 O(m)
단점
- 메모리를 장난아니게 먹는다(포인터 값도 전부 지정해야됨)
위상정렬
이번주에 위상정렬 백준 풀이가 4개 나왔는데
이놈들 풀다가 머리털 다 빠질뻔했다.
처음 푸는 플레티넘 문제였는데 어찌어찌 풀어서 다행이긴하다.
문제풀이 잘하시는분들은 '한창 좋아할때지' 하시겠지만
진짜 좋긴하다.
위상정렬의 알고리즘 자체는 쉬운 편이다.
- 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음.
- 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제
- 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다.
간단하다. 그저 그래프를 그린 후, 진입 차수 리스트와 인접리스트를 만든 후, 위의 알고리즘을 그대로 따라가면 된다.
이대로 끝내기는 양이 너무 적으니 백준 문제 풀이 리뷰를 해보겠다.
백준 1432 그래프 수정 - 위상정렬
arr = [[[0] for _ in range(N)] for _ in range(N)]
edge = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
past = [False for _ in range(N+1)]
seq = deque()
list를 만드는 코드이다.
- arr은 입력을 받아옴
- edge는 받은 입력으로 인접 리스트를 만듬
- visited로 진입차수를 기록함
- past로 진행방향이 역행하지 않도록 채크함.
rutebreaker = True
while past.count(False) != 1:
for i in range(N,0,-1):
if visited[i] == 0 and not past[i]:
seq.append(i)
past[i] = True
for j in range(len(edge[i])):
visited[edge[i][j]] -= 1
break
if past.count(True) == visited.count(0)-1 and past.count(True) != N:
rutebreaker = False
break이후 while구문을 돌리는 코드이다.
- rutebreaker로 탈출 조건을 만듬
- for 구문 - 만약 진입차수가 0이고 한번도 안가본 노드이면 -> 노드를 seq에 저장, past = True, 이 노드가 진출하는 노드들의 진입차수를 -=1(위상정렬 과정 2번)
- if구문 - 만약에 사이클이 만들어져서 순환이 발생하면 -> break로 구문 탈출
이와 같이 위상정렬 자체는 매우 간단하다.
그냥 정의 그대로 따라가는게 별로 어렵지도 않기 때문이다.
하지만 이 문제에서 가장 어려웠던 점은
'인접리스트를 거꾸로 해야 된다'라는 점이다.
여러 조건을 가진 데이터를 정렬할때, 우선순위가 높은 순서대로 정렬하게 되면 데이터가 재대로 정렬이 안된다고 한다.
그래서 하위 조건을 먼저 정렬 한 후, 높은 우선순위로 정렬을 해 나가면 된다고 한다.
이래서 백준 문제 풀때 정 안되면 풀이 보라고 하는거 같다.
