본문 바로가기

제로베이스/Algorithm

 (4)
4. 삽입정렬 삽입 정렬이란? 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘. 1부터 5까지 총 5개의 숫자가 들어있는 배열에 있다고 가정하자. [2, 1, 5, 4, 3] 맨 처음에는 첫번 째 2개의 값만 정렬 범위에 포함시키고 생각한다. 앞에 있는 값 2는 뒤에 있는 값 1보다 작기 때문에 서로 자리를 바꿔준다. [2, 1] : 2 > 1 => swap [1, 2] * * 그 다음에는 기존의 정렬 범위에 한칸 확장하여 세번 째 값을 추가시키고 생각해본다. 기존 정렬 범위에서 가장 큰 값인 2와 새롭게 추가된 5를 비교하면 자리를 바꿀 필요가 없다는 것을 알 수 있다. 기존에 정렬 범위에 있던 두 개의 값은 이 전 패스에서 이미 정렬되어 있기 ..
3. 버블정렬 버블정렬이란? 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘이다. nums = [10,2,7,21,0] length = len(nums) - 1 for i in range(length): for j in range(length - i): if nums[j] > nums[j+1]: # 만약 앞에 있는게 뒤에 있는 것보다 크면 ## 일반적인 순서 변경 방법 temp = nums[j] nums[j] = nums[j+1] nums[j+1] = temp # 파이썬에서 제공되는 방법 nums[j], nums[j+1] = nums[j+1], nums[j]
2. 이진검색 이진검색이란? 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다. datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] print(f"datas: {datas}") print(f"datas length: {len(datas)}") searchData = int(input("찾으려는 숫자 입력: ")) searchResultIdx = -1 startIdx = 0 endIdx = len(datas) - 1 midIdx = (startIdx + endIdx) // 2 midVal = datas[midIdx] while searchData = datas[0]: if searchData > midVal: startIdx = midIdx midIdx = (star..
1. 선형검색 선형검색이란? 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는 것. 인덱스 0부터 9까지 순차적으로 검색한다. 보초법 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다. datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4] print(f"datas: {datas}") print(f"datas length: {len(datas)}") searchData = int(input("찾으려는 숫자 입력: ")) searchResultIdx = -1 datas.append(searchData) n = 0 while True: if datas[n] == searchData: if n != len(datas) - 1: searchResultIdx = n break n..

티스토리툴바