코드는 나만의 비밀 다이어리가 아니야

리눅스에서 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 이란?

이 알고리즘은

1. 섞을 배열의 마지막 요소부터 시작하여, 배열의 첫 요소까지 반복합니다.
2. 현재 위치에서 이전 위치까지의 범위에서 무작위로 하나의 요소를 선택합니다.
3. 현재 위치와 선택된 위치의 요소를 교환합니다.
4. 이전 위치로 이동하여 반복을 계속합니다.
   
   

이런식으로 작동된다.

모든 요소가 균등하게 무작위로 선택되기 때문에, 섞는 효과가 높다. 

시간 복잡도는 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는 배열의 뒤에서부터 앞으로 이동하고 knuth shuffle은 앞에서부터 뒤로 이동한다. 

그래서 그냥 차이는 앞에서부터 하냐 뒤에서부터 하냐의 차인데 지피티는 계속 내 knuth shuffle 알고리즘을 fisher yates 로 바꾼다. 왜그러는지 모르겠다;;

Direct Address Table 의 한계 

direct address table은 키(key)와 값(value)의 쌍(pair)을 저장하는 자료구조로, 키를 인덱스(index)로 사용하여 값을 저장하고 검색할 수 있다. 

이 때, 인덱스의 크기가 충분히 크면(예를 들어, 0부터 999까지의 인덱스가 있을 때, 1000개), O(1)의 검색 시간을 제공한다.

그러나 인덱스의 크기가 매우 작거나 값이 희소하게 분포할 경우, 메모리 공간의 낭비가 발생하게 된다. 

이러한 direct address table의 한계를 극복하기 위해, 해싱 기법을 사용하는 해시 테이블(Hash Table)이 개발되었다.

해시 테이블은 키를 해시 함수(hash function)로 변환하여 인덱스를 생성하므로, 인덱스의 크기와 값의 분포에 구애받지 않는다.

또한, 해시 함수를 이용하여 데이터의 위치를 찾으므로, O(1)의 검색 시간을 제공한다.

하지만 해시 테이블에도 몇가지 문제점이 존재한다. 

Hash Table 의 문제점

1.  충돌 (Collision)

해시 함수에 의해 생성된 인덱스가 다른 데이터와 이미 할당된 경우 충돌이 발생한다.

충돌이 발생하면, 데이터를 추가적으로 처리하여 충돌을 해결해야 한다. 

2. 해시 함수 성능

해시 함수의 성능이 좋지 않으면 데이터 검색 시간이 길어지게 된다. 

해시 함수는 인덱스를 생성하는데 사용되므로 충돌을 최소화하면서 빠른 속도를 제공하는 함수를 선택해야 한다. 

이러한 문제점을 극복하기 위해 충돌 해결(Collision Resolution)방법과 좋은 Hash Function을 선택하는것이 중요하다.

이러한 문제점들을 극복하기 위해, 충돌 해결(Collision Resolution) 방법과 좋은 해시 함수(Hash Function)를 선택하는 것이 중요하다.

충돌 해결 방법으로는 Open Addressing, Chaining 등이 있으며, 좋은 해시 함수 선택을 위해서는 해시 함수의 충돌 가능성과 보안성을 고려해야 한다.

충돌 해결 방법

충돌은 데이터를 검색하는 데 시간이 걸리며, 해시 함수 성능을 저하시킨다.

따라서 충돌을 최소화하는 해시 함수를 선택해야 하며, 충돌이 발생하였을 때는 이를 해결하는 방법을 선택해야 한다.

1. Open Addressing

Open Addressing은 충돌된 데이터를 다른 해시 테이블 위치에 저장하는 기법이다.

충돌이 발생하면, 해당 위치 이후의 다른 위치를 검색하여 데이터를 저장한다.

이러한 방법은 충돌 해결 방법 중에서도 가장 간단한 방법 중 하나이다.

하지만 충돌이 발생할 경우 해시 함수의 성능이 저하되므로, 충돌이 적은 경우에만 사용된다.

2. Chaining

Chaining은 충돌된 데이터를 같은 위치의 연결 리스트(Linked List)에 저장하는 기법이다.

충돌이 발생하고 해당 위치에 이미 데이터가 저장되어 있으면 연결 리스트에 데이터를 추가한다.

이러한 방법은 해시 함수의 성능에 영향을 미치지 않으며, 충돌이 많은 경우에도 사용할 수 있다.

좋은 해시 함수 선택 방법

1. 좋은 해시 함수를 선택하기 위해서는 해시 함수의 충돌 가능성과 보안성을 고려해야 한다.
2. 충돌 가능성이 높으면 검색 시간이 길어지므로, 충돌 가능성이 적은 함수를 선택해야 한다.
3. 보안성이 중요한 경우에는 보안 해시 함수 또는 암호학적 해시 함수를 선택해야 한다.