정렬 방식 자주 사용하는 정렬 방식은 크게 2가지로 나눌 수 있다. 첫 번째로 2중 반복문을 사용하는 Bubble, Select, Insert 정렬이다. 두 번째는 분할-정복 방법을 사용하는 병합, 퀵 정렬이다. 2중 반복문을 사용하는 정렬 방식 해당 방식은 최악의 경우 시간복잡도는 O(N^2)이 된다. 이와 같은 이유는 2개의 반복문을 통해 값을 비교하기 때문이다. Bubble Sort 서로 인접한 두 원소를 검사하여 정렬하는 방식을 사용한다. swap이 더 이상 발생하지 않으면, 중단하여 불필요한 반복문을 실행하지 않을 수 있다. def bubble_sort(nums): for i in range(len(nums)): swap = False for j in range(1, len(nums)): if ..
알고리즘: DFS와 BFS
그래프 탐색 방법 그래프를 탐색하는 방법중 DFS(Depth First Search와 BFS(Breadth First Search)를 간단한 예시를 통해 이해하고자 한다. 두 방식은 각각 Stack과 Queue를 통해 구현할 수 있으며, 그래프 방문 여부를 체크하여 중복으로 탐색하는 것을 방지하여야 한다. 그래프를 코드로 나타내기 그림 1의 그래프에 대한 노드 정보를 코드로 나타내면 다음과 같다. graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'E', 'F'], 'D': ['B', 'G'], 'E': ['C', 'H'], 'F': ['C'], 'G': ['D'], 'H': ['E'], } DFS 그림 2는 루트 노드를 시작으로 모든 그래프 경로를 탐색하..
알고리즘: Recursion
Recursion? 재귀는 특정 함수 내에서 함수 자신을 다시 호출하는 것을 의미한다. 재귀는 Stack의 특성을 그대로 반영하여, 가장 최근에 호출된 함수 부터 처리되는 방식으로 진행된다. 재귀를 잘 다룰 수 있다면 DFS와 백트래킹, 트리 탐색과 같은 문제를 해결 할때 효율적으로 접근할 수 있게 된다. 이진 트리 순회 그림 1과 같은 이진 트리가 있을 경우, 3가지 방식으로 트리를 순회할 수 있다. 첫 번째는 전위 순회로 1-2-4-5-3-6-7 순서로 트리를 순회한다. 두 번째는 중위 순회로 4-2-5-1-6-3-7 순서로 트리를 순회 한다. 마지막으로 후위순회는 4-5-2-6-7-3-1로 순회한다. 트리를 순회하는 것은 재귀 호출을 통해서 구현 할 수 있다. Simple Tree Travel de..
Linked List? 단순한 선형 배열(리스트)을 선언하면 메모리를 연속적으로 할당한다. 만약, 배열 내의 값 삭제가 필요하거나 추가가 필요한 경우 값들의 자리 교체가 필요하다. 이와 달리 연결 리스트는 연속적인 공간을 사용하지 않고, 각각의 노드들을 연결한 구조로 연결되어 중간의 값 삭제가 빈번하게 일어나는 자료를 관리하기에 보다 효율적이다. Single Linked List class Node: def __init__(self, data): self.data = data self.next = None class SingleLinkedList: def __init__(self, data): self.head = Node(data) def add(self, data): node = self.head w..
