자료구조2 2021.2.25 TIL : [자료구조] 순차 탐색과 이진 탐색(Sequential Search and Binary Search) 순차 탐색(Sequential Search)이란 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법이다. 데이터 정렬 유무에 상관 없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점에서 O(N)의 시간 복잡도를 가진다. 순차 탐색 코드는 여기에서 확인할 수 있다. 이진탐색(Binary Search)은 배열 내부 데이터가 이미 정렬 되어 있는 상황에서만 사용 가능한 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진 탐색은 한 번 확인할 때마다 보아야 하는 원소의 개수가 절반씩 줄어든다는 점에서 탐색 시간에서 O(log N)의 시간 복잡도를 가진다. 여기에서 이진 탐색 코드를 확인할 수 있다. 2021. 2. 26. 2021.2.20 TIL : [자료구조] 선택 정렬과 삽입정렬 선택 정렬이란 데이터 중에 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법이다. 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산으로 O(N^2)의 시간 복잡도를 가진다. 즉, 의사코드를 적어보면 다음과 같다. C언어로 구현한 선택 정렬 코드는 여기에서 확인할 수 있다. for(int i = 0; i < N; i++) i 번째 숫자부터 N번째 숫자까지 모두 확인하여 가장 작은 수를 찾아낸다. 가장 작은 숫자를 i번째 숫자와 바꾼다. 삽입 정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법으로, 들어갈 위치를 선택하는 데에 N번, 선택하는 횟수가 N번이니까 O(n^2)의 시간 복잡도를 가진다. 즉, i가 0에서 N까지 1씩 증가하는 수라고 할 때, i번째 자리의 값이 i-1번째 값보.. 2021. 2. 20. 이전 1 다음
