Game Develop

https://www.acmicpc.net/problem/1461 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#include iostream>#include string>#include map>#include vector>#include algorithm>#include math.h>#include queue>#include functional>#include sstream>#include memory.h>#include..

https://www.acmicpc.net/problem/17951 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include iostream>#include string>#include map>#include vector>#include algorithm>#include math.h>#include queue>#include functional>#include sstream>#include memory.h>#include deque>#include set>#incl..

https://www.acmicpc.net/problem/3079123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include iostream>#include string>#include map>#include vector>#include algorithm>#include math.h>#include queue>#include functional>#include sstream>#include memory.h>#include deque>#include set>#includ..

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). 물론 다른것들에 비해 '무조건'해야하는건 아니기 때문에 실제..