남민우의 공부 블로그

이전 #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

컴퓨터 공학의 기초 지식을 재학습하던 중, 자료구조의 중요성과 사용 가치를 굳건히 하기 위해 학습한다.자료구조란 무엇인가"프로그램이란 데이터를 표현하고 그렇게 표현된 데이터를 처리 하는 것" 이 때 '데이터를 표현' 하는 것을 자료구조, '표현된 데이터를 처리' 하는 것을 알고리즘 이라고 볼 수 있다.이 데이터를 표현 에는 저장 의 의미가 내포되어 있다.따라서 자료구조란 결국 데이터를 저장하는 컴퓨터 공학이다 라고도 이해할 수 있다.더보기데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미 한다고도 말한다.https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0 자료구조의 분류 총 4가지의 큰 타입,..

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