알고리즘/개념

📌 - 중복되는 연산을 줄이자 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제가 있다. 컴퓨터 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. ❗️- 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야한다. 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 방법이 바로 다이나믹 프로그래밍이다. 👉 대표적인 예시 - 피보나치 수열 - n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수 - 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1 피보나치 수열을 재귀함수로 만들 수..

🗒️ 위상 정렬이란? 위상정렬이란 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 이해하기 쉽게 예를 들자면 위상 정렬을 수행하게 되는 예시로는 여러 게임들의 직업 시스템을 들 수 있다. 예를 들어 직업 시스템에는 '모험가'로 시작해서 '마법사'가 될 수 있다. 이때 '모험가' 및 '마법사'를 각각의 노드로 표현하고, '모험가'에서 '마법사'로 이어질 수 있도록 방향성을 갖는 간선을 그린다. 그래프에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다. 다시 예를 들면 직업의 단계가, '마법사'가 되기 위해선 '모험가'여야 하고, '대마법사'가 되기 위해서는 '마법사'여야 한다고 가정하자. 이 경우에서 '대마법사'가 되기 위해서..

🕹️ - 신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 🕹️ - 크루스칼 알고리즘 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때 필요한 알고리즘이다. 그리디 알고리즘으로 분류되고 기본적으로 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다. 이때 사이클을 발생 시킬 수 있는 간선의 경우, 집합에 포함 시키지 않는다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. - 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. - 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. 모든 간선에 대하여 2번의 과정을 반복한다. 1️⃣..

🚀 Union_Find(서로소 집합 자료구조) Union_Find 자료구조는 스택의 pop, push처럼 Union(합집합), Find(찾기) 연산으로 구성된다. Union 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다. - A와 B의 루트 노드 A`, B`를 각각 찾는다. - A`를 B`의 부모 노드로 설정한다.(B`가 A`를 가리키도록 한다.) 모든 Union 연산을 처리할 때까지 1번 과정을 반복한다. 실제로 구현 할 때는 A`와 B`중에서 더 번호가 작은 원소가 부모노드가 되도록 구현하는 경우가 많다. 초기 단계에서 각자 자기 자신을 부모로 가지도록 초기화 한다. Union 1,4 - 현재 각각 루트 노드가 1과 4이기 때문에 둘 중 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 ..

📔 트리 구조 노드와 가지로 구성되고 각 노드는 가지를 통해 다른 노드와 연결된다. 트리에는 루트, 리프, 비단말 노드 , 자식, 부모, 형제, 레벨, 차수, 높이 등등의 용어들이 있다. 가장 위쪽에 있는 노드를 루트 가장 아래쪽에 있는 노드를 리프 루트에서 얼마나 멀리 떨어져 있는지 나타내는 레벨 각 노드가 갖는 자식의 수를 차수 루트에서 가장 먼 리프까지의 거리가 높이 📔 이진 트리의 검색 너비 우선 검색 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법 깊이 우선 검색 깊이 우선 검색은 리프에 도달 할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 한다. 깊이 우선 검색의 세가지 종류의 스캔 방법 더보기 노드 방문 -> 왼쪽 자식 -> 오른쪽 자..

🗒️ 우선순위 큐 - 큐는 먼저 들어온 데이터가 먼저 처리되는 자료구조이지만, 우선 순위 큐는 우선 순위가 높은 데이터부터 처리하는 자료구조이다. 배열, 연결리스트, 힙으로 모두 구현할 수 있지만 보통 시간복잡도가 적은 힙을 사용한다. 💡 우선순위큐 from queue import PriorityQueue q = PriorityQueue() # 삽입 q.put(3) q.put(2) q.put(1) # 삽입시 우선순위 지정 q.put((5,"banana")) q.put((1,"apple")) q.put((3,"FINE")) # 반환 print(q.get()) # 1 print(q.get()) # 2 print(q.get()) # 3 # 사이즈 print(q.qsize()) # 튜플 값만 print(q.ge..