교육5주차(2)

bubble Sort(버블정열)

• 인접한 원소들을 비교
• 위치교환
• 큰값(작은값)을 통해 버블처럼 서서히 상단(하단)으로 이동하는 과정
• 원리
  • 초기상태
  • 비교 및 교환
  • 반복
  • 완료 조건

• 구현하기가 쉬움
• 시간복잡도 최악, 평균 (O(n^2))
• 공간복잡도(O(1)) 제자리정렬: 추가적인 공간이 필요
• 안정성: 동일한 값을 가진 원소의 상대적인 순서가 정렬 후에도 유지되므로
• 효율성: 대규모 데이터셋에서는 비효율적임

def bubble_sort(arr):
    n= len(arr)
    for i in range(n):
	    swapped = Fasle
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j + 1], arr[j] = arr[j], arr[j+1]
								swapped = True
						if not swapped:
							break

Selection Sort(선택정렬)

• 전체 배열을 순회하며 각 위치에 올바른 값을 찾아서 배치
• 배열의 모든 요소가 올바르게 정렬될 때까지 반복
• 원리
  • 최속밧 탐색
  • 스왑
  • 다음 위치로 이동
  • 반복
• 비교 횟수 : 크기가 n일때 약 n(n-1)/2 시간복잡도 O(n^2)
• 안정성 : 안정적인 정렬 방법이 아니다
• 인플레이스 정렬 알고리즘

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
         min_idx = i
         for j in range(i+1, n):
              if arr[j] < arr[min_idx]:
                   min_idx = j
         arr[i]. arr[min_idx] = arr[min_idx], arr[i]
    return arr

Insertion Sort(삽입정렬)

• 각 반복에서 하나의 데이터를 적절한 위치에 삽입함으로써 작업을 수행
• 안정성: 안정적인 방법
• 공간복잡도 : O(1)
• 시간복잡도 : O(n), O(n^2), 역순으로 정열되어있거나 무작위 일때는 느림

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
         min_idx = i
         for j in range(i+1, n):
              if arr[j] < arr[min_idx]:
                   min_idx = j
         arr[i]. arr[min_idx] = arr[min_idx], arr[i]
    return arr

Heap Sort(힙정열)

• 선택 정열을 개선한 방법으로 완전 이진트리를 이용한 배열방식
• 시간복잡도 : O(n logn)
• 공간복잡도 : O(1)
• 안정성 : 불안정정룔
• 효율성 : 빠름

def heapify(arr, n, i):
    largest = i  # 루트를 최대로 가정
    l = 2 * i + 1  # 왼쪽 자식
    r = 2 * i + 2  # 오른쪽 자식

    # 왼쪽 자식이 루트보다 크다면
    if l < n and arr[l] > arr[largest]:
        largest = l

    # 오른쪽 자식이 현재 최대값보다 크다면
    if r < n and arr[r] > arr[largest]:
        largest = r

    # 최대값이 루트가 아니라면
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 교환

        # 교환된 루트에 대해 다시 힙 구성
        heapify(arr, n, largest)

• 성능보장
• 인플레이스 정열

Quick Short

• 분발 정복
• 피벗을 기준으로 사용 , 피벗보다 작으면 왼쪽, 크면 오른쪽
• 원리

  • 피벗 선택

  • 분할

  • 정복

  • 결합

    def quick_sort(arr):
    	if len(arr)<= 1:
    		return arr
    	mid= arr[len(arr) // 2]
    	left= [x for x in arr if x < mid]
    	pivot= [x for x in arr if x == mid]
    	right= [x for x in arr if x > mid]
    	return quick_sort(left) + pivot + quick_sort(right)

• 시간복잡도 : O(n logn), O(n^2)

Merge Sort

• 병합 정렬
• 시간복잡도 : O(n logn)
• 원리
  • 분할 : 부분 리스트 크기가 1이 될 때까지 분할
  • 정복
  • 결함
• 스택 크기가 큰 데이터 정열 시 제한적일 수있음
• 추가적 메모리 필요

Radix Sort(기수 정열)

• 비교가 아닌 정렬 방식
• 데이터의 자릿수나 문자의 위치
• 카운팅 정열, 버킷 정열
• 시간복잡도 : O(nk)

탐색알고리즘

Binary Search(이진탐색)

• 특정한 값을 효율적으로 찾는 탐색알고리즘
• 분할정복
• 시간복잡도 : O(log n)
• 간결함

Brute Force

• 사용
  • 비밀번호 크래킹
  • 순열과 조합
  • 체스문제
  • 그래프문제
• 시간 복잡도가 문제

BFS

• 가까운 노드부터 차례대로 탐색
• 노드사이의 최단 경로
• 그래프의 연결성

DFS

• 최단 경로 찾기
• 메로리 사용량이 비교적많음
• 친구 추천기능
• 미로탐색
• 원리
  • 시작노드를 스택에 삽입하고 방문 처리
  • 스택의 최상단 노드에서 방문하지 않은 인접노드
  • 2번의 과정을 더 이상 수행 할 수 없을때까지 반복
• 시간복잡도 : O(V + E)
• 무한탐색에 빠질수 있음

Dijkstra

• 한 정점에서 다른 모든 정점까지 최단 경로 찾기
• 탐욕적 방법을 기초로함
• 원리
  • 초기화
  • 거리 업데이트
  • 정점 선택
  • 종료 조건

벨만 - 포드 알고리즘

• 음의 가중치 가 있는 간선이 포함된 그래프
• 특정상황에 맞게 사용

Dynamic Programming

• 동적 계획법
• 복잡한 문제를 효율적으로 해결하기 위한 알고리즘
  • 최적 부분 구조
  • 중복되는 부분 문제
• 상향식 접근법
• 하향식 접근법

Union-Find

• 집합들의 합집합과 같은 집합연산에 사용
• 경로 압축
• 랭크 기반 합치기

자료참고

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
https://blog.naver.com/ndb796/221227934987
https://velog.io/@https00200/algorithm-radixSort
https://great-park.tistory.com/134
https://blog.naver.com/ndb796/221230967614