본문 바로가기

Algorithm/개념정리

 (7)
Algorithm/개념정리 탐색 알고리즘(Search Algorithm)의 이진 탐색(Binary Search) 개념 정리 이진 탐색 탐색 알고리즘에는 크게 순차(Linear) 탐색과 이진 탐색(Binary Search)으로 구분된다. 순차 탐색은 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이고, 이진 탐색은 정렬되어 있는 리스트에서 시작점, 끝점, 중간점으로 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 예시 이미 정렬된 10개의 데이터 중에서 이진 탐색을 통해 값이 4인 원소를 찾는 과정을 살펴보자. [ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 ]탐색 과정 Step 1 시작점: arr[0], 끝점: arr[9], 중간점: arr[4] (소수점 이하 제거) * * * [ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 ]찾고자 하는 값(4)이 중간점의 값(8..
Algorithm/개념정리 정렬 알고리즘(Sort Algorithm)의 퀵 정렬(Quick Sort) 개념 정리 들어가며 파이썬을 사용하는 경우 정렬해야 하는 상황에서 sort()를 사용하여 내부적인 정렬을 해주거나, sorted()를 사용하여 정렬된 새로운 값을 받도록 하는 경우가 많다. def use_sort(arr: List) -> List: arr.sort() return arr def use_sorted(arr: List) -> List: return sorted(arr) 이러한 정렬 함수가 내부적으로 어떻게 동작하는지 알기 위해서는 적어도 퀵 정렬 또는 병합 정렬 정도는 알고 있어야 한다고 한다. 따라서, 이번에는 퀵 정렬에 대해서 공부한 내용을 정리해보겠다. 퀵 정렬 퀵 정렬(Quick Sort)에서는 중심점(pivot)과 파티션(partition)이라는 개념이 존재하며, 이는 퀵 정렬의 동작 원리이기..
Algorithm/개념정리 자료 구조(Data Structure)의 큐(Queue) 개념 정리 들어가며 지난 포스팅에 이어서 이번에는 큐에 대해 공부한 내용을 정리해보았다. 큐 스택과 달리 큐(queue)는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out) 방식으로 데이터 입/출력을 처리한다. 선입선출은 신선도를 고려한 편의점과 마트의 상품 진열 방식을 생각하면 이해하기 쉽다. 즉, 데이터를 맨 뒤에서 넣고 앞에서 꺼내는데, 이를 각각 인큐(enqueue)와 디큐(dequeue)라고 한다. 이와 같이 큐는 맨끝에서 맨앞으로 데이터를 밀어넣어 꺼내는 방식이며, 큐의 맨 앞의 원소를 프론트(front)라고 하고, 맨 뒤의 원소를 리어(rear)라고 한다. 예를 들어, 인큐와 디큐를 간단히 나타내면 다음과 같다. queue = [] 1. enqueue(1..
Algorithm/개념정리 자료 구조(Data Structure)의 스택(Stack) 개념 정리 들어가며 알고리즘 문제를 풀 때 리스트(이하, 배열)로는 해결하기 어려운 경우가 있으며, 이와 같은 상황에서는 스택이나 큐를 사용해야 한다. 따라서, 이번에는 스택에 대해서 공부한 내용을 정리해보았다. 스택 스택(stack)은 '마룬 풀을 쌓은 더미', '겹겹이 쌓음'을 뜻하는 단어로, 데이터가 쌓인 데이터 집합이라고 할 수 있다. 이는 데이터를 임시 저장할 때 사용하는 자료구조이며, 후입선출(LIFO, Last In First Out) 방식으로 데이터를 입/출력할 수 있다. 즉, 데이터를 맨 위에서부터 쌓고, 맨 위에서부터 꺼낸다는 의미이며, 이를 각각 푸쉬(push), 팝(pop)이라고 한다. 예를 들어, 푸쉬와 팝을 간단히 나타내면 다음과 같다. stack : [] 1. push(1) → stack..
Algorithm/개념정리 검색 알고리즘(Search Algorithm)의 해시법(체인법과 오픈 주소법) 개념 정리 들어가며 해시법에 대해 다루기 전에 한 가지 경우를 살펴보도록 하자. 만약, 아래와 같은 배열에서 a[2]에 새로운 원소 6를 추가하는 경우, 일반적인 배열에서의 처리 과정은 다음과 같을 것이다. a = [1, 7, 10, 13, 16, 22] a[0](=1)와 a[1](=7)사이에 새로운 값이 추가될 수 있도록 이진 검색으로 검색 a[0](=1) 이후의 모든 원소를 한 칸씩 뒤로 이동 a[1](=None)에 새로운 원소 6을 대입 이와 같이 데이터 추가 또는 삭제 시 배열의 원소가 이동하는데 필요한 복잡도는 O(n)이고, 이는 배열의 크기가 커짐에 따라 그 비용 또한 커질 수 밖에 없다는 것을 의미한다. 해시법 해시법은 간단한 연산을 통해 데이터 저장 위치 = 인덱스를 구하는 방법으로, 데이터 검색 뿐..
Algorithm/개념정리 검색 알고리즘(Search Algorithm)의 선형 검색과 이진 검색 개념 정리 들어가며 어떠한 데이터 집합에서 원하는 값의 원소를 찾아내는 것을 검색이라고 하고, 이를 알고리즘으로 구현한 것이 바로 검색 알고리즘이다. 예를 들어, 우리가 주소록에서 누군가를 검색한다고 가정했을 때 다음과 같은 다양한 조건으로 검색할 수 있다. 성별이 남자인 사람 나이가 20세 이상인 사람 이름에 '영'자가 포함된 사람 위 검색 조건은 성별, 나이, 이름과 같이 특정 항목에 주목하고 있는데, 검색 알고리즘에서는 이를 키(key)라고 하며, 이는 대부분 데이터의 일부이다. 성별 : key와 일치하도록 지정 나이 : key가 포함되도록 범위 지정 이름 : key에 가깝도록 지정 가장 대표적인 검색 알고리즘으로는 배열 검색, 연결 리스트 검색, 이진 트리 검색이 있으나, 본 글에서는 배열 검색에 대해서만 ..
Algorithm/개념정리 [자료구조] 이진트리(Binary Tree) 생성 개념 정리 들어가며 사이버 대학교 특성 상 직장을 다니면서 자유롭게 학습할 수 있는 환경을 제공해준다. 그러나, 직장에서 야근, 주말 출근이 잦은 경우에는 출석체크 정도만 할 수 있고, 제대로 된 공부를 할 수 없다는 큰 단점이 있다. 필자 또한 약 2년 6개월 간의 직장생활을 하는 동안 잦은 야근, 거의 매주 출근으로 인해 시험을 보기 위한 벼락치기 외에는 제대로 된 학습을 수행하지 못했다. 현재는 퇴사하고 시간이 남아돌아서 토이 프로젝트를 하며, 공부하던 중 이진트리에 대해 제대로 학습하자는 취지로 본 글을 작성하였다. 1. 이진트리 이진트리에 대한 정의는 구글에 검색하면 긴 글과 다양한 전문 용어로 잘 나와있기 대문에 따로 언급하지 않겠으나, 쉽게 말하자면 아래 그림과 같이 크게 두 갈래로 나뉜 트리라고 할 ..

티스토리툴바