자료구조9 [자료구조] 힙(heapq) 힙(heapq)이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 최소 힙(min heap) 루트 노드가 가장 작은 값을 가진다. 따라서 값이 작은 데이터가 우선적으로 제거된다. 즉, 부모 노드가 항상 자식 노드보다 작다. 최대 힙(max heap) 루트 노드가 가장 큰 값을 가진다. 따라서 값이 큰 데이터가 우선적으로 제거된다. 즉, 부모 노드가 항상 자식 노드보다 크다.파이썬에서 heapq 모듈을 사용하여 구현할 수 있다.import heapqq= []a = [4,9,6,11,8]for i in range(len(a)): heapq.heappush(q,a[i])print(q)#q = [4, 8, 6, 11, 9]for i in range(len(a)): prin.. 2024. 6. 24. [자료구조] 연결리스트 리스트란?순서를 가진 항목들의 모임이다. 리스트 구현방법으로 배열을 이용한 구현과 연결리스트를 이용한 구현이 있다. 배열로 구현된 리스트배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당되므로, 이것을 리스트의 순차적 표현(sequential representation)이라고 한다.#define MAX_LIST_SIZE 100 // 리스트의 최대크기typedef int element; // 항목의 정의typedef struct { element array[MAX_LIST_SIZE]; // 배열 정의 int size; // 현재 리스트에 저장된 항목들의 개수} ArrayListType;// 오류 처리 함수void error(char *message){ fprintf(stderr, "%s\n", .. 2022. 10. 19. [자료구조] 덱(deque) 덱(deque)이란?¨double-ended queue의 줄임말로서 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐이다. 배열을 이용한 덱의 구현#include #include #define MAX_QUEUE_SIZE 5typedef int element;typedef struct { // 큐 타입 element data[MAX_QUEUE_SIZE]; int front, rear;} DequeType;// 오류 함수void error(char* message){ fprintf(stderr, "%s\n", message); exit(1);}// 초기화 void init_deque(DequeType* q){ q->front = q->rear = 0;}// 공백 상태 검출 함수i.. 2022. 10. 19. [자료구조] 큐(Queue) 큐(queue)란? 먼저 들어온 데이터가 먼저 나가는 자료구조로, 선입선출(FIFO: First-In First-Out)의 형태이다. 선형 큐배열을 선형으로 사용하여 큐를 구현삽입을 계속하기 위해서는 요소들을 이동시켜야 함.#include #include #define MAX_QUEUE_SIZE 5typedef int element;typedef struct { // 큐 타입 int front; int rear; element data[MAX_QUEUE_SIZE];} QueueType;// 오류 함수void error(char* message){ fprintf(stderr, "%s\n", message); exit(1);}void init_queue(QueueType* q){ q->rear =.. 2022. 10. 19. [자료구조] 스택(Stack) 예제 스택의 응용괄호 검사괄호의 종류 : [], {}, ()조건1.왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.2.같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.3.괄호 사이에는 포함 관계만 존재한다. 알고리즘의 개요문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 삽입하고,오른쪽 괄호를 만나면 스택에서 top 괄호를 삭제한 후 오른쪽 괄호와 짝이 맞는지를 검사한다.이 때, 스택이 비어 있으면 조건 1 또는 조건 2 등을 위배하게 되고 괄호의 짝이 맞지 않으면 조건 3 등에 위배된다.마지막 괄호까지를 조사한 후에도 스택에 괄호가 남아 있으면 조건 1에 위배되므로 0(거짓)을 반환하고, 그렇지 않으면 1(참)을 반환한다.#include #include #include #.. 2022. 10. 19. [자료구조] 스택(Stack) 스택이란?스택은 쌓아놓은 더미라는 뜻으로, 가장 최근에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO:Last-In First-Out)의 형태이다. 스택의 연산push(): 스택에 데이터를 추가pop(): 스택에서 데이터를 삭제is_empty(s): 스택이 공백상태인지 검사is_full(s): 스택이 포화상태인지 검사create(): 스택을 생성 peek(s): 요소를 스택에서 삭제하지 않고 보기만 하는 연산배열을 이용한 스택1차원 배열 stack[]스택에서 가장 최근에 입력되었던 자료를 가리키는 top 변수¨가장 먼저 들어온 요소는 stack[0]에, 가장 최근에 들어온 요소는 stack[top]에 저장스택이 공백상태이면 top은 -1전역 변수로 구현하는 방법#include #include #de.. 2022. 10. 19. [자료구조] 배열 구조체 포인터 배열같은 형의 변수를 여러 개 만드는 경우에 사용한다. 반복 코드 등에서 배열을 사용하면 효율적인 프로그래밍이 가능하다.배열의 응용 : 다항식다항식의 일반적인 형태다항식 표현 방법모든 차수에 대한 계수값을 배열로 저장한다. 하나의 다항식을 하나의 배열로 표현한다.#include #define MAX(a,b) (((a)>(b))?(a):(b))#define MAX_DEGREE 101 // 다항식의 최대차수 + 1typedef struct { int degree; float coef[MAX_DEGREE];} polynomial;polynomial a = { 5, {10, 0, 0, 0, 6, 3} };// C = A+B 여기서 A와 B는 다항식이다. 구조체가 반환된다. polynomial poly_add1(.. 2022. 10. 18. [자료구조] 순환, 히노이탑 순환이란? 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법이다.순환 알고리즘은 다음과 같은 부분들을 포함한다. 순환 호출을 하는 부분순환 호출을 멈추는 부분만약 순환 호출을 멈추는 부분이 없다면? 시스템 오류가 발생할 때까지 무한정 호출하게 된다.대부분의 순환은 반복으로 바꾸어 작성할 수 있다. 순환적인 방법이 더 효율적인 예제숫자 x의 n제곱 값을 구하는 문제: x^n반복double slow_power(double x, int n){ int i; double result = 1.0; for(i=0; i순환double power(double x, int n){ if( n==0 ) return 1; else if ( (n%2)==0 ) return power(x*x, n.. 2022. 10. 18. [자료구조] 자료구조와 알고리즘 자료구조와 알고리즘이란? 프로그램은 자료구조+알고리즘 말한다. 자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 알고리즘이란 컴퓨터로 문제를 풀기 위한 단계적인 절차이다.알고리즘의 조건입력 : 0개 이상의 입력이 존재해야 한다.출력 : 1개 이상의 출력이 존재해야 한다.명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.유효성 : 각 명령어들은 실행 가능한 연산이어야 한다.알고리즘의 기술 방법영어나 한국어와 같은 자연어흐름도 (flow chart)의사 코드 .. 2022. 10. 18. 이전 1 다음
