바킹독의 실전 알고리즘

0x00 알고리즘 설명 정점과 간선으로 이루어진 자료구조인 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 0x01 예시 원리를 이해해보자 우선 BFS 알고리즘에서는 좌표를 담을 큐가 필요하다. BFS 알고리즘이 시작되면 우선 (0, 0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다. 이 초기 세팅이 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하게 된다. 첫 시작(큐의 front)을 기록해놨으면 pop을 하고 그 점으로부터의 상하좌우 칸을 보는데, 이 중에서 파란색 칸이면서 아직 방문하지 않은 칸을 찾을것이다. 위 상황을 보면 (0,0)과 상하좌우로 인접한 (0,1)과 (1,)은 모두 파란칸이면서 방문하지 않았..

0x00 수식의 괄호 쌍이란? 괄호를 빼놓고 봐도 위에껀 올바른 수식의 괄호 쌍이고 밑에껀 그렇지 않다는게 딱 눈에 들어올 것이다. 이와 같이 수식의 괄호 쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제이다. 0x01 문제 해결을 위한 관찰 올바르게 문자열을 읽을때 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다. 문자열을 다 읽었고 남아있는 괄호가 없는 것으로 보아 모든게 다 짝이 잘 맞았다는걸 알 수 있다. 이처럼 올바른 괄호 쌍일 경우 여는 괄호를 읽을 때 마다 저장하다가 닫는 괄호를 읽을 때 가장 최근에 들어온, 즉 가장 끝에 있는 여는 괄호와 짝을 이루게 해주고 pop을 하면 올바른 괄호 쌍인..

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에서의 포인터랑 거의 ..