코딩하는 진주네카라

Information 거품 정렬 또는 버블 정렬(bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다. 버블 정렬 bubble sort 인접한 인덱스의 값을 순서대로 비교하여 큰 숫자를 마지막 끝으로 옮기는 알고리즘 구현 1 nums = [10, 8, 4, 21, 0] def bubbleSort(arr): length = len(arr) - 1 for i in range(length): for j in range(length - i): if arr[..

Information 순위는 수를 비교해 차례, 순서, 서열 등을 나타내는 위치이다. 순위 Ranking 복잡한 정보를 평가하는 것이 가능하다. 구현 1 import random datas = random.sample(range(50, 101), 5) ranks = [0 for i in range(5)]# 5번 반복해 값을 0으로 초기화 for idx, val1 in enumerate(datas): for val2 in datas: if val1 < val2: ranks[idx] += 1 print(f'점수: {datas}') print(f'순위: {ranks}') for idx, val in enumerate(datas): print(f'점수: {val} \t 순위: {ranks[idx] + 1}') ..

recursive binary search 재귀 함수를 사용한 이진 검색을 해봅니다. 예시 1 리스트를 오름차순으로 정렬하여 '7'를 검색하고 위치(인덱스) 출력하기 nums = [4, 21, 10, 5, 0, 17, 7, 25, 11, 50, 49] def binarySearch(arr, sta, end, key): arr.sort() if end >= sta: mid = sta + (end - sta) // 2 if key == arr[mid]: return mid elif key < arr[mid]: return binarySearch(arr, sta, mid - 1, key) else: return binarySearch(arr, mid + 1, end, key) else: return -1 pr..

Information 이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 이진 검색 이진 탐색 Binary search 정렬된 리스트에서 중앙값의 크고 작음을 이용해 key가 포함된 절반만 사용하는 방법 나머진 무시! key와 중앙값을 비교한다..

Sentinel Linear Search 보초법을 사용한 선형 검색을 적용해 보았다. 예시 1 리스트에서 가장 앞에 있는 특정 숫자 검색하고 위치(인덱스) 출력하기 def sentinelSearch(arr, key): arr.append(key) n = 0 answer = 0 while True: if arr[n] == key: if n != len(arr) - 1: answer = n break else: answer = -1 break n += 1 return answer print(sentinelSearch(nums, 10))# 출력 2 2 리스트에서 특정 숫자 모두 검색하고 각각의 위치(인덱스)와 검색 개수 출력하기 def sentinelSearchAll(arr, key): searchIdx = ..

Information 순차 검색 알고리즘(sequential search algorithm), 또는 선형 검색 알고리즘(linear search algorithm)은 리스트에서 특정한 값을 찾는 알고리즘의 하나다. 이것은 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 것이다. 검색할 리스트의 길이가 길면 비효율적이지만, 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있다. 선형 검색 순차 검색 선형으로 나열되어 있는 데이터를 순차적으로 검색하여 원하는 값을 찾음 검색 성공 또는 검색 실패 구현 1 nums = [0, 4, 2, 1, 8, 5, 7, 3, 9, 6] def sequentialSearch(arr, key): n = 0 a..

깊이 우선 순회 DFS(Depth First Search) 스택(Stack) 물건을 쌓아 올림 LIFO 구조 나중에 들어온 것이 먼저 나간다. last in, first out DFS 기본 깊이 우선 순회(DFS)는 트리 아래로 내려 갈 수 있으면 항상 아래로 내려가고, 더 이상 아래로 내려갈 화살표가 없는 경우에만 옆에 있는 화살표로 넘어간다. + 코드 구현