배열의 특징 배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다. 프로그래밍 언어에서 동일 데이터 타입을 저장 하며, 다른 타입의 요소를 저장할 수 없다. 배열을 구성하는 각각의 값을 요소(element), 배열에서 위치를 가리키는 숫자를 인덱스(index)라고 한다. 배열의 시간 복잡도 Operation average case worst case 읽기(read) O(1) O(1) 삽입(insert) O(n) O(n) 삭제(delete) O(n) O(n) 탐색(search) O(n) O(n) 시간 복잡도의 특징은 항상 최악의 상황을 고려한다. 읽기의 시간복잡도는 특정 인덱스로 바로 접근이 가능하기 때문에 O(1)이다. 삽입의 시간 복잡도는 원하는 인덱스에 삽입, 그 이후의 인덱스는 오른쪽 한칸..
자료구조
스택(Stack)과 큐(Queue) 스택과 큐는 제약을 갖는 배열이다. 제약하는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있으며 문제를 해결하는 새로운 사고방식을 제공한다. 또한, 제약을 제대로 이해해서 작성한 코드는 다른 개발자에게 익숙하고 명쾌하게 읽힌다. 그 알고리즘이 그러한 제약을 가진 채로 동작함을 알게 된다. 스택(Stack) 스택 연산을 묘사하자면 (Last In, First Out) 후입선출을 뜻한다. 처음 들어간 원소가 마지막에 나온다. 스택은 다음과 같은 세 가지 제약이 있다. 데이터는 스택의 끝에만 삽입 가능 데이터는 스택의 끝에서만 삭제 가능 스택의 마지막 원소만 읽을 수 있음 또 한, 스택의 특징은 스택의 끝을 top 스택의 시작을 bottom 스택의 top에서 원소를 제거하..
해시 테이블(hash table) 대부분의 프로그래밍 언어는 해시 테이블(hash table)이라는 자료 구조를 포함한다. 빠른 읽기라는 놀랍고 엄청난 장점이 있고, 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다. 다음은 해시 테이블을 사용해 파이썬으로 구현한 메뉴이다. (파이썬에서는 딕셔너리라 부른다.) menu = { "one" : 1, "two" : 2, "three" : 3, "four" : 4, "five" : 5 } 쌍으로 이루어져 있으며, 첫번째 항목을 키(key)라 부르고, 두 번째 항목을 값(value)이라 부른다. 파이썬에서는 다음과 같은 문법으로 키의 값을 룩업할 수 있다. print(menu["two"]) # 2 해시 테이블의 값 룩업은 딱 한단계만 걸리므로 평균적..
이전에는 효율성이 O(N2)인 데이터 정렬 알고리즘인 버블 정렬(bubble sort)을 살펴보았다. 이번에는 선택 정렬(selection sort)라는 다른 정렬 알고리즘을 알아보고 버블 정렬과 효율성을 비교해 보겠다. 선택 정렬의 루프를 알아보자. 먼저 인덱스 0에 들어 있는 값을 확인하며 시작하여 최솟값으로 지정한 후, 다음 인덱스와 비교한 다음 최솟값을 결정한다. loop1 min_Index = 0 (값 = 5) [5, 3, 2, 1, 4] 인덱스 0과 1의 비교 min_Index = 1 (값 = 3) [5, 3, 2, 1, 4] 인덱스 1과 2의 비교 min_Index = 3 (값 = 2) [5, 3, 2, 6, 4] 인덱스 2과 3의 비교 min_Index = 3 (값 = 2) [5, 3, 2..
