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/개념정리
자료 구조(Data Structure)의 스택(Stack) 개념 정리
들어가며 알고리즘 문제를 풀 때 리스트(이하, 배열)로는 해결하기 어려운 경우가 있으며, 이와 같은 상황에서는 스택이나 큐를 사용해야 한다. 따라서, 이번에는 스택에 대해서 공부한 내용을 정리해보았다. 스택 스택(stack)은 '마룬 풀을 쌓은 더미', '겹겹이 쌓음'을 뜻하는 단어로, 데이터가 쌓인 데이터 집합이라고 할 수 있다. 이는 데이터를 임시 저장할 때 사용하는 자료구조이며, 후입선출(LIFO, Last In First Out) 방식으로 데이터를 입/출력할 수 있다. 즉, 데이터를 맨 위에서부터 쌓고, 맨 위에서부터 꺼낸다는 의미이며, 이를 각각 푸쉬(push), 팝(pop)이라고 한다. 예를 들어, 푸쉬와 팝을 간단히 나타내면 다음과 같다. stack : [] 1. push(1) → stack..