해물파이의 괴발개발 TIL

그 문제를 풀 때 시간과 공간을 얼마나 차지하는지 시간과 공간의 복잡도? 알고리즘이 얼마나 효율적인가를 알 수 있음 사실 프로그래밍 인터뷰에서 자주 묻기 때문에 중요해! 알고리즘을 짤 때, 1.돌아가는가 2. 시간복잡도 3. 공간복잡도 순으로 중요 Constant Time = 요소의 갯수와 상관 없이 정해진 횟수만 실행되면 답이 나오는 것 Big-O Notation을 구하는 방식 3 -> O(1) 2n -> O(n) 2n + 3 -> O(n) n^2 -> O(n^2) --> 최악의 연산 경우의 수에서 최고차 항만 남고 계수를 제거한 것을 Big-O Notation이라고 보면 된다. (지수가 높은 것이 커지는 것을 지수가 낮은 것이 따라잡기 어렵기 때문에 이렇게 표현하는 것) Big-O Notation으로..

그래프란? 그래프는 노드(혹은 정점(vertex))와 노드와 노드 사이를 연결하는 간선(edge)로 구성. 그래프는 무방향(=간선에 의해 연결된 두 노드가 대칭일 수 있음)일 수도 있고 방향성(=비대칭 관계가 존재함)이 있을 수도 있다. 그래프의 개념 -진입 차수는 노드를 머리로 하는 간선이 다른 노드와 연결된 갯수. -친출 차수는 노드를 꼬리로 하는 간선이 다른 노드와 연결된 갯수. -인접 행렬 방식은 그래프 구현 방식 중 하나로 보통 배열을 이용해 정보를 저장한다(adj[i][j]). -인접 리스트 방식은 그래프 구현 방식 중 하나로 그래프의 연결 관계를 vector의 배열(vectoradj[])로 나타내는 방식이며 vector에 노드 번호가 그대로 저장된다. 트리구조란? 노드로 구현된 계층적 자료구..