전체 글

스택(Stack)과 큐(Queue) 스택과 큐는 제약을 갖는 배열이다. 제약하는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있으며 문제를 해결하는 새로운 사고방식을 제공한다. 또한, 제약을 제대로 이해해서 작성한 코드는 다른 개발자에게 익숙하고 명쾌하게 읽힌다. 그 알고리즘이 그러한 제약을 가진 채로 동작함을 알게 된다. 스택(Stack) 스택 연산을 묘사하자면 (Last In, First Out) 후입선출을 뜻한다. 처음 들어간 원소가 마지막에 나온다. 스택은 다음과 같은 세 가지 제약이 있다. 데이터는 스택의 끝에만 삽입 가능 데이터는 스택의 끝에서만 삭제 가능 스택의 마지막 원소만 읽을 수 있음 또 한, 스택의 특징은 스택의 끝을 top 스택의 시작을 bottom 스택의 top에서 원소를 제거하..

문제 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 도현이는 앞으로 M번 바구니의 순서를 회전시키려고 만들려고 한다. 도현이는 바구니의 순서를 회전시킬 때, 순서를 회전시킬 범위를 정하고, 그 범위 안에서 기준이 될 바구니를 선택한다. 도현이가 선택한 바구니의 범위가 begin, end이고, 기준이 되는 바구니를 mid라고 했을 때, begin, begin+1, ..., mid-1, mid, mid+1, ..., end-1, end 순서로 되어있는 바구니의 순서를 mid, mid+1, ....

해시 테이블(hash table) 대부분의 프로그래밍 언어는 해시 테이블(hash table)이라는 자료 구조를 포함한다. 빠른 읽기라는 놀랍고 엄청난 장점이 있고, 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다. 다음은 해시 테이블을 사용해 파이썬으로 구현한 메뉴이다. (파이썬에서는 딕셔너리라 부른다.) menu = { "one" : 1, "two" : 2, "three" : 3, "four" : 4, "five" : 5 } 쌍으로 이루어져 있으며, 첫번째 항목을 키(key)라 부르고, 두 번째 항목을 값(value)이라 부른다. 파이썬에서는 다음과 같은 문법으로 키의 값을 룩업할 수 있다. print(menu["two"]) # 2 해시 테이블의 값 룩업은 딱 한단계만 걸리므로 평균적..

이전의 포스팅에서 버블 정렬과 선택 정렬을 알아보았는데, 둘 다 효율성은 O(N2)이지만 선택 정렬이 실제로는 두배 더 빠르다는 것을 알 수 있었다. 이번에는 삽입 정렬(insertion sort)을 배우면서 최악의 경우가 아닌 다른 시나리오를 분석하는 것에 중점을 두고 어떠한 장점이 있는지 알아 보겠다. 삽입 정렬의 수행 순서 삽입 정렬을 수행 할 배열은 [2, 4, 7, 1, 3] 이다. 먼저 loop1이다. 먼저 인덱스 1의 값을 확인한다. 임시로 인덱스1(값2)를 삭제한 후 temp_value 변수에 저장한다 인덱스 - 1(값4)와 비교한다. 4가 2보다 크므로 4를 오른쪽으로 쉬프트 한다. 더이상 비교할 인덱스가 없으므로 temp_value를 -1인덱스에 삽입한다. 첫번쨰 루프의 결과는 [2, ..