코딩일기

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

안녕하십니까 다제입니다. 오늘은 힙(heap)에 대해서 알아보고자 합니다. Leetcode "k 경유지 내 가장 저렴한 항공권" 문제를 푸는 힙을 이용하여 푸는 풀이가 있었습니다. 그런데, 아무리 문제를 고민해도 풀 수가 없었습니다. 문제를 쪼개서 살펴보니 힙에 대한 개념이 잘 잡혀있지 않다는 사실을 알게되었고 이를 해결하기 위해 힙(heap)을 심도 깊게 공부해보았습니다. 목차 1. heap의 정의 2. heapq.heappop(), heapq.heappush() 의 작동 방식 이해하기 3. heap 구현하기(heapify) 4. heap 정렬 구현하기 1. heap의 정의 - 완전 이진 트리이며, 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같은 자료구조를 말합니다. - 즉 부모노드의 데이터..

안녕하십니까 다제입니다. 지금까지는 배열과 정렬, 링크드 리스트 등에 대해서 배웠습니다. 오늘은 hash Table에 대해서 한번 배워보도록 하겠습니다. ** 저장 진행되는 순서 ** data -> Hash Function -> Hash Table 학습하기에 앞서서 용어를 정리하고 넘어가도록 하겠습니다. ** 용어정리 ** 해시(Hash) : 데이터를 관리 및 유지하는 자료구조 해시함수(Hash Function) : 데이터를 효율적으로 관리하기 위해 일정한 규칙으로 데이터를 변환하는 함수 해시값(Hash Value) 또는 해시코드 : 데이터가 해시함수를 통해 변형된 어떤 값 해싱(Hashing) : 데이터가 해시함수를 통해 특정값으로 변형되고 이를 key-value형태로 저장되는 일련의 과정 해시테이블(..

안녕하십니까 다제입니다. 오늘은 Greedy Algorithm에 대해서 알아보도록 하겠습니다. 언제나 알고리즘은 장단점이 있으며, 그 상황에 맞게 적절히 사용하는게 중요하고 누차 말씀드리고 있습니다. 오늘도 Greedy Algorithm가 무엇이며, 장단점과 언제 사용해야하는지, 소스코드까지 같이 살펴보도록 하겠습니다. 1. 정의 매순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 최적해에 도달하는 기법 2. 개요 우리는 앞에서 DP(dynamic programming)에 대해서 배웠습니다. DP는 모든 경우의 수를 따져본다는 단점이 있습니다. 이러한 단점을 극복하기 위해서 Greedy Algorithm입니다. 위에서 언급한 바와 같이 Greedy Algorithm는 항상 최적해를 ..

안녕하십니까 다제입니다. 오늘은 Dynamic Programming에 대해서 포스팅을 진행하고자 합니다. Dynamic Programming은 memoization(하향식 접근)과 Tabulation(상향식 접근)으로 구성되어 있습니다. 먼저 Dynamic Programming에 대해서 살펴본 뒤 memoization(하향식 접근)과 Tabulation(상향식 접근)도 함께 살펴보도록 하겠습니다. 사실 Dynamic Programming은 Divide and Conquer와 매우 유사하지만 사용해야하는 조건이 있습니다. Dynamic Programming는 1. 최적부분 구조(Optimal Substructure)가 있고 2. 중복되는 부분 문제(overlapping subproblems)가 있다면 사용..

안녕하십니까 다제입니다. 오늘은 Divide and Conquer에 대해서 함께 공부를 해보도록 하겠습니다. 해당 포스팅은 재귀 개념을 확실히 알고 있어야 합니다. 혹시 모르시는 분들은 재귀함수 포스팅 글을 다시 한번 봐주시면 감사드리겠습니다. 2021.05.16 - [Code] - [자료구조] 3. 재귀함수(Recursion) 이해하기 (feat. codestates, self_tutorial) [자료구조] 3. 재귀함수(Recursion) 이해하기 (feat. codestates, self_tutorial) 안녕하십니까 다제입니다. 이제부터는 재귀에 대해서 공부를 진행해보고자 합니다. 많이 어렵다고 소문난 개념이지만, 저와 함께 하시면 쉽게 하실 수 있습니다! 함께 가보시죠! 1. 재귀함수 정 daj..

안녕하십니까 다제입니다. 오늘은 Brute Force에 대해서 알아보도록 하겠습니다. Brute Force는 해킹쪽에서 Brute Force attack이라는 용어로 더 많이 알려진 단어입니다. 실제로도 Brute Force를 검색해보니 온통 Brute Force attack에 대한 이야기만 하고 있더라고요 Brute Force attack은 무차별적으로 마구마구 공격을 한다라는 뜻입니다. 공격이라는 의미만 뺀다면 알고리즘 측면에서 무차별적으로 생각없이 모든 경우의 수를 다 시도해본다고 생각하시면 됩니다. 오늘은 이 Brute Force를 왜 사용하고 어떻게 사용하는지를 간단하게 다루어보도록 하겠습니다. 1. Brute Force 정의 무차별적으로 가능한 모든 경우의 수를 시도하는 가장 순진한 알고리즘 ..

보호되어 있는 글입니다.