자료구조 검색 결과

해당 글 34건
자료구조 스택 : 먼저 넣은 것이 나중에 빠진다.

재귀 호출에 대해서 저번시간에 쭉 배워보았습니다. 이번에는 자료구조 스택에 대해서 배워보고, 활용을 해 보도록 하겠습니다. 사실 계산기 프로그램 하나로 될 거 같긴 하지만, 더 좋은 예제가 없는지 고민을 해 보겠습니다. 하튼, 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
재귀 함수 : 자기 자신을 호출한다.

뜬금없이 C언어 시간에 배우셨을 재귀함수를 왜 자료구조 카데고리에 쓸까요? 사실, 재귀 호출은, 스택을 이용한 것이거든요. 이번 시간에는 간단하게 팩토리얼 함수와 피보나치 함수 정도를 재귀로 어떻게 구현하는지 이야기 해 보도록 하겠습니다. 재귀 함수는 아시다시피, 자기 자신을 호출하는 함수를 의미하는데요. 팩토리얼 함수 f(x) = f(x-1)*x로 정의를 할 수 있어요. 그러면, 다음과 같이 작성할 수 있을 거에요. 그런데, 이렇게만 작성을 하고 컴파일을 해서 프로그램을 실행시켜 보시면, 팩토리얼 5의 값이 나오지 않는 것을 알 수 있어요. 그냥 일정 시간동안 실행이 되다가, 종료가 되어 버리는 것을 알 수 있는데요. 이건 왜 그럴까요? fact 함수 내부를 보면 x에다가 fact(x-1)의 값을 리턴..
자료알고/자료구조 2019. 7. 8. 20:10
동적 배열 : expand 연산을 이해하는 것이 핵심이다.

보통 Dynamic array, 동적 배열이라고 하면 크기가 변하는 배열을 의미합니다. c++의 STL에서는 vector가, 그리고 Java에서는 ArrayList가 있어요. 그런데, push_back이나 add를 100만번, 200만번을 해도, 실제로는 그렇게 오래 걸리지 않는 듯 싶습니다. 이는 왜 그럴까요? ArrayList와 vector는 다음 두 함수가 있습니다. size와 capacity. 이 둘의 차이를 이해하기 전에, 배열에 원소를 추가할 때 어떤 식으로 처리해야 좋은지 생각해 보도록 합시다. 추가할 공간이 많이 남아 있습니다. 예를 들자면, 이 경우, 추가할 공간이 2개나 더 있습니다. 4 뒤에 추가해도 되는 상황입니다. 그러면, push_back이나 add가 호출이 되었을 때, 4 뒤에..
자료알고/자료구조 2019. 6. 23. 23:22