Game Develop

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Comm..

병합정렬과 퀵정렬 둘 다 시간복잡도는 nlogn으로 알려져 있다. 다만, 퀵정렬같은경우 최악의 경우 n^2이 되는 경우가 발생하지만 병합정렬은 항시 nlogn을 보장해준다. 물론 병합정렬은 추가적인 메모리공간을 소비한다는 단점이 있긴 하다.(배열기반의 정렬이라면) 대신 링크드리스트같은 컨테이너의 정렬이라면 추가적인 메모리공간마저 소비하지 않기 때문에 굉장히 효율적이다. 병합정렬이란거 자체가, 쪼갠다음 다시 조합하는건데 배열기반의 경우 조합하기위해서 새로운 공간에다가 조합하는거고 링크드리스트는 각각의 노드가 독립적이기 때문에(주소만 안잃어버린다면) 값 비교후 포인터만 머리와 꼬리에 연결해주면 되기 때문이다. 그리고 퀵정렬은 불안정한 정렬에 속한다. 정렬을 했을 때 중복된 값이 처음의 배열과 불일치하는 경우..

보통 음수가중치(가중치의 합이 음수값이 되는)를 갖는 간선이 있을 경우 다익스트라를 사용해도 되는 경우가 있고, 안되는 경우가 있다. 이 글에서의 다익스트라는 우선순위큐와 인접리스트를 사용한 다익스트라라고 가정한다. 아래의 그림을 봐보자. 시작은 s에서 시작한다고 가정한다. c와 d를 봐보자. c->d는 6이고 d->c는 -3이다. 이경우엔 음수간선이 있지만 음수사이클은 발생하지않는다. 먼저 c에대한 거리값은 5로 업데이트 될 것이다. 후에 c에서 d를 뽑아서 d에 대한 거리값을 11로 업데이트 후, d를 뽑았을 때 c로 가는 간선이 있기 때문에 c에대한 최솟값갱신을 시도해볼 것이다. 11-3을 하면 8인데, 이미 더 짧은 5로 저장되어있기 때문에 갱신될 일은 없고 여기서 그냥 끝이다. 이렇게 위와 같이..

(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 ..