본문 바로가기

Programming/Algorithm

C++ 스택을 사용한 괄호 짝 맞추기(Balanced brackets) 괄호 짝 맞추기(Balanced brackets)는 여는 괄호와 닫는 괄호의 짝이 맞는지 확인하는 문제입니다. 가장 나중에 열렸던 괄호 타입이 가장 먼저 닫혀야 됩니다. 이런 특성은 스택(Stack) 자료형을 활용하면 쉽게 구현이 가능합니다. 여는 괄호는 모두 스택에 넣고 닫는 괄호가 나올 때 스택의 최상단(Top)에 위치한 여는 괄호와 비교합니다. 그리고 닫는 괄호가 나왔을 때 스택이 비어 있으면 잘못된 짝으로 구성된 것입니다. 모든 문자를 비교한 이후에 스택이 깔끔하게 비었으면 완전한 괄호 짝이 맞는 문자열이 됩니다. 전체적인 코드는 다음과 같습니다. 30줄 남짓의 코드로 쉽게 구현이 가능합니다. 추가로 브라켓을 추가해야 하는 경우 map 타입의 pairs에 여는 괄호와 닫는 괄호 쌍을 입력해주면 됩.. 더보기
[정렬 알고리즘] 퀵 소트(Quick Sort) 퀵 소트는 이름 그대로 빠른 성능을 제공하는 정렬 알고리즘입니다.평균적으로 O(n log n)으로, 최악의 경우 O(n2)의 시간 복잡도를 보입니다.기본적인 방식은 아래와 같습니다. 리스트에서 원소를 한 개 선택하는데 이 원소를 피벗(Pivot)이라고 부릅니다. 피벗이 선정되면 피벗보다 작은 값들은 피벗의 좌측에, 큰 값들은 우측에 위치시킵니다. 피벗은 자신의 자리를 찾았으므로 고정되며 좌우의 작은 값들과 큰 값들을 다시 재귀로 반복합니다. 이런 식으로 피벗의 위치를 전부 찾아주게 되면 결과적으로 정렬된 리스트가 됩니다.피벗은 다양한 방법으로 선택이 가능한데 보통 가장 앞의 원소나 가장 뒤의 원소를 선택해서 진행합니다.다음 코드는 가장 뒤의 원소를 피벗으로 선택하는 퀵 소트 코드입니다. #include .. 더보기
2개의 스택(Stack)으로 큐(Queue) 구현하기 스택(Stack)과 큐(Queue)는 대표적인 자료구조 중 하나입니다.스택은 후입선출(Last In First Out) 방식이며 큐는 선입선출(First In First Out) 방식입니다.일반적으로 스택은 접시 쌓기로 비유하고 큐는 은행 등의 대기열에 비유됩니다.스택과 큐는 다음과 같은 방향으로 데이터를 입력하고 출력합니다.스택은 1 -> 2 -> 3 -> 4 순서로 넣고 4 -> 3 -> 2 -> 1의 순서로 꺼낼 수 있습니다.큐는 1 -> 2 -> 3 -> 4 순서로 넣고 1 -> 2 -> 3 -> 4의 동일한 순서로 꺼낼 수 있습니다.꺼낼 때의 순서가 완전히 반대인 것을 확인할 수 있습니다.2개의 스택으로 큐를 구현하는 것은 면접 등에서 자주 볼 수 있는 알고리즘 문제 중 하나입니다.스택에 입력했.. 더보기
[정렬 알고리즘] 삽입 정렬(Insertion Sort) 정렬 알고리즘인 삽입 정렬입니다.배열의 앞쪽부터 시작해서 순회하면서 정렬을 합니다.그리고 앞 부분의 정렬된 부분에서 선택된 값의 위치를 찾아서 이동시키는 알고리즘입니다.기본적으로 버블 소트나 선택 정렬보다 성능이 좋고 구현이 간편한 장점이 있는 정렬입니다.또한 추가적인 메모리가 크게 필요 없는 In-Place 알고리즘입니다.반복문을 돌리기 위한 변수와 swap을 위한 변수 정도가 추가로 필요합니다.그리고 같은 값이 있을 때 그 순서가 변경되지 않는 안정 정렬입니다.Wiki에서 확인할 수 있는 삽입 정렬의 정렬 방식입니다.http://en.wikipedia.org/wiki/Insertion_sort이 영상이 삽입 정렬의 모든 것을 보여주고 있습니다.두 번째 값부터 시작해서 각각의 값들이 앞부분의 정렬된 부.. 더보기
[정렬 알고리즘] 선택 정렬(Selection Sort) 선택 정렬은 정렬 알고리즘의 한 방법입니다.버블 정렬과 마찬가지로 간단한 정렬 알고리즘에 속합니다.가장 작은(혹은 큰) 값을 찾아서 맨 앞(혹은 맨 뒤)로 차곡차곡 이동시키는 방법입니다.기본적으로 생각할 수 있는 방법으로 정렬합니다.선택 정렬의 코드는 다음과 같습니다. #include using namespace std; template void MySwap(T& a, T &b) { T tmpVal = a; a = b; b = tmpVal; } template void SelectionSort(T* arVal, int nCount) { int maxidx; int i, j; for (i = nCount - 1 ; i >= 0 ; --i) { for (maxidx = i, j = i - 1 ; j >= 0.. 더보기
[정렬 알고리즘] 버블 소트(거품정렬) 버블 소트는 정렬 알고리즘의 한 종류입니다. 정렬 알고리즘은 무작위로 있는 정보를 순차적으로 재배치 시키는 것이 목적입니다. 버블 소트는 각종 정렬 알고리즘 중에서도 기본으로 여겨지는 알고리즘입니다. 정렬 알고리즘은 퀵 정렬, 삽입 정렬, 힙 정렬, 선택 정렬 등 여러가지 방법이 존재합니다. 보통은 속도가 빠른 퀵소트를 많이 사용합니다. 퀵소트를 구현하는데는 재귀 함수 방식이 많이 활용됩니다. 재귀 함수에 대한 설명은 아래 링크에서 확인 가능합니다.2014/12/04 - [Programming/C&C++] - 재귀 함수 & 재귀적 함수호출(recursive function call)그럼 본격적으로 버블 소트에 대해서 알아보도록 하겠습니다. 만약 버블 소트의 코드만 필요하다만 가장 하단의 코드를 참조하시면.. 더보기
간단한 GCD 알고리즘(Euclid 호제법) 간단한 GCD(최대공약수)를 구하는 코드입니다. 여기에 이용되는 방법 중 하나가, 유클리드 호제법이라는 방법입니다. A, B가 있을 때((A > B)라고 가정) A를 B로 나눴을 때 나눠지면 B가 최대 공약수입니다. 하지만 나누어 떨어지지 않으면 A를 B로 B를 A % B로 치환하고서 다시 A % B를 실행합니다. 계속 반복했을 때 A % B = 0이 됐을 때의 B값이 GCD값이 됩니다. 12와 9를 기준으로 보겠습니다. A % B = 3 입니다. 나누어 떨어지지 않았기 때문에 A = B, 즉 9가 되고 B = A%B, 즉 3이 됩니다. 9와 3을 가지고 다시 돌립니다. A%B = 0 그럼 여기서 나오는 3(B의값)이 최대공약수라는 것을 알 수 있습니다. 최대공약수가 쓰이는 부분은 많지만 가장 기본적인 .. 더보기