Explict Graph데이터를 저장할 공간을 직접 할당하여 정점과 간선을 기록하는 방식이다.인접 행렬, 인접 리스트, 포인터 기반 연결 리스트를 통해서 직접 데이터를 구현하는 방식.A와 B가 연결되어있다라는 정보를 메모리에 물리적으로 저장하는 셈이다.노드간의 관계를 직관적으로 파악할 수 있으나, 노드 수가 많아질수록 메모리 사용량이 아작난다. (O(V^2))Implict Graph데이터를 저장하는 데신, Rule/Function/Numbers...등을 통해 실시간으로 간선을 계산하는 방식이다.수식이나 조건문을 이용해서 "표현"한다.메모리에 간선 정보를 저장하지 않고, 탐색 과정에서 "다음 노드는 어디인가?"를 로직으로 산출한다.메모리 효율이 아-주 좋고, Locality가 보장됨에 따라 Cache hi..

5개월이라는 시간이 흐르면 자료구조/알고리즘 기억해 놨던게 사라지는 기현상이 있어서... 이진 탐색과 매개변수 탐색에 대해 이야기를 해보려고 한다. 사실 Binary Search는 구현 자체는 크게 어렵지도 않고, 개념적으로도 마찬가지로 어렵지도 않다. 업다운 게임을 생각해 보면 편한데, 1~100까지 수 중에 하나를 고르라 하면 50이 먼저 나올게 당연한 것 아닌가? 마찬가지로 이진 탐색도 정렬되어 있는 수 중에서 (혹은 범위가 지정되어 있는 수 중에서) Up-Down 게임을 열심히 지지고 볶으면 된다. 물론 이진 탐색의 경우 수 중에서 "해당 값"이 반드시 존재하는 경우에 사용하고, 만약 "범위"로 검색하고 싶으면 매개변수 탐색이라는 것을 동원해야 한다. #include #include using ..

Ref : Introduction to ALGORITHMS, Third Edition, Thomas H. CormenRef : C++ DS and ALgoriithm Design Principles, Jon carry.※ 해당 게시글을 이해하기 위해서는 자료구조에 대한 기초적인 지식과 적당한 Python/CPP 능력이 필요합니다.쨋든 DP의 기법들인 Memoization/Tabulation을 알아봅시다. (참고로 Memorization이랑 헷갈리시면 곤란합니다.) 메모이제이션은 대게 하향식 방식에서 부분문제의 답을 캐시에 넣어 사용할때를 말합니다. 대게 재귀를 쓰고, 필요한 값만 요청될 때 계산합니다. 또한 다음 조건을 만족할때 성립하게 됩니다.부분 문제 해법을 캐시에 인덱싱하여 저장하는 방법이 유용해야..

Ref : Introduction to ALGORITHMS, Third Edition, Thomas H. Cormen※ 해당 게시글을 이해하기 위해서는 자료구조에 대한 기초적인 지식과 적당한 Python/CPP 능력이 필요합니다.Dynamic Programming(이하 통칭 DP라 함)은 분할 정복 마냥 문제를 나눠서 푸는게 핵심입니다. 단지 분할 정복이랑 다른 점이 있다면 - 나눈 문제들이 답을 서로 공유한다는 점이죠. 그러니까 대충 정리하자면.... DP는 Sub-Problem을 한번 풀과 결과를 데이터 테이블에 저장해 놓습니다.결과적으로 해당 Sub-Problem을 다시 만났을 때 - 계산을 다시 할 필요가 없어집니다.call fib(6) └─ fib(5) └─ fib(4) ..