리눅스에서 C를 사용한 간단한 게임을 만들고 있는데요, 카드덱을 섞을 일이 있어서 섞는 알고리즘을 지피티쟝이 알려줌
근데 Fisher-Yates algorithm이랑 Knuth Shuffle algorithm 이렇게 두가지가 있더라고요?
제가 썼던건 knuth shuffle인데 지피티한테 효율적으로 바꿔달라 하니까 fisher yates로 바꾸길래 어떤 차이가 있나 싶어서 알아봤습니다.
Fisher-Yates Algorithm 의 역사
Fisher-Yates 알고리즘은 1938년 Ronald A. Fisher와 Frank Yates가 고안한 알고리즘입니다.
이 알고리즘은 원래 통계학에서 무작위로 섞은 샘플을 만들기 위해 개발되었는데, 나중에 컴퓨터 분야에서 배열을 무작위로 섞는데 사용되었다고 한다.
처음 컴퓨터 분야에서 사용되기 시작한건 1964년이다. 초기 버전에는 배열의 각 요소를 무작위로 선택할때 주사위를 이용했지만, 나중엔 난수 생성기를 사용해서 구현되었다고 한다. 지금은 아주 빠르고 효율적으로 구현할수 있다.
사실 이건 굳이 알 필요는 없는데... 제가 궁금함
이름이 너무 귀엽고 찰져서 왜 fisher 지? 사람 이름이 fisher인가? 싶어서 알아봤어요
근데 진짜 사람 이름이었음... 죄송
Fisher-Yates Algorithm 이란?
이 알고리즘은
- 섞을 배열의 마지막 요소부터 시작하여, 배열의 첫 요소까지 반복합니다.
- 현재 위치에서 이전 위치까지의 범위에서 무작위로 하나의 요소를 선택합니다.
- 현재 위치와 선택된 위치의 요소를 교환합니다.
- 이전 위치로 이동하여 반복을 계속합니다.
이런식으로 작동된다.
모든 요소가 균등하게 무작위로 선택되기 때문에, 섞는 효과가 높다.
시간 복잡도는 O(n)이다.
Fisher-Yates Algorithm 과 Knuth Shuffle Algorithm의 차이
Fisher-Yates:
import random
def fisher_yates_shuffle(arr):
n = len(arr)
for i in range(n-1, 0, -1):
j = random.randint(0, i)
arr[i], arr[j] = arr[j], arr[i]
return arr
# 예시
arr = [1, 2, 3, 4, 5]
print(fisher_yates_shuffle(arr))
Knuth Shuffle:
import random
def knuth_shuffle(arr):
n = len(arr)
for i in range(n-1):
j = random.randint(i, n-1)
arr[i], arr[j] = arr[j], arr[i]
return arr
# 예시
arr = [1, 2, 3, 4, 5]
print(knuth_shuffle(arr))
무슨 차이가 있냐면
| Fisher-Yates 알고리즘 | 배열의 뒤에서부터 앞으로 이동하면서 요소를 선택하여 섞음 | O(n) |
| Knuth Shuffle 알고리즘 | 배열의 앞에서부터 뒤로 이동하면서 요소를 선택하여 섞음 | O(n) |
이런 차이가 있다.
Fisher yates는 배열의 뒤에서부터 앞으로 이동하고 knuth shuffle은 앞에서부터 뒤로 이동한다.
그래서 그냥 차이는 앞에서부터 하냐 뒤에서부터 하냐의 차인데 지피티는 계속 내 knuth shuffle 알고리즘을 fisher yates 로 바꾼다. 왜그러는지 모르겠다;;
'언어는 과-학인가요? > Data Structure' 카테고리의 다른 글
| Hash Table (해시 테이블)의 필요성과 문제점, 해결 방법 (0) | 2023.03.28 |
|---|
