자료알고/자료구조 검색 결과

해당 글 43건
자기 참조 구조체 : 간단하게 이해해 봅시다.

자기 참조 구조체란, 자기 구조체와 같은 형을 point 하는 필드가 있는 구조체를 말해요. 왜 갑자기 자료구조가 안 나오고, 이것이 먼저 나왔을까요? 이것을 이해해야 List를 이해할 수 있기 때문이에요. 코드를 봅시다. 보시면 struct node 안에, struct node를 가리키는 포인터가 있음을 알 수 있어요. 그렇다면, node 안의 어떠한 필드가 또 다른 node를 가리킬 수 있다는 것을 의미합니다. 이런 식으로 말입니다. 이게 single로 이어져 있으면 모르겠지만, double로 이어져 있다면, 삭제할 위치라던지, 삽입할 위치만 알고 있다면, 삽입과 삭제하는 연산을 금방 할 수 있기 때문에, List를 쓰고요. C언어에서 List를 구현하기 위해서 자기 참조 구조체를 쓰는 셈입니다. "..
자료알고/자료구조 2019. 7. 24. 18:05
히스토그램에서 가장 큰 직사각형 : 스택으로 선형에 풀어보자.

스택을 응용한 문제 중에는, 히스토그램에서 가장 큰 직사각형이라는 문제가 있습니다. 히스토그램 안에서 그릴 수 있는 직사각형 중, 넓이가 가장 큰 직사각형의 넓이를 구하는 문제입니다. 이것은 푸는 방법이 상당히 많습니다. 세그먼트 트리로 풀어도 되고, 분할 정복으로 풀어도 됩니다. 여기에서는 우리가 배운 스택을 응용해서 풀어보도록 하겠습니다. 먼저 데이터가 다음과 같이 들어왔다고 해 봅시다. 히스토그램에서, 총 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..
자료알고/자료구조 2019. 7. 22. 16:30
올바른 괄호 문자열 검사하기 : 스택으로 손쉽게 해결해 보자.

저번 시간에 스택을 배웠으니까, 응용 문제들을 다뤄보도록 하겠습니다. 오늘은 조금 쉬운, 올바른 괄호 문자열을 검사하는 알고리즘을 작성해 보겠습니다. 올바른 괄호 문자열은 다음과 같이 재귀적으로 정의됩니다. 빈 문자열은 valid하다. (괄호문자열) 역시 valid 하다. 괄호문자열에 괄호문자열을 concat 한 것도 valid 하다. 예를 들어서 ()(())은 valid 합니다. 하지만, ())이나, ()((은 valid하지 않습니다. 이것은 어떻게 구현하면 좋을까요? 먼저, "())"이 올바른지 판단해 보도록 하겠습니다. '('이 들어오면, 괄호 스택에 (을 push 합니다. '('이 들어왔기 때문에, 스택에 '('가 들어가 있습니다. 그 다음에는 ')'가 옵니다. 이 때에는 stack의 맨 위의 원..
자료알고/자료구조 2019. 7. 20. 15:29
자료구조 스택 : 먼저 넣은 것이 나중에 빠진다.

재귀 호출에 대해서 저번시간에 쭉 배워보았습니다. 이번에는 자료구조 스택에 대해서 배워보고, 활용을 해 보도록 하겠습니다. 사실 계산기 프로그램 하나로 될 거 같긴 하지만, 더 좋은 예제가 없는지 고민을 해 보겠습니다. 하튼, stack은 나중에 넣은 원소가 먼저 빠진다는 특성 (Last In First Out : LIFO)을 가지고 있는데요. 주요 연산들만 간단하게 알아보는 시간 가지도록 합시다. 먼저 스택은 크게 2가지 포인터로 이루어져 있습니다. base pointer, 줄여서 bp입니다. 그리고 top pointer, sp라고 많이 이야기를 할 거에요. base는 스택의 시작점이 되는 포인터, 그리고 top은 실제로 꼭대기에 있는 원소를 가리키게 되어요. 만약에, 비어 있다면 top은, 배열로 구..
자료알고/자료구조 2019. 7. 18. 19:11
하노이탑 알고리즘 : 재귀 호출의 대표적인 문제를 구현해 봅시다.

재귀 함수를 배우셨으니까, 제일 유명한 문제 중 하나인 하노이탑 알고리즘을 구현해 봐야 겠어요. 보통 하노이의 탑 문제는 기둥이 3개이고, 작은 기둥 위에 큰 기둥이 올 수 없다는 조건이 걸려있는 문제를 말해요. 또 한 번에 하나의 원판을 옮길 수 있는데요. 물론 백준에는, 기둥이 4개이 문제도 보입니다. 그건 논외로 합시다. 99xx번대에 있던 걸로 기억하는데 말입니다. 이걸 어떻게 구현하면 좋을까요? 생각보다 난이도가 조금 있어 보이는데요. 답은 재귀에 있습니다. 이 부분에 대한 내용은 관련 글에 충분히 설명이 되어 있으니, 개념 이해가 아직 안 되셨다면 보시고 오시는 게 좋아 보입니다. [관련글] 재귀 함수가 무엇일까요? 먼저 기저 조건을 봅시다. 옮길 원판의 갯수가 0개이면 어떤가요? 어떠한 연산..
자료알고/자료구조 2019. 7. 12. 01:42