지난 글에서 Linked List 의 개념과 그 구현에 대해 정리하였다. 이번에는 Array 로 구현했던 Stack 과 Queue를 Linked List 로 구현하는 과정을 살펴보고자 한다. Stack With Linked List 스택을 연결리스트로 구현해보자. 연결리스트에서 데이터를 중간에 삽입할 때는 이전 노드의 주소를 알아야 하기 때문에 아주 복잡했다. 데이터를 맨 처음에 삽입하는 것이 아주 간단하기 때문에, 스택의 데이터 삽입과 삭제가 빈번히 일어나는 top 을 연결리스트의 첫 head로 설정하자. 그림으로 나타내면 이렇게 나타난다. 스택에 데이터를 추가하면 추가된 데이터를 top 이 가리키고, 추가된 데이터가 기존 데이터를 가리키는 방식으로 구현하면 된다. 스택에서 데이터를 뺄 때는 top 의..
지난 포스팅에서는 배열을 이용한 큐를 구현해보았다. front, back 변수를 모두 0으로 초기화 하였을 때, push: back 변수가 가리키는 인덱스에 데이터 추가, back >= size 이면 오버플로우 pop: front 변수가 가리키는 인덱스의 데이터를 제거, front >= back 이면 언더플로우 와 같이 구현할 수 있었다. 그러나 이렇게 구현하면 push 를 최대 N번, pop은 push 횟수 이하로만 할 수 있다는 문제가 있었다. 이번에는 Size N 이라는 메모리 공간에 중간중간 여유가 생긴다면 그 여유공간까지 활용하여 push 를 더 많이 할 수 있도록 기존의 큐를 개선하여 보겠다. 그림과 같이 사이즈 5인 큐에 모든 값이 다 들어있는 상황을 생각해보자. 현재 front 는 2이고,..
이번에는 큐를 배열을 통해 구현하는 과정을 정리하고자 한다. 구현에 앞서 '큐'의 개념을 살펴보자. 큐의 개념 이번에도 구글 번역기로한번 번역부터 해 보았다. 이번에는 번역기가 번역을 해준다! 번역의 결과가 큐를 말 그대로 설명해주고 있다. 큐는 '대기줄' 이다. 대기줄의 특성을 생각해보자. 식당에 (학교에서는 교수님이 '하카타분코' 라는 라멘집을 예시로 들어주신다 ㅋㅋ) 손님이 많아서 대기줄이 길게 있다고 할 때, 신규로 오는 손님은 대기줄의 '뒤'에 서게 되고, (push) 식당에 빈자리가 생기면 대기줄 맨 앞에 있던 사람이 들어가게 된다. (pop) 큐는 이를 그대로 표방하는 자료구조이다. 먼저 들어왔던 데이터가 먼저 나가는 First In First Out (FIFO) 방식의 자료구조이다. 큐는 ..
Stack ( 스택 ) 이란 스택이라는 자료구조는 매우 직관적으로 이해할 수 있는 자료구조이다. 스택이라는 말 자체가 이미 이 자료구조에 대해 모든 걸 설명하고 있다. 보통 스택이라고 하면 어떤 것들이 쌓여있는 형태를 의미하는데, 스택이라는 자료구조도 무언가를 쌓는 형태를 자료구조화 한 것이다. 가령 책이 한 무더기 쌓여있다고 해보자. 중간에 있는 원하는 책을 찾아 꺼내려면 어떻게 해야할까? 가장 당연하게 떠오르는 방법은 맨 위에 있는 책부터 하나씩 하나씩 확인하면서 찾을 것이다. 중간 어디에 있는지도 모르는데 책을 무더기로 들춰가면서 찾는 것은 너무 힘들지 않을까 그 책 무더기에 새로운 책을 여러권 놓는다고 해보자. 그러면 가장 먼저 놓은 책이 제일 밑에 놓이고, 가장 나중에 놓은 책이 맨 위에 놓이는..
3글자의 알파벳으로 이루어진 이름과, 4글자의 숫자로 이루어진 번호 쌍을 저장하는 주소록 프로그램이 있다고 해보자. 이 프로그램에서 이름과 번호쌍을 어떻게 관리할 수 있을까? 대부분의 언어에서 기본으로 제공하는 '배열' 자료구조를 이용하여 구현한다면 아래와 같이 구현할 수 있을 것이다. 1. 두 배열을 이용하여 데이터를 저장하기 첫 번째 방법은 두 배열을 이용해서 이름과 번호를 저장하는 방법이 있다. 이름과 번호를 연결짓는 기준은 '배열의 인덱스' 가 된다. 이렇게 저장한 자료에서 이름을 기준으로 번호를 찾는다고 하면 아래와 같이 코드를 짤 수 있다. #include char name[10][3]; char number[10][4]; char find_name[3]; int main() { printf(..
https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 개인적으로 플레 난이도 치고는 풀만한 문제라고 생각한다. 중복되는 키가 연속으로 들어오는 경우를 체크하는게 고민 포인트. 내가 푼 알고리즘은 다음과 같다. 0. 맨 처음에 들어오는 키는 그냥 스택에 넣는다. 1. 수를 입력받으면 해당 수와 스택의 탑에 있는 값을 비교한다. 1.1 탑에 있는 값 > 새로 들어온 값 인 경우 (키가 감소) 탑에 있는 값과 새로 들어온 값이 서로..
https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 난이도가 조금 있는 스택문제 알고리즘 분류가 스택이라는 것만 알아내면 아이디어가 어렵다기 보다는 구현이 조금 복잡하다고 생각한다. 오등큰수를 결정하는 제일 큰 기준은 '숫자의 등장 횟수' 이다. 따라서 숫자의 등장횟수를 미리 다 저장해둔다. 주어진 수열의 왼쪽부터 차례대로 순회하면서 해당 숫자의 등장 횟수를 스택에 저장해나가다 스택의 가장 위에 있는 수의 등장횟수보다 더 많은 등장횟수를 가진 수가 나타나면 그..
