자료구조

재귀 호출 factorial() 함수는 n - 1의 팩토리얼 값을 구하기 위해 다시 자신과 똑같은 factorial() 함수를 호출하는데 이를 함수의 재귀 호출이라 합니다. ▶ 파이썬에서는 math 모듈에서 정수 x의 팩토리얼 값을 구하는 factorial() 함수를 제공합니다. math.factorial(x) 직접 재귀 vs 간접 재귀 ① 직접 재귀: factorial() 함수처럼 자신과 똑같은 함수를 호출하는 방식 ② 간접 재귀: a() 함수가 b() 함수를 호출하고 다시 b() 함수가 a() 함수를 호출하는 구조 유클리드 호제법 두 정수 x와 y의 최대 공약수를 구하는 문제로, 큰 값을 작은 값으로 나누어 떨어지면 작은 값이 되지만, 나누어 떨어지지 않으면 작은 값과 나머지에 대해 같은 과정을 나누..

큐? 큐는 선입 선출구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입 선출구조입니다. 큐에 데이터를 추가하는 작업을 enqueue, 데이터를 꺼내는 작업을 dequeue, 데이터를 꺼내는 쪽을 front, 데이터를 넣는 쪽을 rear라고 합니다. 배열로 큐 구현하기 1. enqueue 데이터 x를 enqueue하려면 배열 que의 마지막 원소의 인덱스인 idx의 다음 인덱스인 idx + 1에 추가합니다. que[idx + 1] = x 이때 처리의 복잡도는 O(1)이고, 비교적 적은 비용으로 구현할 수 있습니다. 2. dequeue 데이터 y를 dequeue하려면 배열 que의 0번째 원소를 꺼내고, 이후의 원소들을 앞쪽으로 옮겨야 합니다. 이때의 처리 복잡도는 O(n)으로, 데이터를 꺼낼 때마다 ..

스택이란? 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식입니다. PUSH로 데이터를 스택에 넣고, POP을 통해 데이터를 스택에서 꺼냅니다. 스택 구현하기 1. 스택 초기화 스택 배열 stk는 푸시한 데이터를 저장하는 스택 본체인 리스트형 배열입니다. 인덱스가 0인 원소를 스택의 바닥이라고 하며, 데이터가 스택에 추가되는 PUSH 작업이 수행되면 stk[0]에 저장됩니다. 그렇다면 고정 길이의 스택 stk 배열을 구현할 때 어떤 인자를 전달해야할까요? 바로 스택의 최대 크기를 나타내는 capacity와 현재 스택에 쌓여 있는 데이터의 개수를 나타내는 stack pointer입니다. 그렇다면 고정길이 스택 클래스인 FixedStack의 init 메서드를..

배경 예를 들어 배열 x의 원소 수가 13이고, 그 안에 오름차순으로 정렬된 10개의 데이터가 저장되어 있다고 가정해보겠습니다. [5, 6, 14, 20, 29, 34, 37, 51, 69, 75] 이 배열에서 35를 추가한다면 과정은 다음과 같습니다. ① x[5], x[6] 사이에 값이 추가되도록 이진 검색법으로 검사 ② x[6] 이후의 모든 원소를 한 칸씩 뒤로 이동 ③ x[6]에 35 대입 원소가 이동하는데 필요한 복잡도는 O(n)이고, 비효율적입니다. 해시법 해시법은 해시값을 통해 추가·삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행하는 알고리즘입니다. 해시값은 배열의 원소들을 총 원소 개수로 나눈 나머지입니다. 이 해시값은 데이터에 접근할 때 기준이 됩니다. 위 예시라면 배열 x의 ..

이진 검색 배열의 데이터가 정렬 되었을 때 배열의 첫번째 원소부터 하나씩 스캔하는 선형 검색보다 빠르게 검색할 수 있는 알고리즘입니다. 즉, 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있습니다. n개의 원소가 오름차순으로 정렬된 배열 seq에서 이진 검색하는 알고리즘은 검색 범위의 맨 앞(pl), 맨 끝(pr), 중앙의 인덱스(pc)를 활용하여 검색합니다. 검색할 키 값이 정렬된 배열의 중앙 값을 기준으로 앞 혹은 뒤인지를 반복문 안에서 인덱스 변수 값을 갱신해나가며 키 값을 찾을 때까지 검색해나가는 것입니다. 예를 들어 seq = [5, 7, 10, 12, 14, 16, 20] 배열에서 이진 검색 알고리즘을 토대로 키 값 16을 검색하겠습니다. 이때 pl = 0, pr..

검색 알고리즘 검색은 어떤 조건을 만족하는 데이터를 찾아내는 과정입니다. 알고리즘에는 배열 검색, 연결 리스트 검색, 이진 검색 트리 검색 등 다양한 검색 알고리즘이 있습니다. 선택할 수 있는 알고리즘은 다양하지만, 단순히 계산 시간이 빠르다고 해서 좋은 알고리즘은 아닙니다. 검색 처리 시간뿐만 아니라 데이터의 추가·삭제 등 이외 작업들에 대한 비용을 종합 평가하여 적절한 알고리즘을 선택해야합니다. 하여 이번 포스팅에서는 구체적으로 다음 세 가지 배열 검색 알고리즘 중 선형 검색 알고리즘에 대해 공부하고자 합니다. ① 선형 검색: 무작위로 늘어놓은(원소의 값이 정렬되지 않은) 데이터 집합에서 검색을 수행 ② 이진 검색: 일정한 규칙으로 늘어놓은(원소의 값이 정렬된) 데이터 집합에서 아주 빠른 검색 수행 ..