Game Develop

(A + B) % p = ((A % p) + (B % p)) % p (A * B) % p = ((A % p) * (B % p)) % p (A - B) % p = ((A % p) - (B % p) + p) % p (A / B) % p = (A * B^(p-2)) % p = ((A % p) * (B^(p-2) % p)) % p a^b => a^(b/2) * a^(b/2) // b가 짝수일 경우. a^b => a^(b/2) * a^(b/2) * a // b가 홀수인 경우.

선택정렬 (Selection Sort) i가 기준, j가 두번째 포문일 시, i는 당연 처음부터 돌리고 j는 i부터 돌린다. 자기자신도 비교에 포함해야됨. 어쨌든 i기준 잡고 j돌리면서 최소값과 해당 값의 인덱스를 저장해놓고, 반복문 끝낸후에 i랑 최소값이랑 스왑해주면 된다. 시간복잡도는 O(n^2). 매 카운트마다 n-1번의 비교를위한 반복문을 돌려야 하기 때문 삽입정렬 (Insertion Sort) 최선의 성능 : O(n) -> 스왑같은거 없이 비교만할 떄, 즉 값이 거의 정렬된상태로 들어왔을 때. 최악의 성능 : O(n^2) -> 아예 역순으로 배열이 인풋으로 왓을 때. 비교도 n^2번해야하고 스왑도 n^2번 해야한다. 즉, O(n^2). 물론 다른것들에 비해 '무조건'해야하는건 아니기 때문에 실제..

https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 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 void recur(int from, int to, int bypass, int n) { if (n == 1) // 옮길게 한개면 그냥 그대로 옮기면됨. { cout

비트마스크 ->집합의 요소들을 비트로 표현하는 방법. 특정알고리즘이라기보다는 기법,테크닉을 의미한다. 예를들어 {1,2,3,4,5} 의 집합이 있다면 부분집합은 다음과같다 int[] array1 = {1,2} int[] array2 = {1,2,4}............... 등등 물론 배열로 표현할수는 있다. 하지만 그러면 메모리를 많이 잡아먹게된다. 집합의 개수가 n개라 가정하면, 부분집합의 개수는 2^n 개이다. (자기자신 포함) n이 '10'만되도 이미 2^10인 1024개이다. 하지만 저걸 bit로 표현해보자. {1,2,3,4,5} 의 부분집합 {1,2}는 아래와 같이 표현할 수 있다. 11000 {1,2,4} 1,1,0,1,0 이 2진수들을 10진수로 바꿔서 보관하면, 고작 int형 하나로 하..

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 42 43 44 45 46 47 48 49 50 51 void quickSort(vector& data, int startIndex, int endIndex) // pivot은 인덱스순서로 잡는걸 기준으로한다. { if (startIndex >= endIndex) return; // 반씩 자르다 최종적으로 원소개수가 1개가 될 경우. int pivot = startIndex; // 피벗 설정. int left = pivot + 1; int right = endIndex; while (1) { while ..

신장 트리 - n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리(Minimum Spanning Tree) - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 일단 두 알고리즘 최소신장트리(MST)를 만들기 위한 알고리즘이다. 즉, 주어지는 간선의 정보로 최소의 비용을 지불해서 하나의 집합을 만드는 알고리즘이다. 크루스칼 알고리즘 크루스칼 알고리즘은 정점에 비해 간선의 개수가 적을때 MST(최소신장트리)로 만들기에 적합하다. Union-Find 알고리즘(혹은 상호배타적 집합(Disjoint-Set)알고리즘)을 선행학습해야한다. 로직은 다음과 같다. 1. parents테이블을 각자의 값으로 초기화시킨다. -> pare..