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)의 시간 복잡도를 가지기도 한다. 퀵 소트가 좋다고는 하지만 최악의 경우는 높은 성능을 기대하기도 어렵다. 이를 해결하기 위해서 개선된 방식으로는 피봇을 정하는 인덱스를 처음과 끝으로 고정시키지 않는다는 것이다. 그럼 이..