'Programming Languages' 카테고리의 글 목록 (3 Page)

Programming Languages

72건

13 버블 정렬, 칵테일 정렬

버블 정렬: 이웃한 두 요소의 비교, 교환을 반복해 정렬 패스(Pass): 비교, 교환 작업 버블 정렬 구현 교환 횟수는 비교 횟수 = (n - 1) + (n - 2) + 1 = n(n - 1) / 2 의 절반인 n(n - 1) / 4 swap 함수 안에서 값의 이동이 3회 발생하므로 평균 3n(n - 1) / 4 버블 정렬 개선안(1) 버블 정렬 개선안(2) 칵테일 정렬 이 배열은 맨 앞 요소(9) 때문에 빠른 시간 안에 정렬 작업을 마칠 수 없다. 그래서 패스의 방향을 교대로 바꾸는 방식(칵테일 정렬)을 사용한다. /*--- 양방향 버블 정렬(칵테일 셰이커 정렬) ---*/ void shaker(int a[], int n) { int left = 0; int right = n - 1; int last..

12 정렬이란?

정렬(Sorting)이란? : 특정 핵심 항목(key)의 대소 관계에 따라 데이터의 집합을 일정한 순서로 만드는 작업 : 정렬을 통해 검색을 빠르게 할 수 있다. 오름차순(Ascending), 내림차순(Descending) 안정성(Stable)이란? : 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것 정렬 알고리즘의 핵심 요소 : 교환, 선택, 삽입 내부 정렬, 외부 정렬 : 내부 정렬(Internal Sorting) - 정렬할 모든 데이터가 하나의 배열에 저장 할 있는 경우 : 외부 정렬(External Sorting) - 정렬할 데이터가 너무 많아서, 하나의 배열에 저장 할 수 없는 경우

8퀸 문제란? : 서로 공격 할 수 없도록 8개의 퀸은 8x8 체스판에 놓는 문제 1. 8 x 8 체스판, 64칸 에 8개의 퀸을 놓을 수 있는 조합 2. [규칙1] 각 열에 1개씩 배치 3. [규칙2] 각 행에 1개식 배치 3. [규칙3] 대각선 겹침 해결

10 하노이의 탑

하노이의 탑(Top of Hanoi) 1. 하노의 탑 룰 2. 하노이의 탑 그룹핑 - 작은 문제로 분해 3. 하노이의 탑 그룹핑 룰 - 작은 문제의 반복 4. 하노이의 탑 구현

09 재귀 알고리즘 분석

재귀의 이해는 컴퓨터의 실행 구조를 이해하는데 효과적이다. 분석 방법 1. 하향식(top down) 2. 상향식(bottom up) 3. 비재귀적 구현 1. 하향식(top down) 2. 상향식(bottom up) 3. 비재귀적 표현 재귀 함수를 재귀 호출을 사용하지 않고 구현하는 방법 3.1 꼬리 재귀 제거 방법 3.2 재귀 재거 방법

08 재귀와 유클리드 호제법

유클리드 호제법(Euclidean method of mutual division) : 두 정수의 최대 공약수(Greatest Common Divisor)를 재귀적으로 구하는 방법

07 재귀와 순차곱셈(Factorial)

재귀(recursive)란? : 순차곱셈(Factorial) :음이 아닌 정수 n의 순사곱셈(n!) 정의 1. 0! = 1 2. n > 0 이면, n! = n x (n-1)! = 10! = 10 x 9! = 10 x 9 x 8! = 10 x 9 x 8 x 7! ...

큐(Queue)란? : "대기열" : 스택과 마찬가지로 데이터를 일시적으로 저장하기 위한 자료구조 : 큐의 출력 순서 : 선입선출(FIFO, Fisrt In First Out), 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다. 인큐(enqueue): 큐에 데이터를 넣는 작업 디큐(dequeue): 큐에 데이터를 꺼내는 작업 배열을 통한 인큐 디큐 복잡도 데이터를 꺼낼때마다 효율이 떨어진다. 링 버퍼 구조를 통한 디큐 복잡도 향상 링 버퍼 구성도 프런트(front): 맨 처음 요소의 인덱스 리어(rear): 맨 끝 요소 하나 뒤의 인덱스(= 인큐 위치) 인큐와 디큐 수행시, 프런트와 리어 값을 업데이트하면 앞서 발생한 요소 이동 문제를 해결하고 복잡도를 O(1)이 된다. + 오래된 데이터를 버리는 용도

스택(Stack)이란? : "겹겹이 쌓음" : 데이터를 일시적으로 저장하기 위해 사용하는 자료구조 : C 언어 프로그램에서 함수 호출, 실행시 내부에서 스택 구조를 사용한다. 스택의 출력 순서 : 후입선출(LIFO, Last In, First Out), 마지막에 넣은 데이터를 가장 먼저 꺼낸다. 푸시(Push): 스택에 데이터를 넣는 작업 팝(Pop): 스택에서 데이터를 꺼내는 작업 함수의 호출과 실행 과정

1 2 3 4 5 6 ··· 8

티스토리툴바