F.R.I.D.A.Y.

학교 과제. 주변에 동기를 보면 힘들어하는 것 같아서.. 문제 사항 매 학기 같은 문제를 낼거라고 생각하지 않으니까..^^ - 이번 과제에서는 B-Tree 구조를 활용해 set 클래스 템플릿을 구현해야합니다. 그리고 set 클래스에는 총 세 개의 public 멤버 함수만 존재할 수 있습니다. > count, insert, erase - set 클래스에는 아래의 함수가 선언 및 정의되어야합니다. > count, insert, loose_insert, fix_excess, erase, loose_erase, fix_shortage, remove_biggest - 추가로, `show_contents`라는 이름의 public 멤버 함수를 선언 및 정의합니다. 이 함수는 여러분 set 클래스의 B-tree 구조로..

먼저 들어온 데이터가 먼저 나오는 선입선출 구조 물건을 구매한다고 가정하면, 먼저 계산대에 줄을 선 사람이 물건 계산을 하는 것이 지당한 이야기다. 이렇게 먼저 들어온 데이터가 먼저 나가도록 하는 구조를 프로그램에서도 적용이 가능한데, 이 기능을 위해 Queue를 이용할 수 있다. 큐 데이터 구조를 말하라고 하면 스택과 함께 먼저 거론되는 자료형이 아닐까 싶다. 큐는 스택과 같이 두 가지 필수 함수가 구성되어야 한다. push pop 구현 큐는 크게 두 가지 방법으로 구현을 할 수 있다. 배열을 이용하는 방법과 연결리스트를 이용하는 방법이 있는데, 둘 모두 장단점이 있다. 배열을 활용한 구현 배열 구현은 구현 자체가 간단하다는 장점이 있다. 다만 이는 재사용성을 생각하지 않을 때의 경우이고, 이미 사용한..

처음 들어간 데이터가 가장 마지막으로 출력되는 자료구조 자료구조를 따지면 가장 먼저 나오는 구조라고 불러도 이상하지 않을만큼 익숙한 자료구조이다. 스택 Last In First Out이란 단어로 설명이 가능하겠다. 스택은 두 개의 필수 명령이 있다. push pop 입력을 할 때[# 스택에 값을 넣을 때]는 push, 출력할 때[# 스택에서 값을 뺄 때]는 pop으로, 이 명령을 이용해 다음과 같은 작업을 수행한다고 가정하면 push 1 push 5 push 3 pop push 5 push 7 pop 스택은 다음과 같은 순서로 데이터를 관리한다. 구현 기본적으로 스택은 배열을 이용하며, 배열을 어떻게 이용하는가에 대한 방식을 설명한다고 볼 수 있다. 다음은 C++에서 스택을 구현한 클래스 코드이다. 더보..

임의 위치에 데이터를 추가/삭제하는 것이 용이한 연결리스트 생각해보자. 배열에서 임의 위치의 데이터를 삭제하고 빈 공간이 없도록 구성하려면 어떻게 해야할까? 만일 값 3을 삭제한다고 한다면 값만 사라지고 비어있는 공간이 존재한다. 이 빈공간을 채우는 방법은 크게 두가지이다. 우축의 값을 빈공간과 교체하거나 빈공간 오른쪽의 값들을 왼쪽으로 밀어서 빈공간을 오른쪽 끝으로 밀어버리기 첫 번째 방식의 경우, 마지막 값이 위치한 공간만 안다면 손쉽게 해결할 수 있지만 값의 순서가 바뀌어버리는 문제가 있다.[# 마지막 값이 위치한 공간도 모른다면 시간 복잡도는 O(n)에 수렴할 것이다. 일일이 선형으로 다 돌면서 찾아야하니까] 그렇다고 두 번째 방식을 이용하자니 속도가 무조건 O(n)에 수렴한다. 일일이 값을 좌측..

데이터 검색시 시간 복잡도가 상수라고 알려진 해시맵 데이터를 저장하는 하나의 방법으로 의 쌍을 이룬다. 특정 key를 기반으로 value를 저장했을때, 저장한 value를 찾기 위해서는 key를 기반으로 검색한다. 해시맵을 알기 위해서는 해시함수를 필연적으로 알아야한다. 해시함수 어떤 정보를 수학적인 연산처리에 의해 고유한 값을 만들어내는 함수다. 즉, A라는 값을 해시함수에 넣었을 때 1이란 값이 나오고 B라는 값을 해시함수에 넣었을 때 2란 값이 나오는 방식이다. 위 예시에서 순차적으로 값을 내어주었기 때문에 혼동할 수 있는데, 해시함수는 아래의 조건을 만족해야 안정적인 함수이다. 눈사태효과를 가진다.[# 들어오는 값이 아주 조금만 변해도 완전히 다른 값이 산출된다.] 입력에는 하나의 출력만 존재한다..