본문 바로가기

코딩 및 기타/어서와! 자료구조와 알고리즘

 (34)
16 일차 정렬과 탐색 (분할 정복과 정렬 알고리즘) ∙ 분할 정복 (divide and conquer) - 주어진 문제의 규모가 커서 한 번에 해결하기 어려운 경우, 이를 작은 부분 문제로 나워서 해결하는 방식 - 분할(divide) : 주어진 문제를 동일한 방식으로 해결할 수 있는 부분 문제로 나누기 - 정복(conquer) : 각 부분 문제에 대한 솔루션 구하기 - 결합(combine) : 각 부분 문제의 솔루션을 결합하여 전체 문제에 대한 솔루션 구하기 ∙ 분할 정복을 이용한 정렬 알고리즘 - 병합 정렬(merge sort) > 분할 정복에 의한 정렬 알고리즘의 하나 > 입력 배열을 두 개의 부분 배열로 분할 > 각 부분 배열의 원소가 하나가 될 때까지 반복 > 부분 배열을 병합 > 이때 병합된 배열의 원소..
15 일차 정렬과 탐색 ∙ 정렬 (sort) - 주어진 데이터를 정해진 기준에 따라 순서를 재배열하는 작업 - 가장 기본적이고 중요한 알고리즘 중의 하나 ∙ 다양한 정렬 알고리즘 (sorting algorithm) 1. 알고리즘 단순 & 시간 복잡도가 느리고, 비효율적 - 버블 정렬(bubble sort) - 선택 정렬(selection sort) - 삽입 정렬(insertion sort) 2. 알고리즘 복잡 & 대용량 데이터에 대해서 빠르게 동작, 효율적 - 쉘 정렬(shell sort) - 병합 정렬(merge sort) - 퀵 정렬(quick sort) - 힙 정렬(heap sort) - 기수 정렬(radix sort) ∙ 정렬 알고리즘의 평가 척도 - 비교 횟수 & 이동 횟수 - 모든 경우에 최적인 정렬 알..
재귀 알고리즘 주요 예제 팩토리얼 (factorial, 계승) ∙ 팩토리얼 - 20보다 같거나 작은 자연수 N이 입력으로 주어질 경우, 1 * 2 * 3* ... *. (N-1)*N 을 계산하는 팩토리얼 함수를 작성하시오 #include using namespace std; // factorial(20)이 값이 크기 때문에 int형으로 불가능 long long factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } int main() { cout
14 일차 재귀 ∙ 재귀 알고리즘 (recursion, 순환) - 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법 - 많은 종류의 문제가 재귀적으로 해결 가능 > 피보나치수열, 이진 탐색, 병합 정렬, 퀵 정렬 등 ∙ 재귀 함수 (recursion function) - 자기 자신을 다시 호출하는 함수. 순환 함수 - 자기 자신을 완전히 그대로 호출하지 않고, 함수의 인자를 특정한 방식으로 변경하여 호출 (무한 루프에 빠질 수 있기 때문에) ∙ 재귀 함수의 구성 - 기저 조건(base case) : 재귀를 종료하기 위한 조건이 있어야 함(종료 조건) - 재귀 호출(recursive case) : 자기 자신을 다시 호출하는 부분, 재귀를 반복하다 보면 반드시 기저 조건으로 수렴해야 함 ..
13 일차 환형 큐 ∙ 배열을 이용한 큐의 구현 - 크기가 8인 배열에 3개의 데이터가 추가된 큐의 상태 ∙ 배열을 이용하여 구현한 큐의 문제점 - 큐에 데이터의 삽입과 삭제가 지속적으로 발생할 경우, 배열의 앞부분에 무효화되는 공간이 늘어남 ∙ 환형 큐(circular queue) - 선입 선출(FIFO) 원칙에 따라 작업이 수행되고, 마지막 위치가 마치 원을 이루듯이 다시 첫 번째 위치에 연결되는 선형 데이터 구조 - 큐의 front와 rear 값이 시계 방향으로 한 칸씩 이동하는 형태 > 실제 구현에서는 배열 전체 크기를 이용하여 나머지(%) 연산을 수행 - 큐가 empty 또는 full 상태인지를 확인하기 위해 원소의 개수를 따로 저장해야 함 ∙ 환형 큐에서 데이터 추가 rear = (rear + 1) % ..
12일차 큐 ∙ 큐 (queue) - 자료구조에서 큐는 데이터를 마치 줄을 세워 늘여 놓듯이 저장하는 선형 자료 구조로서, 선입선출 원리에 따라 삽입과 삭제가 수행된다. 선입선출 (FIFO) : 먼저 들어온 데이터가 먼저 출력됨 - 데이터 삽입은 뒤쪽에서 데이터 삭제는 앞쪽에서 수행되는 리스트 ∙ 큐의 주요 연산 - enqueue(e) : 큐의 맨 뒤에 있는 원소 e를 추가. push(e) - dequeue() : 큐의 맨 앞에 있는 원소를 삭제. pop() - front() : 큐의 맨 앞에있는 원소를 참고. peek() - empty() : 큐가 비어있으면 true를 반환 - size() : 큐의 원소 개수를 반환 ∙ 배열을 이용한 큐의 구현 - 미리 정해진 크기의 배열을 할당하고, 큐의 앞과 뒤를 나타내는 ..
11일차 스택의 응용 : 올바른 괄호 검사 ∙ 올바른 괄호 검사 - 괄호만으로 이루어진 문자열이 주어질 때, 괄호의 종류별로 쌍이 제대로 되어 있는지를 검사하기 - 괄호의 종류 : [ ] (대괄호, brackets), { } (중괄호, braces), ( ) (소괄호, parentheses) - 올바른 괄호의 조건 > 괄호의 종류별로 여는 괄호와 닫는 괄호의 개수가 같아야 한다. > 같은 종류의 괄호에서 여는 괄호가 닫는 괄호보다 먼저 나타나야 한다. > 마지막 여는 괄호와 쌍이 되는 닫는 괄호가 먼저 나타나야 한다. ∙ 올바른 괄호 검사 알고리즘 - 문자열의 각 문자를 차례대로 검사 > 여는 괄호 (, {, [ 를 만나면 스택에 push > 닫는 괄호 ), }, ] 를 만나면 > 스택이 비어 있으면 false ..
10일차 문자열과 백터 순서 뒤집기 ∙ 문자열 뒤집기 - 문자열의 각 문자 순서를 역순으로 변경 (Palindrome) - 문자열을 역순으로 뒤집는 방법은 여러 가지 있지만, 스택을 사용하여 변경할 수 있음 ex) "Hello" -> "olleH" , "ALGORITHM" -> "MHTIROGLA" ∙ 스택을 이용한 문자열 뒤집기 - 문자열의 각 문자를 스택에 push한 후, 다시 스택에서 문자를 하나씩 pop 하여 출력 문자열을 생성 ∙ 예시 코드 #include #include using namespace std; string reverse(const string& str) { stack stk; for (char c : str) stk.push(c); string res; while (!stk.empty()..

티스토리툴바