알고리즘 검색 결과

해당 글 4건

유사난수 생성기(Pseudorandom number generator, PRNG)

난수유사 난수 생성기에 대해 알아보기에 앞서 난수가 무엇인지에 대해 간단하게 설명한다. 일반적으로 난수(Random Number)란 일정한 패턴이나 순서가 없으며 누구도 다음에 등장할 값을 예측할 수 없는 숫자를 의미한다. 난수는 아래와 같은 특징을 만족해야만 한다.무작위성난수는 패턴이나 순서가 없고 다음 숫자를 예측할 수 없어야 한다.독립성각 난수는 다른 난수들과 독립적이어야 한다.하나의 난수가 다른 난수에 영향을 주면 안된다.난수는 수학, 통계학, 컴퓨터 등 많은 분야에서 이용한다. 예를 들어 시뮬레이션, 암호학, 확률적 알고리즘, 게임, 머신 러닝 등에 사용된다. 또한 컴퓨터만으로 진짜 난수(True Random Number) 를 생성하는 것은 불가능하며 진짜 난수를 생성하려면 물리적인 하드웨어 주..
알고리즘 10개월 전

[C/C++] 삽입 정렬(Insertion Sort)

삽입 정렬은 배열의 모든 요소를 순서대로 비교하고 앞서 규칙에 맞게 정렬된 배열 사이, 적절한 위치에 요소가 삽입되는 정렬 알고리즘이다. 삽입 정렬의 기본 규칙은 이렇다. 1. 비교하고자 하는 배열 요소를 지정하고 (보통 두 번째 요소) 그 이전의 값과 비교한다. 2. 오름차순, 내림차순의 기준에 따라 값을 교환한다. 3. 한번 이상 교환된 구간은 그 구간에 한하여 정렬되어있다. 4. 비교해야할 값이 더 이상 없거나 배열의 끝에 다다랐을 때 종료한다. 삽입 정렬은 최악의 경우 O(N^2), 최선의 경우 O(N)의 시간 복잡도를 가진다. 최악의 경우는 정렬이 역으로 되어있는 경우이고 최선의 경우는 이미 정렬이 되어있는 경우에는 단 하나의 교환 처리가 일어나지 않아 O(N)의 시간 복잡도를 가지게 된다. 삽..
알고리즘 3년 전

[C/C++] AABB(Axis-Aligned Bounding Box)

AABB(Axis-Aligned Bounding Box) 는 방향 전환에 대해서 정적인 사각형에 적용될 수 있는 아주 간단한 문제로써 각 사각형의 (x, y) 좌표와 (width, height) 크기, 높이만 알고 있다면 (혹은 x2, y2) 쉽게 구현할 수 있다. 여기서는 x, y 좌표와 width, height 크기, 높이를 이용한 코드를 사용한다. // 충돌 상태를 확인하는 함수 public bool isCollision(const Rect& A, const Rect& B) { if (A.x B.x // 2. x && A.y B.y) // 4...
알고리즘 3년 전

[C/C++] 퀵 정렬(Quick Sort) 재귀 구현 코드

퀵 정렬은 이름 그대로 빠른 정렬이다. 평균적인 시간복잡도가 O(NlogN)이며 일반적인 상황에서 빠른 속도를 보여주는 정렬 알고리즘이다. 퀵 정렬은 버블, 선택, 삽입 정렬과 비교했을 때 상대적으로 구현이 복잡하다. 퀵 정렬은 대표적인 분할-정복(Divide-and-Conquer) 알고리즘으로 영역을 분할해서 정렬하는 방식을 채용한다. 퀵 정렬은 영역 분할의 기준을 피벗(Pivot)으로 두고 있으며 처음 피벗은 보통 정렬할 배열의 0번지로 지정한다. 아래 코드는 퀵 정렬을 재귀 함수로 구현한 코드이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41..
알고리즘 3년 전