공부 일지/알고리즘

0x00 정의와 성질\ 정의 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 덱은 deque고 Double Ended Queue라는 뜻이다. 성질 덱에서도 삽입, 삭제, 제일 앞/뒤 원소의 확인이 다 O(1). 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다. STL stack, queue에서 불가능했던걸 생각하면 꽤 독특한 일이다. 0x01구현 덱도 스택이나 큐처럼 배열 혹은 연결 리스트 둘 다를 가지고 구현할 수 있지만 배열을 이용하는게 구현이 더 쉽기 때문에 배열을 이용해 구현해 볼것이다. 일단 필요한 변수는 큐랑 똑같이 원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개이다. 이 때 head와 tail을..

0x00 정의와 성질 정의 큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택을 FILO(First In Last Out)이라고 한 것과 비슷하게 큐를 FIFO(First in First Out)이라고 하기도 한다. 성질 큐에서는 추가되는 곳을 rear(뒤쪽)라고 하고, 제거되는 쪽을 front(앞쪽)이라고 한다. 0x01 기능과 구현 선형 배열로 만든 큐 head는 가장 앞에있는 원소의 인덱스이고 tail은 가장 뒤에 있는 원소의 인덱스 +1 이다. 꼭 이렇게 안두고 tail을 가장 뒤에있는 원소의 인덱스로 두어도 괜찮다. 값을 추가하면 head는 변함이 없고 tail은 한 칸..

0x00 정의와 성질 정의 자료구조에서의 스택이란, 한쪽 같에서만 원소를 넣거나 뺼 수 있는 자료구조이다. 스택은 구조적으로 먼저 들어간 원소가 제일 나중에 나오게 되는데, 이런 의미로 FILO(First in Last Out) 자료구조라고 부르기도 한다. 참고로 큐나 덱도 스택처럼 특정위치에서만 원소를 넣거나 뺼 수 있는 제한이 걸려있다. 그래서 스택, 큐, 덱을 묶어서 Restricted Structure라고 부르기도 한다. 성질 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않는다. STL stack에서도 이 기능은 없다. 그리고 스택을 활용하는 예시들을 보면 애초에 제일 상단이 아닌 나머지 원소들의 확인/변경이 필요하지 않다. 하지만 배열을 이용해 스택을 구현하면 기본적인..

0x00 정의와 성질 연결리스트의 정의 원소들을 저장할때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조 연결리스트의 성질 k번째 원소를 확인/변경하기 위해 O(k)가 필요함 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 더보기 Cache hit rate란? 다음에 사이트를 재방문할 때 해당 콘텐츠가 훨씬 빠르게 표시 되도록 웹 사이트의 데이터와 콘텐츠를 임시로 저장하는 고속 메모리. 연결리스트의 종류 단일 연결 리스트 : 단일 연결 리스트는 각 원소가 자신의 다음 원소의 주소를 들고 있다 이중 연결 리스트 : 이중 연결 리스트에서는 각 원소가 자신의 이전 원소와 다음 원소의 주소를..

0x00 정의와 성질 정의 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 Cache hit rate가 높음 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 0x01 기능과 구현 어떤 배열에서 구현 - insert 함수 insert함수를 구현해 보면 void insert(int idx, int num, int arr[], int& len){ for(int i = len; i > idx; i--)//for문으로 순차적으로 값들을 오른쪽으로 이동시킴 arr[i] = arr[i-1]; arr[idx] = num;//새롭게 추가할 값을 넣기 len++;//용량이 부족하니 추가 } 구현 - erase 함수 erase함수를 구현해 보면 voi..

0x00 STL과 함수 인자 참조자(Reference) swap1 함수는 제대로 동작하지 않는걸 알 수 있다. 원본 2개를 바꾸고 싶은데 복사된 2개를 바꾼다한들 의미가 없는것. 그래서 swap2 함수처럼 포인터를 보내서 두 변수의 값을 바꿀 수가 있다. 그런데 C++에서는 해결법이 한 개 더 있는데, 바로 참조자(reference)이다. swap3 함수를 보면 함수 인자인 a와 b의 type이 int가 아니고, int 뒤에 &가 붙어있는 것을 볼 수 있다. 그러니까 a와 b는 int reference인 것이다. 저렇게 a와 b를 참조자로 만들면 함수 내의 코드에서는 그냥 int를 쓰듯이 tmp에 a를 대입하고, a에 b를 대입하고 하는데 저게 다 원본을 바꾸는 것이다. 참조자는 C에서의 포인터랑 거의 ..

0x00 시간, 공간복잡도 시간복잡도(Time Complexity) ★ 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 빅오표기법(Big-O Notation) 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 일단 5N+3을 보면 누가 봐도 N이 커지면 커질수록 3보다는 5N이 훨씬 크다. 그래서 3을 버리고 5N만 냅두는데, 5N에서 상수 5도 떼고 O(N)으로 나타낸다. 2N+10lgN에서도 N이 커지면 커질수록 10lgN보다는 2N이 훨씬 클테니 2N만 냅두고, 상수 2를 떼서 O(N)으로 나타낸다. N^2+2N+4에서는 N^2이 2N과 4보다 훨씬 크니 O(N^2)이 된다. NlgN과 N을 비교하면 아무래도 그냥 N보다는 lgN이 곱해진 NlgN이 더 클 것입니다. 그래서 NlgN ..