Study Blog

선형 검색의 종료 조건1) 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 -> 검색 실패2) 검색할 값과 같은 원소를 찾는 경우 -> 검색 성공! 배열 a가 있을 때 검색하는 프로그램은 다음과 같이 나타낼 수 있다.i = 0while True: if i == len(a): # 검색 실패 if a[i] == key: # 검색 성공(찾은 원소의 인덱스는 i) i += 1 선형 검색 알고리즘 코드 1 (while)# while 문으로 작성한 선형 검색 알고리즘from typing import Any, Sequencedef seq_search(a: Sequence, key: Any) -> int: # 시퀀스 a가 있고 key는 아무 자료형, 결과는 int로 반환한다. ..

파이썬에서는 배열을 리스트와 튜플로 구현할 수 있다.리스트- 원소를 변경할 수 있는 뮤터블 list형 객체- 연산자 [ ] 안에 원소를 쉼표(,)로 구분하여 표기하여 생성- 원소 없이 [ ] 만 사용하면 빈 리스트를 생성list01 = [] # [] 빈 리스트list02 = [1, 2, 3] # [1, 2, 3]list03 = ['A', 'B', 'C', ] # ['A', 'B', 'C'] 맨 마지막 원소에 쉼표를 써도 됨list04 = list() # [] 빈 리스트list05 = list('ABC') # ['A', 'B', 'C'] 문자열의 각 문자로부터 원소를 생성l..

단순 삽입 정렬이란?- 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘- 원소의 비교 횟수와 교환 횟수는 모두 n² / 2번 단순 삽입 정렬의 진행 과정1. 두 번째 원소인 4부터 주목한다. 4는 6보다 앞쪽에 위치해야 하기때문에 맨 앞에 삽입하고 6을 오른쪽으로 옮긴다.2. 세 번째 원소인 1에 주목한다. 1은 4보다 앞쪽에 위치해야 하기때문에 맨 앞에 삽입하고 4와 6을 오른쪽으로 옮긴다.3. 단순 삽입 정렬은 위와 같이 '아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입' 하는 과정을 반복한다.  단순 삽입 정렬은 다음과 같이 종료 조건이 두 가지이다.1. 정렬된 배열의 왼쪽 끝에 도달한 경우 -> 가장 값이 작은 것이다.2. tmp보다 작거나 키값이 ..

선택 정렬이란?- 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘- 원솟값을 비교하는 횟수: (n² - n) / 2번- 시간복잡도 측면에서 퀵 정렬과 같은 다른 정렬방법이나 파이썬 내장 라이브러리를 사용한 정렬 방법보다 비효율적 선택 정렬의 수행 과정1. 선택 정렬은 첫 번째 원소를 두 번째 원소부터 마지막 원소까지 차례대로 비교하여 가장 작은 원소를 찾아 첫 번째에 놓음2. 두 번째 원소를 세 번째 원소부터 마지막 원소까지와 차례대로 비교, 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복선택 정렬은 위와 같은 과정으로 수행된다.다시 한 번 간단히 정리하면, 선택 정렬은 아직 정렬하지 않은 범위에서 값이 가장 작은 원소를 선택, 아직 정렬하지 않은 부분의 맨 앞 ..

셰이커 정렬이란? 버블 정렬을 개선한 알고리즘으로, 양방향 버블 정렬, 칵테일 정렬, 칵테일 셰이커 정렬이라고도 부른다. 지난 글(https://vibeee.tistory.com/29)에서 버블 정렬로 3가지 코드를 살펴보았다.하지만 가장 큰 값이 맨 앞에 있는 경우 3가지 코드 모두 비효율적인 정렬 과정을 수행하는 것을 알 수 있었다. 다음 코드에서는 이 부분을 셰이커 정렬로 개선한 코드를 살펴본다.from typing import MutableSequencedef shaker_sort(a: MutableSequence) -> None: left = 0 right = len(a) - 1 last = right while left a[j]: # 앞의 값이 뒤보다 큰 경우에 교환 ..