LinkedList ?
- LinkedList는 ArrayList와는 다르게 원하는 위치값으로 O(1)의 접근이 불가능하다.
- LinkedList의 각각의 노드들은 저장할 값과 next를 통하여 다음 노드의 위치를 저장해 둔 방식으로 원하는 값을 찾을 때 O(n)의 시간복잡도가 소요된다.
- 위의 그림에서 13을 찾는다고 할 때,
- 처음 null은 next = 8 을 통해 8을 찾는다. 그 다음 8은 next = 5 를 통해 5를 찾은 뒤 next = 13 을 통해 13을 찾는다.
LinkedList의 삽입과 삭제
- LinkedList의 삽입은 다음 노드의 위치를 저장할 next 값만 변경해주면 되고, ArrayList처럼 삽입할 공간을 만들지 않아도 된다.
- 5와 13 사이에 1을 추가한다고 할 때,
- 5의 원래 next = 13 을 next = 1 로 변경하고, 1의 next = 13 을 한다면 다음 노드의 위치들을 저장할 수 있다.
- 즉, 원소의 삽입에 O(1)의 시간복잡도가 소요된다(단, 삽입할 위치를 모른다면 O(n)의 시간복잡도가 소요된다.).
- LinkedList의 삭제는 다음 노드의 위치를 저장할 next값만 변경해주면 되고, ArrayList처럼 삭제 후의 원소들으 ㅣ위치를 변경할 필요가 없다.
- 8과 1 사이의 5를 삭제한다고 할 때,
- 8의 원래 next = 5를 next = 1 로 변경하면 다음 노드의 위치들을 저장할 수 있다.
- 즉, 원소 삭제 시 O(1)의 시간복잡도가 소요된다(단, 삭제할 위치를 모른다면 O(n)의 시간복잡도가 소요된다.).
예제. LinkedList를 이용한 예제 - 요세푸스 문제
[문제]
요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(<=N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K) - 요세푸스 순열이라고 한다. 예를 들어 (7, 3) - 요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K) - 요세푸스 순열을 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 <= K <= N <= 5,000)[출력]
예제와 같이 요세푸스 순열을 출력한다.
예제 입력 예제 출력 7 3 <3, 6, 2, 7, 5, 1, 4>
- 1 부터 n 까지의 사람이 원을 이루어 앉아 있다. 양의 정수 k가 주어질 때, 순서대로 k번째 사람을 제거한다. n명의 사람이 모두 제거될 때까지 계속 반복해서 제거되는 사람의 번호를 출력하는 것이다.
- 예제 입력 1을 보면 n = 7, k = 3 이다.
n번째 사람 1 2 3 4 5 6 7
사람 번호 1 2 3 4 5 6 7
1) 맨 처음 k = 3 번째 사람을 지워라. 3
n번째 사람 1 2 3 4 5 6 7
사람 번호 1 2 4 5 6 7
2) 현재 위치로부터 3번 오른쪽 사람을 지워라. 6
n번째 사람 1 2 3 4 5 6 7
사람 번호 1 2 4 5 7
3) 현재 위치로부터 3번 오른쪽 사람을 지워라. 2
n번째 사람 1 2 3 4 5 6 7
사람 번호 1 4 5 7
4) 현재 위치로부터 3번 오른쪽 사람을 지워라. 7
n번째 사람 1 2 3 4 5 6 7
사람 번호 1 4 5
5) 현재 위치로부터 3번 오른쪽 사람을 지워라. 5
n번째 사람 1 2 3 4 5 6 7
사람 번호 1 4
6) 현재 위치로부터 3번 오른쪽 사람을 지워라. 1
n번째 사람 1 2 3 4 5 6 7
사람 번호 4
7) 현재 위치로부터 3번 오른쪽 사람을 지워라. 4
n번째 사람 1 2 3 4 5 6 7
사람 번호- 결국 3, 6, 2, 7, 5, 1, 4의 순서대로 사람을 지우게 된다.
- 주의하여야 할 사항
- ArrayList 혹은 LinkdeList는 데이터를 지우면 인덱스의 위치가 재정렬된다.
- 예를 들어 1)에서 3을 지우면
n번째 사람 1 2 3 4 5 6 인덱스 0 1 2 3 4 5 사람 번호 1 2 4 5 6 7- 배열에서는 위와 같은 형식을 띠기 때문이다.
- 컴퓨터 표현식으로 로직을 설명하면
1. idx = k - 1(컴퓨터에서 인덱스는 0부터 시작하기에) 2~4를 반복한다. 2. idx를 남아있는 사람 수 n의 나머지 값으로 설정한다(배열의 크기가 1 줄었으므로) 3. idx번째 사람을 지운다. 4. idx에 k - 1을 더해준다(k가 아닌 k-1을 지우는 이유는 사람을 지웠으므로 뒤에 사람이 앞으로 당겨오기 때문이다. 따라서 오른쪽으로 이동 횟수는 3번이 아닌 2번이다).
해답코드
class Node: # LinkedList에서 사용할 노드를 정의한다.
def __init__(self, data):
self.data = data
self.next = None
class LinkedList: # LinkedList의 처음 부분을 정의한다.
def __init__(self, value):
self.head = Node(value)
def insert(self, value): # LinkedList의 데이터를 삽입한다.
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def get_node(self, index): # LinkedList의 해당 index값을 가져온다.
node = self.head
count = 0
while count < index:
count += 1
node = node.next
return node
def delete_Node(self, index): # LinkedList의 해당 index값을 삭제한다.
if index == 0:
del_node = self.head.data
self.head = self.head.next
return del_node
node = self.get_node(index - 1)
del_node = node.next.data
node.next = node.next.next
return del_node
N, K = map(int, input().split()) # n과 k를 입력받는다.
Link = LinkedList(1) # LinkedList 자료구조에 첫 값을 1로 넣어준다.
for i in range(2, N + 1): # 그 뒤 2~n 까지 수들을 n에 넣어준다.
Link.insert(i)
answer = [] # 정답을 기록하기 위한 answer 변수를 생성한다.
idx = K - 1 # idx = k-1 (초기 위치를 k-1)로 설정한다.
while Link.head is not None: # LinkedList가 비어있지 않다면 무한 반복한다.
idx %= N # idx %= N(남아있는 사람의 수로 나눈 나머지 값)으로 설정한다.
# answer에 LinkedList의 idx번째 노드를 값을 넣고 LinkedList의 idx번째 노드를 삭제한다.
answer.append(Link.delete_Node(idx))
idx += (K - 1) # idx += (k - 1)로 설정한다(오른쪽으로 3번 이동).
N -= 1 # 남아있는 사람의 수 -= 1 이다.
print('<', end = '') # 문제에 맞게 출력한다.
for i in range(len(answer) - 1):
print(answer[i], end = ', ')
print(answer[len(answer) - 1], end = '')
print('>')
데이터 사이언스 입문