# 스택 - stack: 선형 리스트의 특별한 형태로, 책 또는 접시 같은 것들을 쌓아 둔 것을 의미 - 후입 선출(LIFO: Last-In, First-Out) 구조 - 함수 호출, 문법 검사, 연산식 평가 등에 활용 - 다음과 같이 원소들의 리스트로 정의 가능 S = [a0, a1, ...., an-1] - push: 원소 추가 / pop: 원소 삭제 - ex) 스택에 원소 a, b, c, d, e 삽입 및 삭제 # 스택 예제 (1) Balanced Parentheses - 괄호의 짝이 맞는지 확인하는 예제 [코드] // c++로 구현한 check_balance 함수 void check_balance(char* p) { struct Stack stack; create(stack, LINESIZE); ..

# Matrix (m rows * n cols) - 2차원 배열: matrix[m][n] - Space complixity = S(m,n) = m*n → 얼마만큼의 기억장소를 필요로하는지 나타내는 척도 * 배열이 int 형일 때, S(m,n) = m*n*4 ex) 4 : 배열 안의 원소를 entry라고 하며 배열을 사용해 나타낼 때는 matrix[0][2]와 같이 나타냄 # Sparse Matrix - 희소 행렬: 행렬의 값이 대부분 0인 행렬 → 저장 공간은 큰데 의미있는 값은 적음 - A[m,n]: 대부분의 값이 0이며 이 행렬을 효과적으로 저장하는 방법을 찾아야함 → 중요한 목표 # Sparse Matrix solution - 0이 아닌 element만 저장한다 - 3튜플을 가지는 배열을 활용한다 ..

자료구조 개념 및 구현 Chapter 4. 알고리즘 분석 - 연습문제 Q1. 점근적 표기법(asymptotic notation)을 사용하는 이유를 적으시오. - 알고리즘의 성능을 비교하기 위해 사용함. 입력의 수가 매우 커질 때, 알고리즘의 복잡도가 증가하는 패턴을 살펴봄 Q2. 시간 복잡도와 공간 복잡도는 각각 무엇을 의미하는가? - 시간 복잡도: 프로그램이 수행을 완료하는데 걸리는 시간 - 공간 복잡도: 알고리즘 실행에 필요한 메모리 Q3. 시간 복잡도에 대한 점근적 표기법의 세 가지 종류를 각각 설명하시오 - 상한선(Big-Oh) 표기법: 시간 복잡도 함수 f(n) = Ο(g(n))이라고 표기할 수 있다면, 이 알고리즘의 수행 시간은 상한선 c·g(n)을 넘지 않는다는 의미 - 하한선(Big-Ome..

# 알고리즘의 성능 분석 - 설계된 프로그램의 구현이 완료될 때 프로그램 성능 평가 과정이 수행됨 - 프로그램은 여러 개의 알고리즘으로 구성될 수 있으므로 알고리즘의 성능 평가라고 부를 수 있음 - 일반적인 성능 평가 질문의 예: 기준이 모호하고 구체적이지 않으므로 객관적인 평가 방법으로 사용하기에 적합하지 않음 더보기 · 프로그램이 본래의 요구 사항들을 만족하고 있는가? · 오류 없이 올바르게 동작하는가? · 효율적으로 구현되었는가? - 실행 가능한 성능 분석 기준: 공간 복잡도(space complexity), 시간 복잡도(time complexity) - 실행 가능한 성능 분석 기준은 알고리즘 간의 성능 비교가 가능함 → 측정 가능한 구체적인 수치를 제공하기 때문 # 공간 복잡도(Space Comp..

자료구조 개념 및 구현 Chapter 3. 재귀 호출 - 연습문제 Q1. 반복문(iteration)과 비교한 재귀문(recursion)의 장단점은 무엇인가? - 장점: 알고리즘을 명료하게 표현 가능 - 단점: 빈번한 함수 호출로 인한 스택 오버플로우 현상 발생 Q2. n개의 정렬된 정수에 대하여 반복문과 재귀 호출 함수를 각각 사용하여 이진 탐색하는 프로그램을 작성하시오. 재귀 호출 함수가 몇 번 호출되는지 변수를 추가하여 확인하시오. [코드] #include #include int binary_search(int list[], int item, int left, int right); int rbinsearch(int list[], int searchkey, int left, int right); int..

# 순열 - 어떤 원소 n개를 나열할 때 순서가 다르면 다른 순열로 간주함 (1) 집합 {'a', 'b', 'c'}에 대하여 찾을 수 있는 모든 순열 > P = {(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)} > 3P3 = 3 * 2 * 1 = 3! = 6 (2) 집합 {'a', 'b', 'c', 'd'}의 순열 > 4! = 24 > 24개의 순열은 4개의 그룹으로 나뉘어질 수 있음 a) (a, Perm(b, c, d)) b) (b, Perm(a, c, d)) c) (c, Perm(a, b, d)) d) (d, Perm(a, b, c)) > 하나의 원소를 고정하고 그 뒤에 원소의 수만 다른 순열을 나타내는 함수를 호출함 > ex) P..

# 하노이 타워 (1) - 세 개의 기둥과 크기가 다양한 원판들이 존재 > 초기 상태: 한 기둥에 모든 원판이 꽂혀 있음 - 목표: 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥에 옮기는 것 - 조건 ① 한 번에 하나의 원판만 옮길 수 있다 ② 큰 원판이 작은 원판 위에 놓일 수 없다 - 알고리즘 더보기 세 개의 기둥 A, B, C가 있고 기둥 A에서 B로 n개의 원판을 옮긴다고 가정 1. 기둥 A에서 n-1개의 원판을 A, B가 아닌 기둥 C로 옮긴다 2. 기둥 A에 남은 1개의 원판을 B로 옮긴다 3. 기둥 C에 있는 n-1개를 기둥 B로 옮긴다 > 2번 과정: 1개의 원판이 이동하면 됨 > 1, 3번 과정: 원판의 수가 1개 줄어든 또 다른 하노이 타워 문제 → 재귀적인 방법으로 해결 가능 >..

# 유클리드 호제법 - 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나 - 호제법이란? > 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘을 나타냄 - 내용 > 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 함 (이때 a>b) > a와 b의 최대공약수는 b와 r의 최대 공약수와 같음 > 위의 성질에 의해 b를 r로 나눈 나머지 r'을 구하고 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복함 > 위의 과정에서 나머지가 0이 될 때 나누는 수가 a와 b의 최대 공약수가 되는 것 # 최대 공약수 (greatest common divisor) gcd(x,y) = gcd(s,x%y) if y>0 gcd(x,0) = x - 최대 공약수를 구하는 알고리즘 > y가 0이면 x를 ..

# 재귀 호출의 개념 - 재귀 호출: 함수가 실행 중에 자기 자신을 다시 호출하는 상황 - 종료 조건을 가지는 동일한 task가 반복될 때 가능 // 종료 조건: 함수가 끝나야하기 때문에 필요 > 종결 조건은 재귀 호출에 반드시 포함되어야하며 잘못 설정할 경우 프로그램이 무한 반복에 빠질 수 있음 - 시스템 입장에서는 새로운 함수가 불리는 것과 같음 - 함수 실행 중 또 다른 함수가 실행되면 함수의 컨텍스트(context), 정보(지역변수, 복귀주소)를 활성 레코드(activation record)에 저장하여 보관하여야 함 - 활성 레코드는 함수의 환경 정보를 담고 있는 구조체이며 실행되는 함수마다 1개씩 생성되어 시스템 스택에서 저장 관리됨 - 시스템 스택은 함수 호출을 관리하기 위해 프로그램에서 사용..

# Polynomial A(x) = 3x^20 + 2x^5 + 4 - a sum of terms(항), ax^e (x: variable, a: coeffiecient(계수), e: exponent(지수)) ​ ​ # Operations of Polynomial ADT - Zero(): 다항식을 0으로 만듦 ::= return 다항식, p(x) = 0 - IsZero(poly): 다항식이 0인지 검사 ::= if(poly) return FALSE else return True - Coef(poly, expon): 다항식에서 지수가 expon인 계수를 반환 - Lead_Exp(poly): 다항식에서 가장 큰 차수(지수의 값)를 반환 - Attach(poly, coef, expon): 계수가 coef이고 지수..