본문 바로가기

C4

[C/자료구조] 최대, 최소 힙(heap) 정렬 구현 힙(heap) 자료구조 - 부모가 되는 노드의 값이 자식 노드보다 크거나 작은 자료구조 - 완전이진트리의 구조를 가짐 - 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 - 방식에 따라 최대 힙(max heap)과 최소 힙(min heap)으로 나뉨 힙(heap)의 구현 - 힙을 저장하는 표준적인 자료구조는 배열 이다. - 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. - 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. · 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다. - 힙에서의 부모 노드와 자식 노드의 관계 · 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 · 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 +.. 2022. 11. 30.
[C/자료구조] 연결 리스트 다항식 덧셈 연결 리스트를 이용하여 희소 다항식을 표현 동적 메모리를 이용한 단순 연결 리스트로 표현하였음 한 개의 노드는 data / link 2가지의 값을 가짐 (data는 현재 노드의 값, link는 다음 노드의 주소) 노드의 data는 '계수(coef)'와 '차수(expn)'값을 가짐 이때, 연결 리스트는 '차수' 내림차순 정렬된 형태를 가짐 두 다항식을 더하는 add_poly 함수 구현 두 리스트 list1, list2 를 인자로 받음 두 다항식을 더한 결과 리스트 ListType* new_poly 생성 및 초기화 두 리스트의 감시할 노드를 가르키는 ListNode* h1, *h2 생성, 각 리스트의 head로 초기화 h1 또는 h2 가 하나라도 NULL 값이 아니면 반복 h1이 NULL인 경우, h2 노드.. 2022. 11. 20.
[C/자료구조] 하노이탑 문제 하노이탑이란? 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 하노이탑의 조건 한 번에 한개의 원판만 옮길 수 있다. 맨 위에 있는 원판만 이동할 수 있다. 크기가 작은 원판위에 큰 원판이 쌓일 수 없다. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다. 이제 문제 자체는 이해했으니, 이를 체계적으로 정의해보자. "체계적"이라함은, 문제의 입력과 출력을 보다 함수에 가깝게 정의하자는 것이다. 우리는 "원반의 이동횟수를 최소화하고자 할 때, 각 원반을 옮기는 모든 순서를 출력하는 것"으로 한다. 이때 각 이동의 출력은 '3번 원반을 A에서 C와 같이로 정하며.. 2022. 10. 22.
[C/자료구조] 재귀함수를 이용한 피보나치 수열과 반복문을 이용한 피보나치 수열 피보나치 수열이란? 피보나치 수열이란 다음과 같이 정의되는 수열이다 피보나치 수열에서는 앞의 두 개의 숫자를 더해서 뒤의 숫자를 만든다. 정의에 따라 수열을 만들어 보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 피노나치 수열은 이탈리아 수학자 피보나치(Fivonacci)가 발견한 수열로서 한 쌍의 토끼가 번식하는 상황을 수열로 만든 것이다. 피보나치 수열은 수학과 과학의 많은 분야에서 사용되고 있다. 피보나치 수열은 정의 자체가 순환적으로 되어 있다. 따라서 구현 시에 순환 호출을 사용하는 것이 자연스러운 방법이다. 피보나치 수열을 재귀함수로 이용하여 프로그램해 보면 다음과 같다. #define _CRT_SECURE_NO_WARNINGS #i.. 2022. 10. 21.

티스토리툴바