자료구조5 [자료구조] - 덱(deque)의 구조와 원형 덱 구현 1. 덱(deque)이란? 덱(deque)이란, double-ended queue의 줄임말로 큐의 front와 rear에서 삽입과 삭제가 모두 가능한 자료구조이다. 간단히 말해, 양방향 큐라고 볼 수 있다. 2. 덱 구현을 위한 기본 함수 init (dq) - 덱 초기화 is_empty (dq) - 덱이 비어있는지 검사 is_full (dq) - 덱이 꽉 차있는지 검사 add_front (dq, e) - 덱의 맨 앞에 요소를 추가 add_rear (dq, e) - 덱의 맨 뒤에 요소를 추가 delete_front (dq) - 덱의 맨 앞 요소 반환 후 삭제 delete_rear (dq) - 덱의 맨 뒤 요소 반환 후 삭제 pop_front (dq) - 덱의 맨 앞 요소 반환(삭제X) pop_rear (d.. 2024. 1. 5. [자료구조] - 원형큐의 구조와 구현 1. 선형큐의 문제점 앞서 포스팅한 큐 설명 글에서 선형큐에 대한 문제점을 잠깐 언급하였다. 선형큐를 1차원 배열을 이용하여 구현할 경우, front와 rear의 값이 계속 증가만 하므로 언젠가는 배열의 끝에 도달하게 되어 비효율적이다. 이러한 문제는 큐를 구현하는 배열을 선형 말고 원형으로 두면 쉽게 해결할 수 있다. 원형큐의 구조와 구현 방법을 지금부터 알아보자. 2. 원형큐의 구조 원형큐도 선형큐와 마찬가지로 1차원 배열로 구현하는데, front와 rear가 증가만 하는 선형큐와 달리, 원형큐는 front와 rear의 값이 배열의 끝 값인 MAX-1 에 도달하면 그 다음값은 다시 0이 된다. 원형큐에서 front와 rear의 초기값은 둘 다 0이다. front가 큐의 첫번째 요소의 하나 앞을, re.. 2023. 12. 10. [자료구조] - 큐(queue)의 구조, 선형큐 구현하기 1. 큐(queue)란? 큐(queue)라는 단어의 사전적인 뜻을 찾아보면, " (무엇을 기다리는 사람·자동차 등의) 줄" 이다. 계산을 기다리는 사람들의 줄을 생각하면 이해가 쉽다. 선입선출 (FIFO : First - In - First - Out) 스택과 비교되는 큐의 중요한 특징이다. 스택에서는 가장 마지막에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO)의 특징을 가졌다면, 큐는 이와 반대로 먼저 들어온 데이터가 먼저 나가는 구조이다. 즉 큐에서 입력은 뒤쪽에서만 일어나며, 출력은 앞쪽에서만 일어난다. 큐에서 삽입이 일어나는 뒤쪽을 rear(후단), 삭제가 일어나는 앞쪽을 front(전단) 이라고 한다. 2. 선형큐 구현하기 큐도 스택과 같이 1차원 배열로 구현이 가능하다. (물론 다른 방.. 2023. 12. 9. [자료구조] - 스택(Stack)의 구조와 구현 1. 스택(Stack)이란? 스택(stack)이란 단어의 사전적인 뜻은, "쌓아놓은 더미"이다. 쌓아놓은 접시들을 생각하면 이해가 쉬울 것이다. 후입선출 (LIFO : Last - In - First - Out) 스택의 중요한 특징이다. 앞서 말한 접시 더미의 예시처럼, 스택에서는 가장 마지막에 들어온 데이터가 가장 먼저 나간다는 뜻이다. 다시 말해, 스택에서의 입출력은 맨 위에서만 일어난다. (들어올때도 맨 위, 나갈때도 맨 위) 이러한 특징 때문에 스택의 중간에서는 데이터를 삽입하거나 삭제할 수 없다. 2. 스택 구현을 위한 기본 함수 스택은 1차원 배열을 이용하여 간단한 방법으로 구현이 가능하다. 단 1차원 배열을 이용하면 스택의 크기가 고정된다는 단점이 있다. (스택의 크기를 가변적으로 구현하려면.. 2023. 12. 3. [자료구조] - Ch1) 시간복잡도 (Time Complexity) 1. 시간복잡도(Time Complexity)란? 시간복잡도란 간단히 말하자면, 어떠한 알고리즘의 연산 횟수를 수치로 나타낸 것을 말한다. 예를 들어, 어떤 자연수를 n번 더하는 문제를 풀기 위하여 세 가지의 알고리즘을 만들었다고 가정하자. 이처럼 입력의 개수 n에 따라서 변하는 연산의 수행횟수를 n에 대한 함수로 나타낸 것을 시간복잡도 함수라고 말하며, T(n)으로 표기한다. 시간복잡도 표기법은 크게 3가지가 있다. Ο(빅오 표기법) - 함수의 상한 (최악의 경우) Ω(빅오메가 표기법) - 함수의 하한 (최선의 경우) θ (빅세타 표기법) - 함수의 상한과 하한 (평균) 빅오 표기법 (Big-O notation) 빅오 표기법은, 간단히 말해 시간 복잡도의 점근적 상한을 나타낸 것이다. (즉 최악의 상황.. 2023. 12. 1. 이전 1 다음
