구르미의 개발 이야기 구르미의 개발 이야기

CH 05 큐(Queue)목표 자료구조 큐에 대해 알아보고, C/C++ 프로그래밍 언어로 구현해봄으로써 큐의 대한 이해의 깊이를 늘려보세요! 목차1. 큐란 무엇인가? 2. 큐 ADT 3. C로 구현하기 4. C++로 바꿔보기 5. 결론 1. 큐란 무엇인가? 큐란 마치, 순서가 있는 대기열 같습니다. 그림처럼 은행의 대기열이 있다고 합시다. 당연히 먼저 온 사람이 먼저 나가게 되겠죠? 이것이 바로 큐입니다. 유식한 말로는 FIFO(First In First Out) 구조라고 하지요. 이번 시간에 우리가 구현할 큐는 배열 기반의 원형 큐입니다. 본격적으로 코드를 구현하기 전에 원형 큐가 무엇인지 살펴보도록 하죠.일반 배열로 큐를 구현했을 때, 우리가 가질 수 있는 문제점 중 하나는, 큐가 꽉차면, 재활용이 ..

CH 04 스택(Stack)목표자료구조 스택에 대해 알아보고, C/C++ 프로그래밍 언어로 구현해봄으로써 스택의 이해의 깊이를 늘려보세요 목차1. 스택이란 무엇인가? 2. 스택 ADT 3. C로 구현하기 4. C++로 바꿔보기 5. 결론 1. 스택이란 무엇인가? 스택이란 마치, 프링글스 통과 같습니다. 그림처럼, 프링글스는 맨 위의 과자를 꺼내지 않는한, 그 밑의 과자는 먹을 수가 없지요. 즉, 가장 나중에 들어온 과자가 가장 먼저 나가게 됩니다. 이를 LIFO (Last In First Out) 구조라고 합니다. 바꿔서 스택이란 자료구조라도 말합니다. 자 지금부터 본격적으로 스택에 대해 알아봅시다. 2. 스택 ADT 스택의 ADT는 다음과 같습니다. ADT Stackcharacters:arr: T[]데..

[알고스팟] 조세푸스 문제(JOSEPHUS)목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 조세푸스 문제(JOSEPHUS)를 풀어보자문제 URL풀이조세푸스 문제는 대표적인 큐 시뮬레이션 문제입니다. 먼저 첫 번째 예제를 살펴보도록 할까요? N = 6, K = 3 병사들은 1~6번까지, 원 형태로 앉아 있습니다. 이제 1번부터 2명이 남을 때까지 차례대로 죽여 나갈 건데, 아래 표에서 죽인다면, X를 표시해보도록 하지요. 또한, O는 죽어야 하는 놈을 가리키는 인덱스라고 하겠습니다. 1명 쨰, | 1 | 2 | 3 | 4 | 5 | 6 | | X | | | | | | | O | | | | | | 1번은 안타깝게도 묻지도 따지지도 않고 죽여야 합니다. 2명 째, | 1 | 2 | 3 | 4 | ..

[알고스팟] 짝이 맞지 않은 괄호(BRACKETS2)목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 "짝이 맞지 않는 괄호"를 풀어보자문제 URL풀이"짝이 맞지 않은 괄호" 같은 문제는 스택을 이용하는 대표적인 알고리즘 문제입니다. 이 문제의 경우 다음의 조건을 검사해야 합니다. 모든 괄호는 쌍이 맞아야 한다.모든 괄호는 먼저 열리고 그 후에 닫혀야 한다.어떠한 쌍도 교차될 수 없다. (ex : "({)}" ) 이 문제 역시 스위핑 알고리즘을 기반으로 짭니다. 문제의 핵심은 닫히는 괄호가 나올때 짝이 맞는 열리는 괄호가 있는가입니다. 알고리즘의 가장 큰 줄기는 다음과 같습니다. 입력 문자열을 다음과 같이 순회합니다.현재 문자가 괄호를 여는 문자들 "(", "{", "[" 중 하나라면, 스택에..

[알고스팟] 울타리 쳐내기(FENCE)목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 "울타리 쳐내기"를 풀어보자문제 URL풀이이 문제를 푸는 열쇠는 스택과 스위핑 알고리즘입니다. 스위핑 알고리즘이란 간단히 말해서 이미 연산이 진행된 이전 공간에 대해서는 연산을 하지 않는다라고 생각하시면 됩니다. 개념 자체는 쉽습니다만... 굉장히 생각하기 어렵다는게 함정입니다. 이 문제를 예를 들어 설명하겠습니다. 이 문제에서 우리가 사각형을 구하기 위해 필요한 정보는 그 사각형의 왼쪽 끝과 오른쪽 끝 그리고 높이입니다. 높이가 오른쪽 끝점의 높이라고 했을 때, 왼쪽으로 연속된 판자들 중 이 높이를 포함하는 가장 낮은 지점이 왼쪽 끝 점이 되겠죠. 이 성질을 이용해서, 문제를 푸는 것이죠. 그래서 어떻게 ..

CH 03 이중 연결 리스트(Double Linked List)목표연결 리스트의 응용 중 하나인 이중 연결 리스트에 대해 알아보고, C/C++ 프로그래밍 언어로 구현해봄으로써 연결 리스트의 이해의 깊이를 늘려보세요!목차이중 연결 리스트란 무엇인가?연결 리스트의 한계이중 연결 리스트에 대해서이중 연결 리스트 ADTC로 구현하기C++로 바꿔보기결론이중 연결 리스트 정리1. 이중 연결 리스트란 무엇인가?연결 리스트의 한계배열의 한계를 뛰어넘기 위해서, 연결 리스트란 자료 구조를 공부하였습니다. 그러나 연결 리스트에도 불편함이 있지요? 무슨 불편함이냐면, 분명히 꼬리 부분 tail 의 위치를 알고 있음에도, 꼬리 삭제 시에 꼬리 이전까지 반복문을 돌아야 했습니다. 이를 개선할 방법이 없을까요?이중 연결 리스트에..

CH 02 연결 리스트(Linked List)목표연결 리스트가 나오게 된 배경과 연결 리스트의 개념에 대해서 알아보고, 연결 리스트의 삽입, 조회, 삭제 연산이 어떻게 동작하는지 이해해 보세요. 그 후 C/C++ 프로그래밍 언어로 구현해봄으로써 한 층 더 자료구조의 이해의 깊이를 늘려보세요!목차연결 리스트란 무엇인가?배열의 한계연결 리스트에 대해서연결 리스트 ADTC로 구현하기C++로 바꿔보기결론연결 리스트 정리연결 리스트 응용1. 연결 리스트란 무엇인가?배열의 한계배열은 충분히 좋은 자료구조입니다. 인덱스를 통해서 조회, 추가, 삭제에 대한 연산이 가능하지요. 하지만, 프로젝트가 커지고 복잡해질수록 배열로는 한계가 있습니다. 제일 큰 한계는 다음과 같습니다.배열은 길이가 정해져 있어야 한다. 즉, 무한..

CH 01 ADT(Abstract Data Type)목표본격적으로 자료구조를 알기 전에, Abstract Data Type(이하 ADT)를 알아봅시다.목차ADT란 무엇인가?지갑을 통한 ADT의 이해ADT는 이렇게 씁시다결론1. ADT란 무엇인가?ADT를 번역하면 추상 자료형이라는 뜻입니다. 이는 구체적인 기능의 완성 과정은 서술하지 않고 오로지 순수하게 기능이 무엇인지만 나열하는 것을 말합니다. 추상 자료형에는 다음의 속성들을 가지고 있습니다.CharactersOpertionsCharacters는 추상 자료형의 내부 속성을 뜻합니다. 예를 들어서, 자동차라는 ADT가 존재한다면, 바퀴, 문, 핸들 등이 바로 이 ADT의 내부 속성입니다. 이들은 객체지향 프로그래밍(이하 OOP)에서 말하는 클래스의 내부 ..