자료알고 검색 결과

해당 글 130건
올바른 괄호 문자열 검사하기 : 스택으로 손쉽게 해결해 보자.

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

2가지 정렬을 배웠습니다. insert, select. 이 두 개는 키 값들을 비교를 했습니다. 2개의 값을 compare 했습니다. 제가 오늘 설명하는 counting sort, 계수 정렬은 이 둘과 크게 다른 점이 있는데요. 두 개의 키 값을 비교하지 않는다는 것입니다. 즉, 비교 기반 정렬이 아닙니다. 그러면 어떻게 구현을 할까요? arr = [3, 6, 3, 0, 4, 1]이라고 해 봅시다. 최솟값이 양수고, 최댓값 또한 적당히 작은 수라고 해 봅시다. co[x]를, 배열에서 x가 나타난 빈도수라고 정의합시다. 그러면, arr을 순회하면서, 어떠한 값 v가 나오면 co[v]의 값을 하나씩 증가시키면 될 거에요. 먼저 co 배열은 아래와 같이 초기화가 되어 있습니다. 1번째 원소를 봅니다. 3입니다..
자료알고/알고리즘 2019. 7. 20. 01:22
이진 검색 (binary search) : 정렬이 되어 있어야 한다.

어떠한 수가 배열 내에 있는지를 빠르게 찾고 싶습니다. 그럴 때, 이진 검색, binary search를 이용할 수 있습니다. 그런데, 전제 조건은 정렬이 되어 있어야 한다는 것입니다. 왜 그럴까요? 정렬이 되어 있지 않다고 해 봅시다. 중앙에 있는 3을 기준으로 9는 왼쪽에 있고 오른쪽에 없을 수도 있어요. 그러면 3을 기준으로 왼쪽에서 찾아야 합니다. 그런데, 이런 경우도 있을 수가 있어요. 중앙에 있는 3을 기준으로 좌측에 없고, 우측에 있다. 이런 경우는 또 어떤가요? 내가 있는 위치를 기준으로 9가 왼쪽에 있을 수도 있고, 오른쪽에 있을 수도 있고, 없을 수도 있기 때문에, 현재 탐색하는 위치를 기준으로 절반씩 해를 좁혀나갈 수가 없어요. 따라서, 선형 탐색으로 해결을 할 수 밖에 없을 거에요...
자료알고/알고리즘 2019. 7. 19. 00:10
자료구조 스택 : 먼저 넣은 것이 나중에 빠진다.

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

오늘은 선택 정렬 알고리즘에 대해 공부해 봅시다. selection sort는 매 회전마다, 제일 우선 순위가 높은 값을 선택해서 재정렬 하는 알고리즘입니다. 배열 arr의 크기가 n이라고 해 봅시다. 그러면 총 n회전을 돌 건데요. i회전일 때 이러한 일을 수행합니다. 구간 [i,n]에서 우선순위가 가장 높은 위치 lo를 찾습니다. 그리고 배열에서 i번째 원소와 lo번째에 있는 값을 맞바꿉니다. 구간 [i,n]은 정렬이 되어 있지 않기 때문에, 우선 순위가 가장 높은 값과 위치를 찾기 위해서, i에서부터 n까지 보아야 합니다. 그러므로, 회전마다 O(n-i)만큼 걸리게 되고, 결과적으로 시간 복잡도는 O(n^2)가 됩니다. 매 회전마다, O(log(n)) 급에 해결할 수 있는 방법이 있는데, 특수한 자..
자료알고/알고리즘 2019. 7. 17. 19:47