프로그래밍 언어들/알고리즘 썸네일형 리스트형 C언어 막대 자르기(Rod cutting in C) - 동적 프로그래밍(Dynamic-Programming) C언어 막대 자르기(Rod cutting in C) - 동적 프로그래밍(Dynamic-Programming) - 어떤 막대(rod)를 그들의 최종 값을 최대화하는 방식으로 작은 길이의 막대로 자르는 것 - 막대의 어느 부분을 자를 것인지 선택하는 간단한 문제 - 막대의 길이 n(inches)와 가격 p를 고려하여 자른 부위를 팔았을 때 얻을 수 있는 최고의 수익 r을 결정하는 것 - 만약 자른 길이의 가격이 충분히 크다면, 최적의 솔루션은 자르는 것을 전혀 요구하지 않는다. - 막대의 길이가 n이면 총 2ⁿ-¹의 다른 방식으로 자를 수 있다. ( 자르지 않는 경우의 수도 포함 ) the strategy of the rod-cutting, cite : introduction to algoritms 3/E .. 더보기 C언어 동적 프로그래밍(Dynamic Programming in C) C언어 동적 프로그래밍(Dynamic Programming in C) - 동적 프로그래밍은 하위문제들에 대한 해결책을 결합하는 방식으로 문제를 해결한다. - 일반적으로 동적 프로그래밍은 최적화 문제에 적용된다. - 동적 프로그래밍 알고리즘을 개발할 때, 다음과 같은 시퀀스를 따른다. (1) 최적의 해결책의 구조를 특징 짓는다. (2) 재귀적으로 최적의 해결책의 값을 정의한다. (3) 최적의 해결책의 값을 계산한다. (4) 계산된 정보를 바탕으로 최적의 해결책을 구성한다. 더보기 C언어 레드-블랙 트리 삭제 알고리즘(Red-Black Trees in C, deleting or removing algorithm) C언어 레드-블랙 트리 삭제 알고리즘(Red-Black Trees in C, deleting or removing algorithm) - 많은 검색-트리 구조 중 하나이다. - 기본 동적 명령들이 최악의 경우에도 O(lg n) 시간이 걸리도록 보장하기 위해 안정(balanced) 되었다. - 각 노드마다 하나의 추가적인 비트를 가지고 있다. - 편리한 상태처리를 위해 NIL을 나타내는 센티널 노드가 있다. - 다음 5가지의 특성을 만족하는 이진 트리이다. (1) 각 노드는 빨강 또는 검정색이다. (2) 루트(root)는 검정색이다. (3) 모든 leaf(NULL)은 블랙이다. (4) 만약 노드가 빨강이면, 해당 노드의 자식은 모두 검정이다. (5) 각 노드에 대해, 해당 노드에서 자식 노드까지의 모든 경.. 더보기 C언어 레드-블랙 트리 삽입 알고리즘 (Red-Black Trees in C, insertion algorithm) C언어 레드-블랙 트리 삽입 알고리즘 (Red-Black Trees in C, insertion algorithm) - 많은 검색-트리 구조 중 하나이다. - 기본 동적 명령들이 최악의 경우에도 O(lg n) 시간이 걸리도록 보장하기 위해 안정(balanced) 되었다. - 각 노드마다 하나의 추가적인 비트를 가지고 있다. - 편리한 상태처리를 위해 NIL을 나타내는 센티널 노드가 있다. - 다음 5가지의 특성을 만족하는 이진 트리이다. (1) 각 노드는 빨강 또는 검정색이다. (2) 루트(root)는 검정색이다. (3) 모든 leaf(NULL)은 블랙이다. (4) 만약 노드가 빨강이면, 해당 노드의 자식은 모두 검정이다. (5) 각 노드에 대해, 해당 노드에서 자식 노드까지의 모든 경로들은 같은 수의 .. 더보기 C언어 이진 탐색 트리(Binary Search Trees in C) C언어 이진 탐색 트리(Binary Search Trees in C) - 이진 탐색 트리는 각 노드가 객체인 연결된 데이터 구조로 표현된다. - 각 노드를 기준으로 노드의 키 값보다 작은 값은 좌측, 큰 값은 우측으로 보낸다. - 각 노드는 키 값 외에도 left, right, p의 포인터 변수를 포함한다. - left, right는 자신의 자노드들을, p는 상위 노드를 가르킨다. - root 노드는 유일하게 상위 노드가 없는 노드이다. [ Fig. 1 ] 이진 탐색 트리 1. 동작 원리 (1) root 노드를 가르키는 root 포인터를 선언하고 초기화 한다. (2 - 1) 노드 삽입 명령 시 새로운 노드를 생성하고, 키 값을 입력한다. (2 - 2) 현재 트리를 구성하고 있는 노드들의 키 값과 비교하여.. 더보기 C언어 원형 이중 연결리스트(Circular, doubly linked lists in C) C언어 원형 이중 연결리스트(Circular, doubly linked lists in C) - 이중 연결리스트의 구조에서 가장 처음과 마지막 노드가 서로 연결 되어있는 구조 - 시작 위치를 알기 위해 연결리스트의 맨 앞에 NULL 노드를 추가 [ Fig. 1 ] 원형 이중 연결리스트, site: introduction to algorithm 3/E 1. 동작 원리 (1) NULL 노드를 생성하고 초기화하고 HEAD 포인터가 이를 가르키게 한다. (2-1) 삽입 명령시 새로운 노드를 생성한다. (2-2) NULL 노드의 이전 노드를 새로 생성한 노드로 지정하고, 새로 생성한 노드의 다음 노드를 NULL 노드로 지정한다. (2-3) 연결리스트의 가장 마지막 노드를 찾아서, 이 노드의 다음 노드를 새로 생성.. 더보기 C언어 이중 연결리스트(Doubly linked lists in C) C언어 이중 연결리스트(Doubly linked lists in C) - 연결 리스트의 한 종류이다. - 각 노드가 자신의 다음 노드 및 자신의 이전 노드를 가르킨다. [ Fig. 1 ] Doubly linked list, site : introduction to algorithms 3/E 1. 동작 원리 (1) 연결리스트의 가장 처음을 가르키는 HEAD 포인터를 초기화한다. (2 - 1) 삽입 명령시 연결리스트의 가장 마지막 노드를 찾는다. (2 - 2) 연결된 노드가 없을 경우, HEAD가 새로 생성한 노드를 가르키게 한다. (2 - 2) 연결된 노드가 있을 경우 가장 마지막 노드 다음에 새로 생성한 노드를 연결하고, 새로 생성한 노드가 마지막 노드를 가르키게 한다. (3 - 1) 제거 명령시 제거하.. 더보기 C언어 단일 연결리스트(Singly linked lists in C) C언어 단일 연결리스트(Singly linked lists in C) - 연결리스트는 객체가 선형순서로 정렬되는 자료구조이다. - 배열의 인덱스가 아닌 각 객체의 포인터에 의해 연결리스트의 순서가 결정된다. - 연결리스트는 동적 구조를 위해 간단하고 유연한 표현을 제공한다. - HEAD 포인터가 리스트의 맨 앞을 가르키고, 각 노드가 다음 노드를 가르킨다. [ Fig. 1 ] Singly linked list 1. 동작 원리 (1) 연결리스트의 가장 처음 노드를 가르키는 HEAD 포인터를 초기화한다. (2 - 1) 삽입 명령시 새로운 노드를 생성하고, key 값을 입력한다. (2 - 2) HEAD 포인터가 가르키는 노드가 없을 경우 HEAD 포인터에 노드를 연결한다. (2 - 3) or 연결리스트의 가장.. 더보기 C언어 원형 큐(circular queues in C) C언어 원형 큐(circular queues in C) - 선형 큐의 문제점을 개선하기 위해 고안(= 큐의 포화 상태와 빈(empty) 상태를 구별하지 못함) - 큐의 한 칸을 비워두고 이것을 포화 상태와 빈(empty) 상태를 구분하기 위해 사용한다. [ Fig. 1 ] process of circular queue 위의 그림을 보면 (A)는 시작 부분이라 T(Tail)과 H(Head)가 동일한 위치에 있다. 즉, 이것은 큐가 비어있다는 것을 의미한다. 큐에 데이터를 삽입할 때 H가 가르키는 위치에 데이터를 삽입하게 되면 모든 큐에 데이터를 삽입했을 경우(=포화 상태) T와 H가 같은 곳을 가르키게 된다. 즉 포화 상태인지 큐가 비어있는 상태인지 알 수가 없다. 따라서 H가 가르키는 위치가 아니라 H .. 더보기 C언어 큐(Queues in C) - 연결리스트로 구현(The implementation with the linked lists) C언어 큐(Queues in C) - 연결리스트로 구현(The implementation with the linked lists) - 큐에 대한 내용은 이전 글 참고 1. 동작 원리 (1) 최근 노드를 가르키는 HEAD 포인터와 가장 오래된 노드를 가르키는 TAIL 포인터 초기화 (2 - 1) 삽입 명령 시 새로운 노드를 생성하고, 데이터를 입력한다. (2 - 2) TAIL 포인터가 가르키는 노드가 없을 경우(= 큐가 비어있을 경우) (2 - 2) HEAD와 TAIL이 새로운 노드를 가리킨다. (2 - 3) 가르키는 노드가 있을 경우, HEAD의 위치를 갱신하면서 새로운 노드를 추가한다. (3 - 1) 제거 명령 시 큐가 비어있는지 확인한다. (3 - 2) 큐에 노드가 있을 경우에 TAIL은 그 다음 노.. 더보기 이전 1 2 3 다음
