알고리즘을 좋아하는 나

Heap 은

최소 힙과

최대 힙이 있다.

Heap 은 완전 이진트리다.

맨 위의 전구는 한 번씩 다 껐다 켜본다.

모든 전구는 2번 이상 건드리지 않는다.

대충 나오는 시간복잡도

O(2^N*N^2)

=> O(2^N)

N은 최대 18

풀이 방법 : 위의 전구가 켜져있으면 끈다.

근데 맨 위의 전구는 방법이 없다.

그래서 다 해본다.

위상 정렬 Week 끝!

내일은 Merge Sort 를 다시 복습 해야겠다.

다음주는 MST 를 공부해야지!

음.. 친구의 부탁으로 만들어봤다.

애니팡이 맞으려나?

게임 진행하는 코드를 짰다기보단.

게임에서 사용하는 로직들을 짰다.

상하좌우 3개가 같은게 있으면 클리어하고, 정렬

*.spec은 테스트하는 코드

코드링크

flowchart를 그리면서 했으면, 더 최적화가 가능했을거 같다.

ACM CRAFT와 비슷한 문제다.

1. in-degree가 0인거 부터

2. 문제 번호가 낮은거 우선순위

문제 번호가 낮은거 우선순위는 priority_queue로 하면되고,

in-degree는 위상정렬

A -> B

C -> B 일때,

B = MAX(A, C)

이런식으로 값이 들어간다.

이번주는 위상 정렬 문제만 풀어야지 ㅋㅋ

만약 진입차수가 0인게 endVertex 인 것을 처리하기 위해

완전 그래프는 모든 vertex가 연결돼있다.

출력하는건 사전순이다.

그래서 현재 vertex에서 사전순으로 제일 가까운것을 출력하면 된다.

그런데 N(N-1) 번째에는 1이 출력되고

N(N-2)번째에는 N이 출력된다.

이 방법을 이용하면 쉽게 풀이가능

dp로 풀었다. O(NM)

입력차례대로 위칸과 왼쪽칸과 왼쪽위 대각선 칸을 비교해서 가장 작은값 + 1로 새로운 정사각형을 만들 수 있다.

NYPC에서 풀었던 문제와 유사하다.

NYPC문제때는 급수를 이용해서 풀었었는데 틀리다고 나왔었다.

벽 부신다!!!