이번 포스팅에선 탐욕법(그리디) 알고리즘에 대해 알아보겠습니다. 개념과 알고리즘을 사용하는 조건을 알아보고, 동전 문제를 통해 활용 예시를 살펴보겠습니다. * 언어는 C++로 진행됩니다. 목차 📃 그리디 알고리즘 개념 및 조건 📃 그리디 알고리즘 예제 - 동전 문제 그리디 알고리즘 개념 및 조건 📌 개념 그리디 알고리즘은 가장 최선의 선택만을 쫒아가는 알고리즘입니다. 다이나믹 프로그래밍의 경우, 다양한 경우들을 하나하나 살펴보면서 최선의 수를 찾고자 했습니다. 그와 달리, 그리디 알고리즘은 오직 눈앞의 최선만을 쫒아 갑니다. 그리디 알고리즘은 Best Solution을 찾기 위한 알고리즘은 아닙니다. 그저 최선을 쫓다보면 결과도 좋겠지 하는 막연한 기대가 구현된 알고리즘이라 할 수 있습니다. 이때문에 현..

이번 포스팅에선 큐의 변형인 원형 큐(Circular Queue)에 대해 알아보겠습니다. 큐에 대한 사전 지식이 없다면 이해가 어려울 수 있으니, 미리 개념을 습득하고 오시길 바랍니다. [큐(Queue) 개념 이해하기] https://mengu.tistory.com/30?category=931463 [자료구조] 큐(Queue) 개념 및 코드 구현 이번 포스팅에선 큐(Queue)의 개념과 코드 구현을 할 것이다. 만약 스택(Stack) 개념을 알지 못한다면 이전 포스팅을 보고 오자. [이전 포스팅 URL: https://mengu.tistory.com/29] [자료구조] 스택(Stack) 개념.. mengu.tistory.com 목차 📃 원형 큐(Circular Queue) 정의 및 원리 📃 원형 큐 구현..

오늘은 자료구조 중 하나인 덱(Deque)에 대해 알아보겠습니다. 덱은 스택, 큐와 아주 유사한 자료구조이며, 스택/큐의 단점을 보완하고 장점을 가져왔기 때문에 유용하게 쓰입니다. 목차 📃 덱(Deque) 개념 📃 덱(Deque) 코드 📃 덱(Deque) 예제 덱(Deque) 개념 📌 정의 덱은 스택/큐와 같은 일차원의 선형 자료구조입니다. 스택과 큐 연산을 모두 지원하기에, 양 끝에서 삽입과 삭제가 가능한 자료구조입니다. 내부가 double-linked list(양방향 연결 리스트)로 구현되어 있습니다. 📌 시간 복잡도 O(1) 양방향 연결 리스트로 구현되어 있어, 양 끝 요소의 추가/삭제가 O(1)를 만족합니다. 그에 반해 List는 고정된 사이즈의 메모리를 갖는 배열로, 첫 번째 요소를 삭제하면 모..

이번 포스팅에선 우선순위 큐에 대해 알아보겠습니다. 큐, 스택에 대한 이해가 없으신 분은 밑의 포스팅을 먼저 보고 와주시면 감사하겠습니다. 본 포스팅은 python으로 진행합니다. [스택 개념 및 코드] https://mengu.tistory.com/29?category=931463 [자료구조] 스택(Stack) 개념 및 코드 구현 자료구조 중 하나인 스택(Stack)에 대해 알아보고, 직접 코드로 구현해보자. 배열 구현과 연결 리스트 구현 모두 해볼 것이다. 들어가자. 스택(Stack) 개념 가장 나중에 넣은 데이터를 가장 먼저 빼 mengu.tistory.com [큐 개념 및 코드] https://mengu.tistory.com/30?category=931463 [자료구조] 큐(Queue) 개념 및 ..

매개 변수 탐색은 이분 탐색의 활용 버전입니다. 이분 탐색은 탐색을 통해 target 값을 찾는 알고리즘이었습니다. 그렇다면 매개 변수 탐색도 target 값을 찾는 또 다른 방법일까요? 아닙니다. https://mengu.tistory.com/83?category=931463 [Algorithm] 이분 탐색(Binary Search) 개념 및 코드(python) 순서대로 나열되어 있는 배열이 있습니다. 이 배열에서 target 값을 찾으려 하는데, 배열 요소가 100만개라 모두 비교하면 시간이 많이 걸립니다. 이때 더 빠르게 target 값을 찾을 순 없을까요? 이 mengu.tistory.com 📌 매개 변수 탐색(Parametric Search) 정의 매개 변수 탐색은 조건을 만족하는 값(targe..

📌 쿼드트리란 무엇인가? 이진트리에 대해선 들어보셨을 겁니다. 한 개의 부모 노드에서 두 개의 자식 노드가 파생되는 구조의 자료구조입니다. 파이썬으로 구현하면 이렇게 생겼습니다. 🎨 이진 트리 구현 (python) class Node: def __init__(self): self.item = item self.left = None self.right = None 쿼드트리는 이진트리의 응용 버전입니다. 한 개의 부모 노드에서 네 개의 자식 노드가 파생되는 구조가 쿼드트리입니다. 쿼드트리는 이진트리처럼 나무가지로 표현할 수도 있습니다. 📌 쿼드트리 정의 하. 지. 만 쿼드트리는 3D 데이터를 표현하기 위한 자료구조인 '장면 그래프(Scene Graph)'에 해당합니다. 상하 개념이 없고, 3차원 세계를 4개..