자료구조의 덱, 그러니까 deque는 queue하고 비슷합니다. front와 back, 이렇게 2개의 포인터 있습니다. 그런데, 큐가 front에서 삭제가 일어나고, back에서 삽입 연산이 일어나는데 비해서, 덱은 front에서도 삽입과 삭제가, back에서도 삽입과 삭제가 일어납니다. 이 연산만 구현하려면, 사실 List로 구현하는 게 제일 간단해 보입니다. 먼저 다음과 같이 초기화를 시켜 봅시다. 그러면 이 때가 비어있는 상태일 겁니다. head->next가 tail이고, tail->prev가 head일 때, empty 상태라고 판단할 수 있습니다. 저는 이 두 개의 더미를 인위적으로 잇기만 하였습니다. 여기에서 push_front 연산을 수행해 봅시다. 이것은 맨 앞에 원소를 추가하는 것입니다. ..
자료구조 검색 결과
Queue를 직접 구현해야 할 때에는 어떻게 해야 할까요? 사실, 선형 큐를 먼저 고려합니다. 큐는 먼저 넣은 친구가 먼저 빠지는 특성을 지닙니다. 예를 들자면, 은행 창구를 생각해 보세요. 먼저 번호표를 뽑은 손님이 먼저 처리됩니다. 그런가요? 그렇기 때문에, 포인터가 front하고 rear, 이렇게 2개가 있는데요. front는 제일 앞에 있는 것을, rear는 제일 뒤에, 넣을 위치를 가리킵니다. 선형 큐를 구현할 때, 저는 is_full 처리를 하지 않아요. 그렇기 때문에 초기 크기를, 큐에 들어가는 원소의 갯수 + 10로 잡습니다. 예를 들어서, 가로 r개, 세로 c개의 맵이라면 BFS를 돌릴 때, rc만큼 들어가기 때문에 크기를 rc + 10 정도로 잡습니다. 처음에 front와 rear의 값..
자기 참조 구조체란, 자기 구조체와 같은 형을 point 하는 필드가 있는 구조체를 말해요. 왜 갑자기 자료구조가 안 나오고, 이것이 먼저 나왔을까요? 이것을 이해해야 List를 이해할 수 있기 때문이에요. 코드를 봅시다. 보시면 struct node 안에, struct node를 가리키는 포인터가 있음을 알 수 있어요. 그렇다면, node 안의 어떠한 필드가 또 다른 node를 가리킬 수 있다는 것을 의미합니다. 이런 식으로 말입니다. 이게 single로 이어져 있으면 모르겠지만, double로 이어져 있다면, 삭제할 위치라던지, 삽입할 위치만 알고 있다면, 삽입과 삭제하는 연산을 금방 할 수 있기 때문에, List를 쓰고요. C언어에서 List를 구현하기 위해서 자기 참조 구조체를 쓰는 셈입니다. "..
스택을 응용한 문제 중에는, 히스토그램에서 가장 큰 직사각형이라는 문제가 있습니다. 히스토그램 안에서 그릴 수 있는 직사각형 중, 넓이가 가장 큰 직사각형의 넓이를 구하는 문제입니다. 이것은 푸는 방법이 상당히 많습니다. 세그먼트 트리로 풀어도 되고, 분할 정복으로 풀어도 됩니다. 여기에서는 우리가 배운 스택을 응용해서 풀어보도록 하겠습니다. 먼저 데이터가 다음과 같이 들어왔다고 해 봅시다. 히스토그램에서, 총 7개의 직사각형이 있어요. 그러면 arr[0]과 arr[8]은 0으로 초기화를 합니다. 이를 더미 데이터라고 합니다. 처리하기 쉽게 처리한 겁니다. 그리고 arr[1] = 2, arr[2] = 1, arr[3] = 4, arr[4] = 5, arr[5] = 1, arr[6] = arr[7] = 3..
저번 시간에 스택을 배웠으니까, 응용 문제들을 다뤄보도록 하겠습니다. 오늘은 조금 쉬운, 올바른 괄호 문자열을 검사하는 알고리즘을 작성해 보겠습니다. 올바른 괄호 문자열은 다음과 같이 재귀적으로 정의됩니다. 빈 문자열은 valid하다. (괄호문자열) 역시 valid 하다. 괄호문자열에 괄호문자열을 concat 한 것도 valid 하다. 예를 들어서 ()(())은 valid 합니다. 하지만, ())이나, ()((은 valid하지 않습니다. 이것은 어떻게 구현하면 좋을까요? 먼저, "())"이 올바른지 판단해 보도록 하겠습니다. '('이 들어오면, 괄호 스택에 (을 push 합니다. '('이 들어왔기 때문에, 스택에 '('가 들어가 있습니다. 그 다음에는 ')'가 옵니다. 이 때에는 stack의 맨 위의 원..
최근댓글