나의 기록, 현진록

dbguswls030/Argorithm Contribute to dbguswls030/Argorithm development by creating an account on GitHub. github.com 재귀 호출로 구현할 수 있는 가장 대표적인 예 중 하나가 피보나치 수열이다. 앞의 두 개의 숫자를 더해 뒤의 숫자를 만들면 된다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.... func fib(_ n: Int) -> Int{ if n == 0{ return 0 } else if n == 1{ return 1 } else{ return fib(n-1) + fib(n-2) } } 이 함수는 단순하고 이해하기 쉽게 재귀 호출로 구현되었지만 사실 매우 비효율적이다. 그 이유는 ..

dbguswls030/Argorithm Contribute to dbguswls030/Argorithm development by creating an account on GitHub. github.com 순환(recursion), 또는 재귀 호출이란 어떤 알고리즘이나 함수가 자시 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 순환이란? 순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다. 정수 팩토리얼은 순환의 예가 될 수 있다. n!은 다음과 같이 정의할 수 있다. if n = 0 { n! = 1 } else if n>=1 { n! = n * (n-1) } n! 을 정의하는데 다시 팩토리얼 (n-1)!이 사용된 것에 주목하라. 이러한 정의를 순환적이라고 한다. 위 정..

dbguswls030/Argorithm Contribute to dbguswls030/Argorithm development by creating an account on GitHub. github.com 원형 덱의 예 덱은 큐를 응용하여 전단(front)과 후단(rear)에서 삽입(add), 삭제(delete)가 모두 이루어진다. 선형 덱에서 배열을 원형으로 생각하면 원형 덱으로 구현할 수 있다. 원형 덱의 경우에는 front와 rear의 값이 배열의 끝인 MAX_DEQUE_SIZE-1에 도달하면 다음 증가되는 값이 0으로 되도록 한다. 구현에 필요한 요소 initDeque() : 덱을 초기화 함 add_front(e) : 주어진 요소 e를 덱의 맨 앞에 추가한다. delete_front() : 전단 ..

dbguswls030/Argorithm Contribute to dbguswls030/Argorithm development by creating an account on GitHub. github.com 덱의 예 덱은 큐를 응용하여 만들어진 것으로 전단(front)과 후단(rear)에서 모두 삽입, 삭제가 가능한 큐를 의미한다. 구현에 필요한 요소 init() : 덱을 초기화 함 add_front(e) : 주어진 요소 e를 덱의 맨 앞에 추가한다. delete_front() : 전단 요소를 삭제하고 반환한다. add_rear(e) : 주어진 요소 e를 덱의 맨 뒤에 추가한다. delete_rear() : 전단 요소를 삭제하지 않고 반환한다. get_front() : 전단 욯소를 삭제하지 않고 반환한다...

dbguswls030/Argorithm Contribute to dbguswls030/Argorithm development by creating an account on GitHub. github.com 원형 큐 실제 배열로 구현된 큐는 원형의 형태를 가지지 않지만 원형이라고 가정할 수 있도록 구현할 수 있다. 다음은 선형 큐를 원형 큐로 변형하는 데에 이해하기 위한 사진이다. 구현에 필요한 요소 init() : 큐를 초기화하는 메소드 is_empty() : 큐가 비어있는지 여부를 확인 enqueue(x) : x를 큐에 삽입 dequeue() : 큐에서 rear에 위치한 요소 삭제 후 반환 size() : 큐의 모든 요수 개수를 반환 peek() : 큐에서 rear에 위치한 요소 삭제하지 않고 반환 M..

dbguswls030/Argorithm Contribute to dbguswls030/Argorithm development by creating an account on GitHub. github.com 큐의 예 스택이 나중에 들어온 데이터가 먼저 쓰이는 후입선출 구조 형태의 자료구조였다면, 큐는 먼저 들어온 데이터가 먼저 쓰이는 선입선출 구조 형태의 자료구조이다. 실생활에서의 예로는 은행에서 서비스를 기다리는 손님들의 길게 늘어진 줄로 이해할 수 있다. 먼저 번호표를 뽑고 줄을 서게 되면 줄에 가장 먼저 와서 기다린 손님부터 업무를 처리하는 방식이다. 다음은 선형 큐를 구현에 쓰인 요소들이다. init() : 큐를 초기화하는 메소드 is_empty() : 큐가 비어있는지 여부를 확인 enqueue(x..

삽입 정렬 삽입 정렬은 한 번에 한 항목씩 최종 정렬된 배열에서 자신의 위치를 찾아 삽입함으로 정렬을 완성하는 알고리즘이다. 시간 복잡도는 평균 O(n2)으로 퀵 정렬이나, 힙 정렬 또는 병합 정렬과 같은 고급 알고리즘보다 큰 목록에서 비효율적이다. 시간 복잡도의 최상은 O(n), 최악은 O(n2)이다. 다음 영상은 삽입 정렬의 동작 방식이다. 12345678910111213141516171819#include void insertion_sort(int arr[], int len) { for (int i = 1; i = 0 && key

선택 정렬 선택 정렬이란 리스트 중에 최솟값을 찾아 맨 앞의 값과 교체하는 정렬이다. 시간 복잡도는 평균 O(n2)으로 일반적으로 유사한 삽입 정렬보다 비효율적이며, 특히 큰 리스트에서 최악의 효율성을 가진다. 시간 복잡도의 최상은 O(n2), 최악은 O(n2)이다. 다음 영상은 선택 정렬의 동작 방식이다. 12345678910111213141516171819202122#include void selection_sort(int arr[], int len) { for (int i = 0; i

버블 정렬 버블 정렬은 인접한 두 원소를 비교하여 정렬하는 방법이다. 시간 복잡도는 평균 O(n2)로 느리고 비효율적이지만 코드가 단순하기 때문에 자주 사용된다. 시간 복잡도의 최상은 O(n), 최악은 O(n2)을 기록한다. 다음 영상은 버블 정렬 동작 방식이다. 1234567891011121314151617181920#include void bubble_sort(int arr[], int len) { for (int i = 0; i