남민우의 공부 블로그

하노이 타워란?원반을 한 번에 하나씩 옮기면서 최종적으로 초기 상태를 유지한 채로 두 칸 옆의 기둥으로 옮기는 퍼즐이 퍼즐을 현실에서 푸는 동작은 사실 어렵지 않다.문제는 이 과정에서 재귀의 특성을 찾고, 그걸 프로그래밍적으로 해결하는 것이다. 크기가 큰 순서부터 3, 2, 1 이라고 할 때제일 먼저 해결해야 하는 것은 3 원반을 C로 옮기는 것. 다만 그렇게 하려니 2번과 1번을 B로 치워야 한다.2번과 1번 원반을 옮기면, 또 1번을 C로 옮겨야 한다.처음 이 문제를 보면서 프로그래밍적으로는 큰 문제를 해결하기 위해 작은 문제부터 해결하는 분할 정복(Divide/Conquer) 알고리즘을 사용해야 하나 싶었는데, 조금 다른 결의 풀이다. 내가 생각했던 이유로는 4개의 원판이 있다고 했을 때 3개를 먼..

프로그래밍 및 언어/자료구조 학습 2024. 10. 21. 02:21

재귀의 이해재귀란? 어떤 코드를 정의할 때 그 안에서 자기 자신을 참조하는 것을 말한다.흐름 상 반복문과 혼동하거나 호출 구조를 헷갈리기 쉬운데, 먼저 반복문은 한번 함수 호출 시 그 함수의 본문을 계속적으로 반복하는 코드 동작이라 별개의 방식이고호출 구조를 봤을 때 같은 자기 자신을 계속 호출하는 재진입의 구조로도 보이지만정확하게는 원본 함수를 한번 호출하고, 같은 함수의 복사본을 계속 생성해내는 Copy&Paste -> Call 의 과정이라고 보는 것이 정확하다.모든 코드 동작은 동작 시 컴퓨터에 메모리를 차지한다.이때 재귀함수의 메모리 호출 - 해제 순서는원본 - 복사본A - 복사본B - 복사본C ... 으로 소요됐을 경우... - 복사본C - 복사본B - 복사본A - 원본 순으로 역방향으로 메모리..

프로그래밍 및 언어/자료구조 학습 2024. 10. 20. 23:30

순차 탐색의 최악의 경우 시간 복잡도는T(n) = n 으로 나타내고 이는 빅-오 표기법으로 O(n) 으로 나타낸다. 이진 탐색의 최악의 경우 시간 복잡도는T(n) = Log2N + 1 로 나타내고 이는 빅-오 표기법으로 O(LogN) 으로 나타낸다. 둘을 비교하기 위해선 n에 증가량에 따른 연산 횟수를 살펴봐야 하는데단순 계산만 보더라도순차 탐색의 연산횟수보다 이진 탐색의 연산 횟수가 극단적으로 적다는 것을 알 수 있다 특히 이진 탐색의 연산 횟수는 n의 값이 증가함에 따라 그 상승폭이 점점 더 줄어드는 모습으로이는 사용하기 좋은, 매우 뛰어난 알고리즘이다 라고 결론 내릴 수 있다.

프로그래밍 및 언어/자료구조 학습 2024. 10. 19. 01:21

이전 #5의 마지막 문단, +1을 생략하는 이유에 이어서 진행된다. 빅-오 표기법T(n) 의 수식에서 실제로 영향력을 끼치는 부분을 '빅-오(Big-Oh)' 라고 부른다.이 영향력을 끼치는 부분만 표기하는 방법이다. 이전 +1 을 생략하는 질문을 다르게 생각해서+1 이 너무 작은 수치라 생략하는 거라면 +100, +500 과 같이 숫자가 커져도 똑같이 생략하는거냐?라는 질문을 던질 수 있다. 이 대답을 하기에 앞서, 시간 복잡도 함수를 보는데 있어서 그 관점이 어디에 있냐 를 먼저 판단해야 한다.그 관점이 어딘가 하면 항상 가정하는 최악의 경우, 즉 데이터 표본이 셀 수 없을 많을 때 이다. 데이터 표본이 너무 많아서, 예를 들어 10만, 100만의 데이터 중 원하는 값을 찾는다고 할 때과연 +100, ..

프로그래밍 및 언어/자료구조 학습 2024. 10. 18. 03:34

시간 복잡도를 구하기 위해, 당연하게도 함수를 먼저 구해서 그래프를 그려야 한다....while(first 이 기본 골격에서 핵심 연산은 " == " 연산이다.이전 순차 탐색 알고리즘에서 봤던 것과 동일하게 다른 연산자, 추가로 if / else 문 의 시행 또한 == 연산자에 의존한다. 따라서 == 연산자의 연산 횟수를 기준으로 시간 복잡도를 결정할 수 있다. 탐색 대상은 ( n => n/2 => n/4 .... ) 으로 절반씩 줄어들면서 진행된다. : 언제까지? 탐색 대상이 1개가 될 때까지 : 그래서 몇번이냐? 모른다! => 객관적 성능 비교가 불가능하다. 해서 이 탐색 대상이 1개가 될 때까지 총 몇번을 시행해야 하는지 정확한 수식을 세울 필요가 있다. 이 추론 과정을 통해 T(n) = K + 1..

프로그래밍 및 언어/자료구조 학습 2024. 10. 18. 03:17

이진 탐색 알고리즘기본적으로 이차원으로 정렬된 배열에서 탐색하는 알고리즘이다.순차 탐색 알고리즘보다 좋은 성능을 보이지만 배열이 정렬되어 있어야 한다는 제약이 있다.이때 정렬은 반드시 오름차순/내림차순 이어야 한다 가 아니라 정해진 기준이 있으면 상관없다. 이러한 배열이 있다고 할 때 3 이라는 값을 찾는 알고리즘을 설계한다고 해보자. 이진 탐색 알고리즘의 기본 골격은 다음과 같다.1. 처음 인덱스 + 끝 인덱스 값을 더한다2. 그 값을 2로 나눈다.3. 해당 결과값을 인덱스로 하여 배열의 값을 탐색한다. 이 골격을 가지고 순서를 다시 생각해본다면1. 처음 인덱스 : 0 / 끝 인덱스 : 8 => 82. 8 / 2 = 43. arr[4] = 9의 과정을 거치게 된다. 만약 여기서 arr[4] 가 우리가 ..

프로그래밍 및 언어/자료구조 학습 2024. 10. 18. 02:27

순차 탐색 알고리즘말 그래도 순차적으로, 정해진 순서에 따라 탐색하는 알고리즘이다. 예를 들어 길이가 5인 배열이 존재하고, 이 중 3 이라는 숫자를 찾는다 가정할 때첫 인덱스부터 마지막 인덱스까지 순차적으로 탐색할 것이다. int LSerach(int ar[], int len, int target){ int i; for(i = 0; iar[] 배열에서 target 과 동일한 인덱스를 찾기 위해 순차적으로 탐색하는 알고리즘이다. 이 코드에서 시간 복잡도를 결정할 연산자는 if(ar[i] == target) 의 '==' 가 된다.Why?코드의 목적 자체가 target 과 값이 같은지 '확인' 하는 알고리즘이다.이 확인에서 가장 중요한 연산자가 시간 복잡도를 결정한다. 여기서 중심이 되는 연산자의 특징 을 ..

프로그래밍 및 언어/자료구조 학습 2024. 10. 17. 23:50

알고리즘의 성능을 분석하기 위해서는 수학에 대한 기초적인 개념을 먼저 요구한다.이 두가지 그래프를 봤을 때 x축이 '데이터의 갯수', y축이 '데이터 연산의 횟수(소요 시간)' 으로 본다. 예를 들어A알고리즘은 데이터 처리 방식이 지수함수 그래프를 그린다.라고 하면 데이터의 갯수에 따라 소요 시간이 급증하는 모양이 될 것이다.= 안좋은 알고리즘 반대로B알고리즘은 데이터 처리 방식이 로그함수 그래프를 그린다.라고 한다면 데이터 갯수가 늘어난다고 해도 소요시간이 크게 증가하지 않는 흐름이 될 것이다.= 사용하기 좋은 알고리즘 이정도의 개념을 깔고 간다. 알고리즘 평가 요소1. 시간 복잡도얼마나 빠른가 / CPU(연산)에 얼마나 부담을 주는가 로 판단한다 2. 공간 복잡도얼마나 메모리를 적게 사용하는가 = 메..

프로그래밍 및 언어/자료구조 학습 2024. 10. 17. 23:22