[강의정리] [연결리스트] 실전 알고리즘 0x04 정리

바킹독의 실전 알고리즘 0x04 강의 정리.

 

연결리스트는 어떤 문제에 쓰일까?

- 연결 리스트가 쓰이는 문제는 크게 응용해서 낼만한게 없고 원소들을 돌아다니면서 이동하다가 삭제나 삽입이 필요한 문제들

 

 

- 연습문제들

https://jjpearl.tistory.com/52

[백준 - 1406번] 에디터

 

- 손코딩 문제 1

원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법?

 -> 효율적 = 생각한 풀이의 공간복잡도와 시간복잡도를 생각해봐라

답: 시작노드를 따로 저장해뒀다가 동일한 노드가 나올 때 까지 계속 다음 노드로 가면 됨. 

 -> 공간복잡도 O(1), 시간복잡도 O(N)

 

- 손코딩 문제 2

중간에 만나는 두 연결리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법?

답: 두 시작점 각각에 대해 끝까지 진행시켜서 각각의 길이를 구한다.

그 후 다시 두 시작점으로 돌아와 더 긴족을 둘의 차이만큼 앞으로 이동시켜 놓으면

둘을 동시에 한칸씩 전진시켰을 때 만나는 지점을 구할 수 있다.

 -> 공간복잡도 O(1), 시간복잡도 O(A+B)

 

 

https://jjpearl.tistory.com/53?category=1033721 

[백준 - 5397번] 키로거

 

 

https://jjpearl.tistory.com/54?category=1033721 

[백준 - 1158번] 요세푸스 문제