DevYoon

DP란 무엇일까? Dynamic Programming, 동적 계획법 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 피보나치 수열의 예시 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞의 숫자의 합을 구해야 함 D[i] = D[i-1] + D[i-2] 색칠된 부분은 동일한 문제를 다시 계산해야 하는 문제 발생 ➡️ DP로 풀이해야 함 DP는 언제 사용할 수 있을까? 다음의 가정 하에 DP를 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. ➡️ 크고 어려운 문제가 있으면 잘게 나누어 해결한 뒤에 전체의 답을 구한다. Memoization 계산한 결과는 배열에 저장하여, 동일한 계산이 필요할 경우 저장된 값을 반환하기만 ..

트리(Tree) 알고리즘🌳 1️⃣ 트리란? 1:n의 관계를 가지는 비선형 구조 원소들 간에 계층관계를 가지는 계층형 자료구조 한 개 이상의 노드로 이루어진 유한 집합 2️⃣ 용어 노드(node) : 트리의 원소 루트노드(Root) : 최상위 노드, 트리의 시작 간선 : 노드를 연결하는 선 ex) 부모노드와 자식노드 연결 형제 노드 : 같은 부모 노드를 가진 자식 노드들 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 노드의 차수 : 노드에 연결된 자식 노드의 수 트리의 차수 : 트리에 있는 노드의 차수 중 가장 큰 값 단말 노드(Leaf) : 차수가 0인 노드 (..

DAT의 문제점(음수, 문자 등 인덱스로 활용하기 불가능하거나 메모리 손해인 경우)를 보완할 수 있는 해시 알고리즘 보안에 사용하는 방식이 너무 흥미롭다...✨ keyword : 빠른 검색, DAT의 단점 보완

Heap을 사용하여 우선순위 큐 알고리즘을 공부해봅시다~~~✏️ 1️⃣ 기본 : heapq를 사용하면 Minheap이 디폴트이다! heap에서 코드로 구현했던 루트노드의 값을 출력하고, 맨 마지막에 있는 값을 최상단으로 올려 정렬하는 과정은 heappop()을 활용한다. import heapq arr = [] # insert, Minheap이 디폴트 heapq.heappush(arr, 4) heapq.heappush(arr, 1) heapq.heappush(arr, 3) heapq.heappush(arr, 9) heapq.heappush(arr, 6) # 1 4 3 9 6 # heapq.heappop(arr) -> top() and pop() print(heapq.heappop(arr)) # 1 prin..

1️⃣ 우선순위 큐(Priority Queue)의 원리 2️⃣ 완벽한 이진트리의 형태 3️⃣ 시간 복잡도 O(nlogn) Keyword : Maxheap(부모노드 > 자식노드), Minheap(부모노드 < 자식노드) 하나씩 꺼낼 때마다 부모 노드와 비교하여 Maxheap이면 → 부모 노드보다 자식 노드가 크면 swap Minheap이면 → 부모 노드보다 자식 노드가 작으면 swap 코드 구현 arr = [4,7,8,1,5,3,6,9] # Maxheap heap = [0]*20 hindex = 1 # 힙이라는 1차 배열의 인덱스 역할 def insert(value): global heap, hindex heap[hindex] = value now = hindex hindex+=1 while 1: paren..

Dijkstra 알고리즘 Dijkstra 알고리즘이란? 1️⃣ 한 정점에서 다른 모든 도착점까지 드는 최소 비용 or 최단 거리를 구할 때 사용하는 알고리즘 2️⃣ BFS, DFS보다 효율성을 높이고 빠른 속도를 위해 사용 3️⃣ 한 점에서 다른 점까지의 비용에 양수만 존재해야 함. (음수 → Bellmanford) 4️⃣ 양방향, 단방향 모두 가능 Keyword 시작 → 도착 vs 시작 → 경유지 → 도착 비교 후 더 작은 것으로 갱신 코드 구현 name = &#39;ABCED&#39; inf = 99999 arr = [[0, 3, inf, 9, 5], [inf, 0, 7, inf, 1], [inf, inf, 0, 1, inf], [inf, inf, inf, 0, inf], [inf, inf, 1, i..