[Algorithm] 요세푸스 문제 - 1, 2

백준 1179번 문제 - 마지막 요세푸스

https://www.acmicpc.net/problem/1179

- N명의 사람들은 원탁에 둘러 앉아서 시계 방향으로 1번부터 N번까지 번호 부여 받음

- N보다 작거나 같은 K를 정하고, 1번부터 순서대로 K번째 사람 제외시킴

- (N - 1)명이 제외될 때까지 시계 방향으로 K번째 사람을 제외시킴

- 임의의 두 자연수 N과 K (<= N)가 주어질 때, 최후까지 살아 남을 사람의 번호를 구하시오

---

요세푸스 문제 해결법

1. Queue를 이용하는 방법 (속도 느림)

# n = 6, k = 2

class Solution:
	def findTheWinner(self, n: int, k: int) -> int:
    q = [i for i in range(1, n + 1)]
    while len(q) > 1: # q의 길이가 1보다 크면 1이 될 때까지 반복
    	for j in range(1, k + 1):
        	friend = q.pop(0)
            if j != k:	# j가 k번째가 아니라면
            	q.append(friend) # 요소를 다시 Queue의 맨 뒤에 추가
    return q[0]	# q의 길이가 1이 되면 q[0] return

---

2. Circular Linked List를 이용하는 방법

# N = 6, K = 2

class Solution:
	def findTheWinner(self, n: int, k: int) -> int:
    q = [i for i in range(1, n + 1)]
    j = 0
    while len(q) > 1:
    	j = (j + k - 1) % len(d)
        """
        k가 2 니까, 1 2 3 에서
        1 -> 2를 가는 것이므로 k - 1을 하는 것임
        즉, 1을 더하는 것과 같음
        만약 k가 3이면 j에 2를 더할 시 3이 됨
        
        len(d)를 해줘야 범위를 벗어나지 않음
        k가 3이면 3으로 갔다가, 다시 6으로 갔을 때, % 연산을 하면
        0으로 돌아오니 서큘러 리스트라고 볼 수 있음
        """
        q.pop(j) # 제거하는 기능
    return q[0]

---

3. Recurrence Relation(점화식)을 이용하는 방법 (자료구조 안 써서 제일 빠름)

- f(n, k): n과 k가 주어질 때 생존자의 번호

• k번째 사람을 제외하면 n - 1명이 남음
• 다음 게임의 시작 위치는 (k % n) + 1
• f(n - 1, k): 남은 n - 1명이 k번째 사람을 제거할 때 생존자의 번호

점화식: f(1, k) = 1 # 1만 있으면 loop를 몇번 돌든 1이 제거 됨
		f(n, k) = (f(n - 1, k) + k - 1) % n + 1
        """
        f(n - 1, k)의 위치에 있는 사람을 파악한 이후에
        그 다음 위치가 k - 1을 해주면 됨 (서큘러 리스트)
        그 다음 % n 을 하고 (코드상으로 len(q)) +1을 해줘야 f(n, k)에서의 생존자가 나옴
        """

# 점화식을 이용한 재귀 호출:

def findTheWinner(self, n: int, k: int) -> int:
    if n == 1:
    	return 1
    return ((self.findTheWinner(n - 1, k) + k - 1) % n) + 1

# 동적계획법 (반복문 이용)의 적용: 재귀에서 반복으로
# 동적계획법 (D.P): 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

def findTheWinner(self, n: int, k: int) -> int:
    s = 1
    for n in range(1, n + 1):
    	s = ((s + k - 1) % n) + 1
    return s

---

출처

1. 주니온TV 아무거나연구소 - 요세푸스 문제: 1편 https://www.youtube.com/watch?v=rxgBHPy-GAk

2. 주니온TV 아무거나연구소 - 요세푸스 문제: 2편 https://www.youtube.com/watch?v=MHarxFDYBw8&t=9s