728x90
문제 1
원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 풀이를 효율적으로 구하는 방법은?
정답
동일한 노드가 나올때까지 계속 다음 노드로 가면 된다. 공간 복잡도 O(1), 시간 복잡도 O(N).
문제 2
중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때, 만나는 지점을 구하는 방법은?
정답
일단 두 시작점 각각에 대하여 끝까지 진행시켜서 각각의 길이를 구한다. 그 후 다시 시작점으로 돌아와서 더 긴 쪽을 둘의 차이만큼 앞으로 먼저 이동시켜 놓고, 두 시작점이 만날 때까지 두 시작점을 동시에 한 칸씩 전진시키면 된다.
공간 복잡도 O(1), 시간 복잡도 O(A+B).
문제 3
주어진 연결 리스트 안에 사이클이 있는지 판단하라.
정답
Floyd's cycle-finding algorithm 을 사용하면 판단이 가능하다.
snutiise.github.io/Floyd's-Cycle-Detection-Algorithm/
한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시키면 사이클이 있는 경우 반드시 만나게 된다.
반대로 만약 사이클이 없으면 두 커서가 만나지 못하고 연결 리스트의 끝에 도달하지 못하게 된다.
이 방식으로 사용하면 거치는 모든 노드를 저장할 필요 없이 공간 복잡도 O(1)에 사이클의 존재 여부를 확인할 수 있다.
공간 복잡도 O(1), 시간복잡도 O(N)
728x90
'Algorithm > 바킹독의 알고리즘 강의' 카테고리의 다른 글
큐 (0) | 2021.04.12 |
---|---|
스택 (0) | 2021.04.12 |
연결 리스트 (0) | 2021.04.10 |
배열에 0 채우기 좋은 방법 (0) | 2021.04.09 |
배열의 정의와 성질 (0) | 2021.04.08 |
댓글