CS (23) 썸네일형 리스트형 [알고리즘] Insertion Sort Insertion Sort 처리되지 않은 데이터 중 하나씩 골라 적절한 위치에 삽입하는 알고리즘 Process 1. 먼저 두번째 데이터와 첫번째 데이터의 대소를 비교해 두번째 원소가 더 작다면 교환한다 2. 다음 인덱스는 이전 데이터들과 비교해 적절한 위치에 둔다 Code numbers = [] length = 100 for i in range(length, 0, -1): numbers.append(i) for idx, num in enumerate(numbers): for n_idx in range(idx, 0, -1): if numbers[n_idx] < numbers[n_idx - 1]: numbers[n_idx], numbers[n_idx - 1] = numbers[n_idx - 1], numbe.. [알고리즘] Selection Sort Selection Sort 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 처리되지 않은 데이터 중 맨 앞의 데이터와 바꿔가는 알고리즘 Process 1. 처리되지 않은 데이터 중 최소값을 찾는다 2. 처리되지 않은 데이터 중 맨 앞에 위치한 값과 교체한다 3. 그 다음 인덱스 부터 같은 방법으로 교체한다 Code numbers = [] length = 100 for i in range(length, 0, -1): numbers.append(i) for idx, num in enumerate(numbers): min_idx = idx for n_idx in range(idx + 1, length): if numbers[n_idx] < numbers[min_idx]: min_idx = n_idx num.. [알고리즘] Bubble Sort Bubble Sort 서로 인접한 두 데이터의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 Process 1. 첫번째 원소부터 마지막 원소까지 인접한 데이터를 비교해 조건에 맞지 않다면 서로 교환 2. 1번 수행 후엔 가장 큰 원소가 맨 뒤로 이동하게 되어 정렬에서 제외되고 (배열의 크기 - 1)만큼 반복하면 모든 데이터가 정렬됨 Code numbers = [] length = 100 for i in range(length, 0, -1): numbers.append(i) for _ in range(length): for i in range(length - 1): if numbers[i] > numbers[i + 1]: numbers[i], numbers[i + 1] = num.. [알고리즘] Floyd Warshall Algorithm Floyd Warshall Algorithm 이란? 모든 정점에서 모든 정점으로 가는 최단거리를 구하는 알고리즘 특징 가중치/비가중치 그래프 모두에서 최단거리를 도출해낼 수 있다 음수 가중치를 가져도 사용가능하다 (단, cycle이 있고 가중치의 총 합이 음수인 경우엔 성립하지 않는다) 시간복잡도가 O(V³) 이다 다이나믹 프로그래밍(DP)을 사용하는 알고리즘이다 Floyd Warshall Algorithm 동작 과정 1. 모든 노드 무한대로 초기화 2. 자기 자신에게 가는 간선의 가중치는 0으로 설정 ( i -> i ) 3. 나머지 노드 방문하며 주변 노드에 방문하는 최단거리 갱신 - i 에서 j 로 가는데에 크게 두가지 경우로 나뉘고, 이 두가지 경우 중 최소값을 선택 1) i 에서 j 로 가는 경로.. [알고리즘] Trie Trie 란 ? 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 radix tree 혹은 prefix tree라고도 함 위와 같은 구조로 조회 시 문자열의 길이만큼의 시간 복잡도를 가진다 검색어 자동완성, 사전에서 찾기, 문자열 검사 등으로 활용된다 O(m) m:문자열 길이 Trie 구현 소스 class Node: def __init__(self, key): self.key = key self.child = dict() self.count = 0 class Trie: def __init__(self): self.head = Node(None) def insert(self, word): cur = self.head # 루트를 현재 포인터로 설정 for ch in word: cur.count.. [알고리즘] Dijkstra's Algorithm Dijkstra's Algorithm 두 정점 사이의 최단거리를 찾을 때 사용하는 알고리즘 가중치가 없는 최단거리를 구할 때 DFS, BFS 알고리즘을 사용하지만, 양의 가중치가 있고, 그 가중치가 모두 다를 경우 다익스트라 알고리즘을 사용한다 Dijkstra's Algorithm 동작 과정 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산 후 최단 거리 테이블 갱신 5. 위 과정에서 3번과 4번을 반복 Dijkstra's Algorithm 구현 소스 아래는 다익스트라 알고리즘 문제인 '민준이와 마산 그리고 건우' 소스이다. https://www.acmicpc.net/problem/.. [DB] Index with B-Tree B-Tree Binary Tree 에서 확장된 트리 한 node가 가질 수 있는 child node의 수가 2개 이상인 트리 각 노드는 여러개의 key를 가질 수 있고 각 key에 대응하는 data도 가지고 있다 leaf node는 모두 같은 레벨에 존재해야 한다 B+ Tree B-Tree 에서 확장된 트리 branch node 에는 key값만 가지고 있고, leaf node에만 data가 저장된다 따라서 disk I/O 시 disk block에 더 많은 key를 배치할 수 있기 때문에 key 탐색 시 B-Tree 보다 상대적으로 적은 disk block만 읽어도 된다 (리프노드를 제외하고 데이터를 담아두지 않기 때문) ⟹ 성능 개선 leaf node는 linked list로 연결되어있다 B-Tree 가.. [자료구조] Binary Tree Binary Tree 모든 노드가 최대 2개의 자식노드를 가질 수 있는 트리 자료구조 여러 종류의 binary tree에 대해 알아보자 ! Full Binary Tree : 정이진트리 모든 노드가 0개 혹은 2개의 자식노드를 가지고 있는 이진트리 L = B + 1 L = leaf nodes, B = branch(non leaf) nodes Complete Binary Tree : 완전이진트리 왼쪽부터 차례대로 채워져있는 이진트리 모든 자식 노드가 채워질 경우 포화이진트리 가 된다 cf. 부모 노드가 항상 자식 노드보다 작은 형태의 완전 이진 트리가 최소 Heap 이다. Perfect Binary Tree : 포화이진트리 모든 branch node가 2개의 자식노드를 가지고 있고, 모든 leaf 노드가 같.. 이전 1 2 3 다음
