JINHEE's lab

스택(Stack)과 큐(Queue)는 컴퓨터 과학에서 가장 기본적인 자료 구조 중 하나입니다.

스택은 LIFO(Last-In-First-Out) 원칙에 따라 데이터를 저장하는 자료 구조입니다. 새로운 데이터는 스택의 가장 상단에 추가되며, 데이터를 꺼낼 때에는 가장 상단에 있는 데이터부터 차례대로 꺼내야 합니다. 

큐는 FIFO(First-In-First-Out) 원칙에 따라 데이터를 저장하는 자료 구조입니다. 새로운 데이터는 큐의 가장 뒤에 추가되며, 데이터를 꺼낼 때에는 가장 앞쪽에 있는 데이터부터 차례대로 꺼내야 합니다. 이러한 특성 때문에, 큐는 주로 작업 대기열(job queue) 등에 활용됩니다.

스택과 큐는 각각의 특성 때문에 다양한 알고리즘과 데이터 구조에서 중요한 역할을 합니다. 스택과 큐는 둘 다 리스트와 같은 데이터 구조를 기반으로 하며, 파이썬에서는 리스트를 이용하여 스택과 큐를 구현할 수 있습니다.

Big-O 표기법?

-알고리즘 성능을 수학적으로 표기해주는 표기법

-알고리즘의 시간복잡도(필요한 시간)와 공간복잡도(필요한 메모리)를 표현할 수 있게 해줌

-알고리즘의 실제 러닝 타임을 표시한다기 보다 데이터나 사용자의 증가율에 따른 알고리즘의 성능 예측이 목표

Big-O의 시간복잡도 관련 표기법

• O(1): 입력 크기에 관계없이 알고리즘의 수행 시간이 일정한 상수 시간을 가지는 것을 나타냅니다. (예: 배열에서 인덱스를 사용하여 특정 값을 찾는 경우)
• O(log n): 입력 크기가 늘어날 때마다 수행 시간이 로그 함수의 증가율로 증가하는 것을 나타냅니다. (예: 이진 검색 알고리즘)
• O(n): 입력 크기에 비례하여 알고리즘의 수행 시간이 증가하는 것을 나타냅니다. (예: 배열에서 최대값을 찾는 경우)
• O(n log n): 입력 크기가 늘어날 때마다 수행 시간이 n과 로그 n의 곱으로 증가하는 것을 나타냅니다. (예: 병합 정렬 알고리즘)
• O(n^2): 입력 크기의 제곱에 비례하여 알고리즘의 수행 시간이 증가하는 것을 나타냅니다. (예: 버블 정렬 알고리즘)
• O(2^n): 입력 크기가 1 증가할 때마다 수행 시간이 2배

Big-O의 공간복잡도 관련 표기법

• O(1): 알고리즘이 고정된 메모리 양을 사용하는 경우 (예: 상수 개수의 변수를 사용하는 경우)
• O(n): 알고리즘이 입력 크기와 비례하는 메모리 양을 사용하는 경우 (예: 입력 배열을 저장하는 경우)
• O(n^2): 알고리즘이 입력 크기의 제곱과 비례하는 메모리 양을 사용하는 경우 (예: 2차원 배열을 사용하는 경우)
• O(log n): 알고리즘이 입력 크기에 로그 함수의 증가율과 비례하는 메모리 양을 사용하는 경우 (예: 이진 트리를 사용하는 경우)

그러나 실제로는 Big-O를 사용하여 알고리즘의 성능을 평가하기보다는 실제로 알고리즘을 실행하여 성능을 측정하는 것이 더욱 정확하다.

로그 함수는 어떤 수를 다른 수의 거듭제곱으로 나타내는 함수입니다. 예를 들어, 2를 몇 번 거듭제곱해야 8이 되는지를 구할 때, log₂ 8을 계산하면 됩니다. 이 때, 밑이 2인 로그 함수를 사용한 것입니다.