공부 메모장

공간 복잡도란?→ 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계 ex) N짜리 2차원 배열이 필요하면 O(N^2), 따로 배열이 필요없으면 O(1)임. 문제 풀 때 기억하면 좋은 것512MB = 1.2억 개의 int이다.(메모리 제한이 512MB일 때, int변수를 대략 1.2억 개 정도 선언할 수 있음→ int 1개가 4바이트인 것을 이용해서 계산 가능)

DFS - 갈 수 있을 만큼 깊이 간 후, 갈 곳이 없으면 이전 정점으로 돌아감 DFS는 방문 순서를 스택으로 관리한다. 스택을 쓰는 이유는, dfs 안에서 다시 dfs 함수를 호출하는 재귀 호출을 하기 때문이다. 함수 호출은 시스템 스택에서 관리한다.  ( ->  다시 말해, 스택을 특별히 정의하지 않아도 사용할 수 있다.)BFS - 시작점에서 가까운 정점 순서대로 탐색   큐를 이용하는 BFS는 명시적으로 큐를 정의해줘야 한다. 먼저 방문된 순서대로 다시 방문을 진행해야 하기 때문에, 선입선출형 자료구조인 큐가 적합하다.

이 사진에 나온 완전이진트리는 최대힙일까 아닐까? 일단 답은 최대힙이 맞다..근데 왜??? 이 빨간 동그라미 부분을 보면 위에꺼가 밑에꺼보다 작은데 이게 최대힙이라고???할 수 있다..  그런데 이렇게 최대힙을 생각하면 안 된다!!3은 6을 기준으로삼촌 노드인거지 부모노드가 아니기 때문에둘의 크기는 최대힙에서 고려 대상이 아니다...! 오직 부모노드와 자식노드끼리만 비교를 해야한다! 그러므로 이 그림은 최대힙이 맞다.