Stunning-PS 팀 블로그

트리(Tree) Tree : 노드로 이루어진 자료 구조 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖는다. 비선형 자료구조로 계층적 관계를 표현한다. 그래프의 한 종류다. # 이진 트리 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None 트리(Tree)와 관련된 용어 루트 : 부모노드 leaf node : 자식이 없는 노드 간선(edge) : 노드를 연결하는 선 노드의 크기 : ...

정렬 알고리즘 1. 거품 정렬 (Bubble Sort) 동작 과정 예제 코드 시간복잡도 2. 선택 정렬 (Selection Sort) 동작 과정 예제 코드 시간복잡도 3. 삽입 정렬 (Insertion Sort) 동작 과정 예제 코드 시간복잡도 4. 퀵 정렬 (Quick S...

너비 우선 탐색 수행 순서 구현 코드 예제 무네 너비 우선 탐색 시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서,방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 가까운 정점들을 먼저 방문하고 멀리있는 정점들은 나중에 방문하는 순회방법 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야하므로 선입선출의 구조를 갖는 큐를 사용 너비 우선 탐색의 수행순서 (1) 시작 정점 𝑣를 결정하여 방문한다. (2) 정점 𝑣에 인접한 정점들 중에서 방문하지 않은 정점을 차례로 방문하면서 큐에 e...

DFS와 BFS 시작하기 전에… 그래프의 표현 방법 1. 인접 행렬(Adjacency Matrix) 2차원 배열로 그래프의 연결관계를 표현하는 방식 INF = 99999999999999 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] 2. 인접 리스트(Adjacency List) 리스트로 그래프의 연결 관계를 표현하는 방식 graph = [[] for _ in range(3)] graph[0].append((1, 7)) # 0번 노드는 1번 노드와 7의 거리로 연결되어 있다는 뜻 1. BFS Breadth First Searc...

BFS 알고리즘이란? BFS(Breadth-First-Search) 알고리즘은 그래프 탐색 방법 중의 1개로 인접한 노드(가까운 노드)를 먼저 탐색하는 방법이다. 두 노드 사이의 최단 경로 또는 임의의 경로를 찾고 싶을 때 선택되는 방법이다. 그래프 탐색이란? → 하나의 정점에서부터 차례대로 다른 모든 정점들을 한 번씩 방문하는 것 Ex) 특정 도시에서 다른 도시로 이동, 전자 회로에서 특정 단자가 연결되어 있는 여부 확인 특징 깊은 탐색(DFS)가 아닌 넓게 탐색(BFS) 하는 방법이다. 최단 경로를 찾고 싶을 때 활용하는 알고리즘 큐(queue)를 사용하는 알고리즘 → 재귀를 이용하지 않...

그리디 알고리즘 그리디 알고리즘은 탐욕적으로 문제를 푸는 알고리즘이다. 탐욕적이라는 말은 현재 상황에서 지금 당장 좋은것만 고르는 방법을 의미한다. 그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’ 와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다. 그리디 알고리즘의 정당성 그리디 알고리즘은 모든 알고...

Greedy 알고리즘이란? 특징 Greedy 문제 예시(스케줄링) Binary Search 문제 모음 Greedy 문제 모음 참고자료 Greedy 알고리즘이란? Greedy 알고리즘은 Greedy(욕심 많은, 탐욕적인)의 뜻을 가지고 있는 알고리즘으로 욕심쟁이, 탐욕법 알고리즘이라고도 불립니다. Greedy 알고리즘은 경우의 수가 존재할때 경우를 선택하는 경우마다 최선이라고 생각하는 경우를 선택하는 알고리즘입니다. 즉 현재 선택해야 하는 단계에서 미래의 상황을 고려하지 않고 현재 할 수 있는 최적의 선택을 하는 알고리즘이라고 이해하시면 편할 것 같습니다....

트라이 (Trie) 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 보통 Prefix Tree, digital search tree, retrieval tree라고도 부릅니다. 트라이는 문자열을 key로 사용하는 동적인 set 또는 연관 배열을 저장하는 트리의 확장된 구조입니다. 트라이 자료구조는 문자열을 탐색하고자할 때 단순하게 하나씩 비교하면서 탐색을 하는 것보다 훨씬 효율적입니다. 단, 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점이 있습니다. 위 그림과 같이 ...