해설 보기
정답단순 연결리스트의 특정 노드 탐색은 O(1)이 아니라 순차 접근이 필요한 O(n)입니다.
핵심 개념
연결리스트 종류별 연산의 시간복잡도
연결리스트는 노드가 포인터로 이어진 자료구조라서 배열과 달리 인덱스로 임의 접근을 할 수 없고, 원하는 노드까지 헤드부터 순차적으로 따라가야 하므로 탐색은 O(n)입니다. 삽입과 삭제 자체는 포인터 몇 개만 바꾸면 되므로 O(1)이지만, '어디에' 연산할지 찾는 비용과 '이전 노드'를 확보하는 비용이 시간복잡도를 좌우합니다. 단순 연결리스트는 앞으로만 이동할 수 있어 삭제 시 선행 노드를 찾느라 O(n)이 걸리고, 이중 연결리스트는 prev 포인터가 있어 노드 주소만 알면 O(1)에 삭제할 수 있습니다. 원형 연결리스트에서 헤드가 마지막 노드를 가리키면 마지막 노드의 next가 곧 첫 노드이므로 앞뒤 양쪽 조작을 O(1)에 처리할 수 있습니다.
선지별 해설
①단순 연결리스트는 배열처럼 인덱스로 바로 접근할 수 없고 헤드부터 next 포인터를 따라 하나씩 이동해야 하므로, 특정 노드 탐색의 시간복잡도는 최악의 경우 O(n)입니다. 따라서 이 설명이 정답 선지입니다.
②원형 연결리스트에서 헤드 포인터가 마지막 노드를 가리키면 '마지막 노드->next'가 곧 첫 번째 노드이므로, 첫 노드의 삽입과 삭제를 포인터 재연결만으로 O(1)에 처리할 수 있습니다.
③이중 연결리스트는 각 노드가 prev와 next를 모두 가지므로 삭제할 노드의 포인터만 알면 선행 노드를 따로 탐색할 필요 없이 양쪽을 이어 붙일 수 있어 삭제가 O(1)입니다.
④단순 연결리스트는 뒤로 되돌아갈 수 없어, 삭제할 노드의 위치를 알아도 그 앞 노드의 next를 고쳐야 하므로 선행 노드를 처음부터 찾아야 합니다. 그래서 삭제 비용이 O(n)이 됩니다.
해설 보기
정답세마포어는 두 값만 갖는 변수가 아니라 임의의 정수값을 가질 수 있는 변수입니다.
핵심 개념
임계구역과 상호배제 해결 기법
임계구역(Critical Section)은 여러 프로세스가 공유 자원에 접근하는 코드 영역으로, 동시에 둘 이상이 들어가면 데이터 일관성이 깨집니다. 이를 막기 위한 조건이 상호배제(Mutual Exclusion), 진행(Progress), 한정 대기(Bounded Waiting)입니다. 소프트웨어적 해결책으로는 두 프로세스를 대상으로 flag와 turn 변수를 함께 쓰는 피터슨(Peterson) 알고리즘이 대표적이고, 데커 알고리즘도 같은 계열입니다. 하드웨어·OS 수준 해결책으로는 세마포어와 모니터가 있는데, 세마포어는 P(wait)와 V(signal) 연산으로 조작되는 정수형 변수이며 0과 1만 갖는 이진 세마포어와 여러 개의 자원을 세는 계수 세마포어로 나뉩니다. 모니터는 공유 데이터와 연산을 캡슐화해 한 순간에 한 프로세스만 진입하도록 언어 차원에서 보장하는 상위 수준 기법입니다.