IT : 기초라는 뿌리

더보기 출처 : 윤성우의 열혈 자료구조 빅-오 표기법(Big-oh Notation) 데이터의 수 n과 그에 따른 시간 복잡도 함수 T(n)을 정확히 그리고 오차 없이 구하는 것은 대부분의 경우 쉽지 않다. 따라서 오차를 허용하지 않으면 ‘+1을 넣는게 맞다 아니다’로 투닥일 것이다. ex) T(n) = 2n + 1.234..... 이다!!! 하지만 여기서 중점적인 한마디는 그냥 “빅-오만 따지자“ 이다. 도대체 이 빅-오(Big-oh Notation)란 무엇인가? - O가 매우 크다? 사실상 맞다고 한다. 빅-오라는 것은 함수 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것인데, 이때 사용되는 표기법에 대문자 O 즉, 큰 O를 사용하기 때문에 빅-오라고 한다. 설명을 위한 함수식 기본 함수 형태..

더보기 출처 : 윤성우의 열혈 자료구조 이진 탐색 알고리즘을 다시 살펴봅시다. - 이진 탐색 알고리즘의 탐색 시작과 끝 위치의 변화 - 시작위치 인덱스가 first, 탐색 마지막 위치 인덱스가 second - 이진 탐색 알고리즘이 진행되면 first와 second는 거리를 줄여나가고 있다. * first : 왼쪽, last : 오른쪽 Q. 이진 탐색 알고리즘은 언제까지 계속되어야 할까? ??? : first와 last가 만날때까지 계속 되어야 합니다. first와 last가 만나면 탐색 대상이 존재하지 않음을 뜻하지 않나요? * 잘못된 생각이다. first와 last가 만났다는 것은 탐색의 대상이 아직 하나 남아있음을 뜻한다. 따라서 이진 탐색은 first < last, first==last인 상황에서도..

더보기 출처 : 윤성우의 열혈자료구조 이진 탐색 알고리즘은 순차 탐색보다 훨씬 좋은 성능을 보이는 알고리즘 입니다. 이진 탐색 알고리즘을 적용하기 위해서는 다음과 같은 조건이 성립되어야 합니다. " 배열안의 요소(데이터)들이 정렬되어 있어야 한다. " 해당 알고리즘은 정렬된 데이터가 아니면 적용이 불가능합니다. (정렬의 기준 및 방식과는 관계없습니다.) 때문에 이진 탐색 알고리즘보다 성능이 덜한 순차 탐색 알고리즘도 우리에겐 유용한 알고리즘 입니다. 예제를 보겠습니다. 우선 길이가 9인 배열에 다음과 같이 정렬된 상태로 데이터가 저장되어 있습니다. (배열의 이름은 arr) 해당 배열의 이진 탐색 알고리즘의 첫 번째 시도는 다음과 같습니다. 1. 배열 인덱스의 시작과 끝은 각각 0과 8입니다. 2. 0과 ..

더보기 윤성우의 열혈자료 구조를 토대로 작성한 글입니다. "평균의 경우 시간 복잡도를 계산하는것은 쉽지 않구나! 라는 정도만 느끼자." 평균적인 경우의 시간복잡도를 구할때의 가정 2가지 입니다. 1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정 2. 배열의 첫 요소부터 마지막 요소까지 탐색 대상이 존재할 확률은 동일하다. 가정 1부터 연산횟수를 계산해 보겠습니다. (존재하는 경우와 존재하지 않는 경우) * 배열에 탐색 대상이 존재하지 않는 경우 데이터의 수가 n개일 때, 총 n번의 비교연산을 진행해야 합니다 (총 n 번의 비교연산이 끝나야 비로소 탐색 대상이 존재하지 않음을 판단할 수 있다.) 따라서 배열에 탐색 대상이 존재하지 않는 경우의 연산횟수는 다음과 같습니다. > 탐색 대상이 존재하..

순차탐색(Sequential Search) = 선형 탐색(Linear Search) 글에 인용한 정보 서적 : 윤성우의 열혈자료구조 사이트 출처 : https://blog.hexabrain.net/245, https://inpages.tistory.com/143 데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘입니다. 이 순차 탐색은 데이터를 따로 조작할 필요가 없어 단순하지만 비효율적이라는 단점을 지니고 있습니다. 오늘은 순차 탐색 알고리즘에서 시간복잡도 분석과 핵심요소를 알아볼까 합니다. 위에서 간단하게 소개했듯이 맨 앞에서부터(0번째 인덱스부터) 순서대로 탐색을 진행하는 알고리즘 입니다. 언어는 C언어 이고 아래 코드로 먼저 볼..