[프로그래밍 대회에서 배우는 알고리즘 문제해결전략]에서 선형자료구조 단원 내용을 요약, 정리한 게시글입니다.

도입

배열과 같이 일렬로 늘어선 자료들을 저장하기 위한 자료 구조: 동적 배열과 연결 리스트

동적 배열

배열의 큰 문제 중 하나: 처음 배열을 선언할 때 배열의 크기를 지정, 그 이상의 자료를 집어넣을 수 없음.
⇒ 동적 배열: 자료의 개수가 변함에 따라 크기가 변경되는 동적 배열
js 에서는 그냥 배열(Array type)도 동적 배열임.

(재배열 관련 수행시간 어쩌고 이론)

연결 리스트

배열 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입, 임의의 위치에서 원소를 삭제하는 건 시간이 오래 걸리는 작업.

⇒ 연결 리스트: 특정 위치에서의 삽입과 삭제를 O(1)에 할 수 있게 함

js 연결 리스트 구현

특징

• head와 tail에 대한 포인터를 가짐.
• i번째 노드 탐색 수행 시간: O(n), 리스트의 길이에 선형 비례함
  이유: 여기저기 흩어져 있기 때문.
• 삽입/삭제 수행 시간: 0(1)
• 다른 리스트의 일부를 삽입하는 수행 시간: O(1)
• 양방향 연결 리스트의 경우, 삭제했던 원소를 돌려놓기 쉬움.
  ⇒ 이런 특징은 11장 조합 탐색에서 유용함.(되돌리기)
  ++ 커누스의 dancing links 기법 참고

조세푸스 문제 → 원형 연결 리스트 문제(pg. 620)

1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 7V-1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하느니 차라리 자살하자고 결의했고，포위당한7V명의 사람들이 모두 원형 으로 둘러선 뒤 순서대로 자살하기로 했습니다. 한 사람이 자살하면, 다음에는 그 사람으로부터 시계 방향으로《번째 살아 있는 사람이 자살하는 것입니다. 조세푸스의 책에 따르면 조세푸스와 다른 병사 하나만이 살아남았을 때 이들은 마음을 바꿔 로마에 항복해서 살아남았다고 합니다. 마지막 두 명 중 하나가 되 기 위해서는 조세푸스는 첫 번째 병사로부터 몇 자리 떨어진 곳에 있어야 했을 까요?

• 풀이 방법 1

  포인터를 앞으로 K-1번 옮기기 → $O(nk)$

• 풀이 방법 2

  포인터를 처음부터 K mod N만큼 옮기기 → $O(n^2)$