컴퓨터공학 💻 도서관📚

이진 탐색은 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 해주는 탐색 알고리즘이다   [ 이진 탐색 예시 ]  중간점을 구할 때 소수점 이하는 제거한다.   끝점이 중간점 왼쪽으로 움직여 새로운 끝점이 된다    시작점이 중간점 오른쪽으로 움직여서 새로운 시작점이 된다.      이진탐색 파이썬 예시 1 :  재귀함수 버전   이진탐색 파이썬 예시 2 :  반복문 버전    C++에서는 하나의 배열 정보를 받을 때 1. 포인터를 사용하거나 2. vector 라이브러리를 사용하되  별도로 변수를 카피하지 않고 이미 존재하는 vector 변수의 래퍼런스를 전달해야 한다 만약 &(앰퍼샌드)를 빼주게 되면 이 함수를 호출할 때 기존 vector에 담겨 있던 값을 카피하기 때문에 시간복잡도가..

병합정렬은 데이터를 가장 작은 단위까지 분할한 다음 정렬하면서 다시 병합하는 알고리즘이다. 병합정렬의 시간복잡도는  O(N*logN) 이다.  (약 2천만)  [병합정렬 예시 1]  [병합정렬 예시 2] :  데이터의 총 개수가 홀수인 경우 데이터의 총 개수가 홀수일 경우에는 분할 과정이 남았지만 더 이상 분할할 수 없는 그룹이 존재하게 된다. 이 때는 모든 분할 과정이 끝날 때까지 계속 1개의 원소를 유지합니다.     분할정복 알고리즘 :  하나의 문제를 동일한 유형의 작은 문제들로 분할한 다음에 작은 문제에 대한 결과를 조합해서 큰 문제를 해결하는 방식의 알고리즘분할 정복 알고리즘은 보통 재귀 함수로 구현된다는 특징이 있다.

파이썬에서 제공하는 기본 정렬 라이브러리는  ( sort() )병합 정렬을 기본으로 한 하이브리드 형식의 정렬 알고리즘을 제공하고 있다.        자바에서 내림차순 정렬을 할 때는 Collections 라이브러리의 reverseOrder() 메서드를 사용하기

계수 정렬은 가장 작은 데이터부터 가장 큰 데이터까지의 모든 범위를 포함할 수 있는 크기의 배열을 만들어야 하기 때문에 상대적으로 공간 복잡도가 높지만, 조건만 맞다면 다른 방법보다 더 효율적인 알고리즘이다 계수 정렬은 데이터를 정수 형태로 표현할 수 있을 때 사용 가능하다. 계수 정렬은 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 크기의 리스트를 선언해야 한다       계수 정렬 코드에서 중첩 for문을 보면 바깥쪽 for문이 K 번 돌아가고 안쪽 for문은 수행 횟수가 N 번이므로  시간복잡도는 O(K + N) 이다  계수정렬은 동일한 값을 가지는 데이터가 여러 개 나올 때 효과적이다.

원소가 1개인 경우에는 그대로 종료한다     1. 리스트 슬라이싱과  2. 리스트 컴프리헨션을 활용

comprehension 영단어 뜻은 이해, 이해력, 포용력 이다.List Comprehension 을 이용하면 리스트의 모든 요소를 단 한 줄로 관여할 수 있다   표현식 + for문 형식# case 1result = [int(input()) for i in range()]# case 2result = [list(map(int, input().split())) for i in range(n)]# case 3result = [[0]*n for i in range(n)]  표현식 + for문 + 조건문 형식# case 1n = 10result = [i for i in range(n) if i % 2 == 0]print(result)# 출력 결과 : [0, 2, 4, 6, 8]# case 2left_sid..

data = ['서울', '부산', '대구', '인천', '강릉']   city = data[0:3]print(city)# 출력 결과 : ['서울', '부산', '대구']  city = data[2:5]print(city)# 출력 결과 : ['대구', '인천', '강릉']  city = data[3:]print(city)# 출력 결과 : ['인천', '강릉']  city = data[:2]print(city)# 출력 결과 : ['서울', '부산']  city = data[2:-1] # data[2:4] 와 같다, 마지막은 열린구간이니까 마지막 앞에까지 출력print(city)# 출력 결과 : ['대구', '인천']

퀵 정렬 표준 라이브러리를 이용하는 경우에는 기본적으로 NlogN 을 항상 보장한다    퀵 정렬 동작 예시    아주 중요!!! :  위치가 엇갈릴 때는 '피벗'과 '작은 데이터'의 위치를 서로 변경한다.    퀵 정렬의 시간 복잡도     퀵 정렬은 이미 정렬된 배열에서 최악의 시간 복잡도를 가진다(우측에서부터 0보다 작은 데이터가 없기 때문이다)그래서 결국 위치가 엇갈려서 0이 자기 자신과 위치를 바꾸는 상황이 된다그리고 0과 나머지 숫자들의 묶음으로 분할이 된다그 후 계속 가장 작은 수와 나머지 숫자들의 묶음으로 분할이 되서 시간 복잡도가 O(N^^2) 이다.