Programming/자료구조12 [자료구조] 12. 큐(Queue) 큐 (Queue) ▶ 줄 서기. ▶ 특징 : First In First Out (FIFO). First Come First Served. ▶ 정의 : Insert가 한쪽 끝(Rear)에서 발생하고, Remove가 다른 한 쪽 끝(Front)에서 발생하는 제한 조건(constraint)을 갖는 리스트형 구조. ▷ (초기화를 -1로 하는 방식으로 구현하는 경우) front와 rear가 동일한 인덱스를 가리키면, 배열에 남은 값은 하나이다. (구현 방식에 따라 차이가 있을 수 있음.) ▶ 선형 큐 vs. 원형 큐 ▷ 선형 큐의 경우, 실제 배열에 값이 가득 차있지 않고 배열 인덱스 마지막 칸에만 값이 있어도 rear값이 배열의 끝에 도달하면 Full이라고 처리된다. 이 단점을 보완해주는 것이 원형 큐이다. 원.. 2021. 11. 2. [자료구조] 11. 중위(Infix), 전위(Prefix), 후위(Postfix), 수식 표기법 ※ 수식 표기법의 기준은 연산자(Operator)이다. 중위 표기법 (Infix Notation) ▶ 연산자(Operator)가 피연산자(Operand) 중간에 위치. ▷ 예시 : 9+5, G-Y, K*9 ▶ 사람들이 일반적으로 계산할 때 사용. ▶ 연산자 우선순위를 고려하여 계산함. ( 괄호 -> 지수 -> 곱셈과 나눗셈 -> 덧셈과 뺄셈 ) ▶ 연산 방향 : 왼쪽에서 오른쪽으로. ▶ 문제점 : 괄호가 없으면 계산이 모호해질 수 있으며, 괄호와 연산자 우선순위를 고려해야 하기 때문에 수식 전체를 봐야 한다. 이러한 문제점을 보완하기 위해서 나온 것이 전위 표기법과 후위 표기법이다. 전위, 후위 표기법은 연산자의 우선순위를 고려하지 않아도 되며 괄호를 사용할 필요가 없다. 때문에 계산이 모호해지는 일도 .. 2021. 11. 1. [자료구조] 10. 스택 (Stack) 스택 (Stack) ▶ 쌓아놓은 더미. ▶ 특징 : LIFO (Last-In First-Out) : 후입 선출의 특징을 가짐. ≫ 가장 최근에 들어온 데이터가 가장 먼저 나감. ▷ Top : 스택의 상단. 정보의 입출력이 발생하는 곳. ▷ Bottom : 스택의 하단. ▶ 정의 : Insert와 Remove가 동일한 한 쪽 끝(Top)에서 발생하는 제한 조건(constraint)을 갖는리스트형 구조. 스택 추상 데이터 타입 (ADT) º 객체 (Object) : 0개 이상의 아이템을 가지는 유한 선형 리스트. º 속성 (Attributes) : 리스트의 한쪽 끝(Top)에서 삽입(Insertion)과 삭제 (Deletion) 발생. · create(size) : 크기가 size인 empty stack 생.. 2021. 10. 30. [자료구조] 09. 동적 메모리 할당 동적 메모리 (Dynamic Memory) 할당 ▶ 프로그램의 실행 도중에 Heap 영역으로부터 메모리를 할당받는 것. ▶ 필요한 만큼만 할당 받고, 사용 후 반납하기 때문에 효율인 메모리 사용 가능. ▶ 동적 메모리를 다 사용한 후, free함수로 해제 필수. main() { int *DM; DM = (int *)malloc(sizeof(int));//동적 메모리 할당 --- ***//동적 메모리 사용 --- free(DM); //동적 메모리 반납. 필수!!! } ▷ malloc(5*sizeof(int)); → 5 : 필요한 수만큼 곱하기 → sizeof(int) : 4byte. ▶ 활용 예제 ▷ 전형적인 동적 메모리 할당 //malloc을 이용하여 정수 10개를 저장할 수 있는 동적 메모리를 할당하고.. 2021. 10. 29. [자료구조] 08. 포인터 ※ 사전 지식 변수 : 이름(name) / 값(value) / 주소 값(address)을 가짐. 포인터(Pointer) ▶ 다른 변수의 주소를 가지고 있는 변수. int a = 10; int *p; p = &a; //포인터 변수의 초기화 ▷ p : 포인터 변수. p의 값은 주소값. 해당 주소에 실제 위치한 값이 int. (p의 값으로 a의 주소 값 할당) ▶ 포인터가 가리키는 값의 변경 : * 연산자 사용. (역참조) ▷ 역참조 : p값인 주소값이 실제로 갖는 값을 가져옴. ▷ 변수 a의 값을 직접 변경하지 않아도 포인터 변수 p의 역참조를 통해 a의 값을 변경할 수 있음. int a = 100; int *p = &a; // a의 주소값을 이용해 포인터 변수 p의 값을 초기화 *p = 200; // 변수.. 2021. 10. 27. [자료구조] 07. 배열과 구조체 배열 (Array) ▶ 같은 자료형의 변수를 여러 개 만드는 경우에 사용한다. (타입이 같은 데이터들을 하나로 묶는 방법.) ▷ 예시 : int list 1, list 2, list3, list4, list5, list6; → int list [6]; ▶ 1차원 배열(One-Dimensional Array; Vector) int value, list[6]; // 정수형 배열과 변수 선언 list[0] = 100; // 배열 첫번째 원소에 값을 할당.(100 할당) value = list[0]; // 배열 첫번째 원소의 값을 가져와 value 수에 할당. (value = 100) ▶ 2차원 배열(Two-Dimensional Array; Matrix) int list[3][5]; //정수형 2차원 배열 선언.. 2021. 10. 26. [자료구조] 06. 재귀 (Recursion) 재귀란? ▶ 알고리즘이나 함수가 실행 중에 자기 자신을 다시 호출하여 (함수 정의에서 자기 자신 호출 포함) 문제를 해결하는 기법이다. 정의 자체가 순환적으로 되어 있는 경우에 적합하다. ▶예시 : 팩토리얼 구현 int factorial(int n) { if(n ALGORITHYM factorial(n) // 알고리즘 이름 //Input : n (Integer; n >= 0) //Output : n! if n ▷모든 재귀 알고리즘은 2 part로 나뉜다. 1) Base Case (= Escape Condition) : 탈출 조건 → 탈출 조건이 없다면 시스템 오류가 발생할 때까지 무한 호출하게 된다. 2) General Case : 일반적 정의 재귀(Recursion) vs 반복(Iteration) ▶ .. 2021. 10. 23. [자료구조] 05. 알고리즘의 효율성 (최선, 평균,최악) 알고리즘의 효율성 1. 최선의 경우 (best case) : 수행 시간이 가장 빠른 경우. (운이 좋은 경우) 2. 평균의 경우 (average case) : 수행 시간이 평균적인 경우. 3. 최악의 경우 (worst case) : 수행 시간이 가장 늦은 경우. (운이 나쁜 경우) ▶ 예시 : 순차 탐색에서의 최선, 최악, 평균 ▷ 최선의 경우 : 찾는 숫자가 맨 앞에 있는 경우. (입력에 무관해지므로, 의미 없는 경우가 많음.) → O(1) ▷ 최악의 경우 : 찾는 숫자가 맨 뒤에 있는 경우. (가장 널리 사용됨. 응용에 따라 중요한 의미를 가짐. 계산하기 쉬움.) → O(n) (O(10)이 아닌 이유 : 뒤에서부터 찾기 시작해도 제일 마지막에 찾아야 하기 때문이다.) ▷ 평균적인 경우 : 각 요소들이.. 2021. 10. 22. [자료구조] 04. 빅오메가 표기법 & 빅세타 표기법 빅오메가 표기법 (Big Omega) ※ 수학적 정의 : 모든 n ≥ n0에 대하여 |f(n)| ≥ C|g(n)|을 만족하는 2개의 상수 C와 n0가 존재하면 f(n) = Ω(g(n))이다. ▶ 함수의 하한 (lower bound)을 표시한다. ▶ 예를 들어, f(n) = 2n +1일 때, n ≥ 5이면 2n + 1 < 10n이므로 f(n) = Ω(n)이다. ▶ 빅오 표기법이 Worst Case에 대한 표기법이라면, 빅오메가 표기법은 Best Case에 대한 표기법이다. 빅세타 표기법 (Big Theta) ※ 수학적 정의 : 모든 n ≥ n0에 대하여 C1|g(n)| ≤ |f(n)| ≤ C2|g(n)|을 만족하는 3개의 상수 C1, C2와 n0가 존재하면 f(n) = Θ(g(n))이다. ▶ 함수의 상한인.. 2021. 10. 21. [자료구조] 03. 알고리즘의 성능 분석(시간 복잡도, 빅오 표기법) "얼마나 효율적인가?" (시간/메모리/리소스) 1. 수행 시간 측정 (직접 구현 O ) → 동일한 하드웨어를 사용하여 실제 수행 시간을 측정한다. 2. 알고리즘의 복잡도 측정 (직접 구현 X) → 연산의 횟수를 계산하여 비교한다. (예측) → 연산의 횟수는 n의 함수 (n은 충분히 큰 양의 정수. 즉, 입력의 크기에 따른 연산 횟수를 계산한다.) 수행 시간 측정 2가지 방법 #include start = clock(); // 시작 전 check // 알고리즘 내용 삽입 부분 stop = clock(); // 종료 직후 check double duration = (double)(stop - start) / CLOCK_PER_SEC; #include start = time(NULL); //알고리즘 내용 삽입.. 2021. 10. 20. [자료구조] 02. 추상 데이터 타입 사전 지식) 자료형 - 데이터의 종류(데이터와 연산의 집합) "추상 데이터 타입(ADT : Abstract Data Type)" ▶ 데이터 타입을 추상적(개념으로만 존재하고 실재하지 않는)으로 정의한 것이다. (= 개념으로만 존재하고 실재하지 않는다.) ▷ 데이터의 추상화 : 사용자에게 중요한 기능과 동작만 강조되고, 중요하지 않은 구현 세부 사항은 제거하는 것을 말한다. ▶ 데이터나 연산이 무엇인가는 정의(속성, 특징을 정의) 되지만 데이터나 연산을 컴퓨터 상에서 어떻게(방법을 정의하지 않는다.) 구현할 것인지 세부적 사항은 정의하지 않는다. 추상 데이터 타입의 정의 * 객체 : 추상 데이터 타입에 속하는 속성 또는 특징을 정의한다. * 연산 : 객체들 사이의 연산을 정의하고, 추상 데이터 타입과 외부.. 2021. 10. 20. [자료구조] 01. 자료 구조와 알고리즘 * 자료구조 : 데이터의 표현 및 저장 방법 * 알고리즘 : 문제의 해결 방법, 문제를 풀기 위한 단계적 절차. 자료구조에 의존적임. 1. 입력 : 0개 이상의 입력이 존재해야 한다. 2. 출력 : 1개 이상의 출력 즉, 반환 값이 존재해야 한다. 3. 명백성 : 각 명령어의 의미는(입출력은) 명확해야 한다. 4. 유한성 : 반드시 종료 되어야 한다. (무한 루프에 빠져서는 안 된다.) 5. 유효성 : 컴퓨터로 실행 가능한 연산이어야 한다. 1. 자연어 (Natural Language / 말, 글로 기술) -장점 : 사람이 읽기 쉽다. -단점 : 간결하지 않고, 코드로 변환하기 어렵다.(모호성 존재).. 2021. 10. 12. 이전 1 다음
