THIS IS ELLIE

소프트웨어는 어떻게 난수를 생성할까? 사실상 컴퓨터는 난수를 생성할 수 없다. 엄밀히 말하면 pseudorandom numbers를 생성하는 것이다. 난수는 수학적인 방법으로 진행된다. 위는 유사 난수를 위한 공식이다. 유사 난수(pseudorandom number)는 난수를 흉내내기 위해 알고리즘으로 생성되는 값을 가리킨다. 이때 유사 난수를 생성하는 알고리즘을 유사 난수 생성기(pseudorandom number generator, PRNG)로 부른다. 예를 들어 5를 넣는다고 가정한다. 5 * 8 = 40이고 을 11로 나눈 값은 7이다. 여기서 나온 결과 값을 다시 앞으로 보낸다. 그럼 7*8을 곱한 56을 11로 나눈 나머지인 1이 나온다. 위와 같이 결괏값을 앞으로 보내준다. 그러면 8을 11..

스위프트 데이터 구조와 알고리즘 책을 읽으며 알게 된 사실. 흔히 아는 퀵 정렬. 스위프트에서도 정렬 함수에 퀵 정렬이 사용된다. 그만큼 강력한 정렬이고 장점이 많다. 평균 시간복잡도는 O(nlogn)이다. 하지만 피봇 값에 따라 편향되게 분할될 가능성도 있어 최악의 경우 시간복잡도는 O(n^2)이다. 예를 들어 이미 정렬할 데이터가 정렬되어 있거나 역으로 정렬되어 있는 경우 피봇이 한쪽으로 치우쳐 N개의 원소를 피봇 기준으로 나누는 작업을 N번 실행하기 때문에 최악의 경우는 O(n^2)의 시간 복잡도를 가지기도 한다. 퀵 소트가 좋다고는 하지만 최악의 경우는 높은 성능을 기대하기도 어렵다. 이를 해결하기 위해서 개선된 방식으로는 피봇을 정하는 인덱스를 처음과 끝으로 고정시키지 않는다는 것이다. 그럼 이..

Swfit의 Shuffle( ) "Use the shuffle() method to randomly reorder the elements of an array."shuffle()은 배열의 순서를 랜덤화 하는 함수입니다. 시간 복잡도는 O(n)이네요. WWDC2018 Generic을보다가 shuffle()이 어떻게 구현되었는지 언급이 되길래 정리하고자 합니다. 사용된 fisher yates shuffle 알고리즘은 오래된 알고리즘입니다. 위에서 shuffle()은 배열을 랜덤화 할때 사용하는 함수라고 했으니array.shuffle()을 해주고 print를 찍어보면 잘 섞여서 나오는걸 확인할 수 있습니다.위 print문이 어떻게 찍혔는지 과정을 살펴봅시다.먼저 컬렉션의 첫 번째 요소에 대한 인덱스부터 시작합..