알고리즘

[Sam1000won]

Algorithm

1. Algorithm 개념

• 알고리즘은 어떤 문제를 해결하기 위한 정해진 일련의 절차나 방법을 공식화한 형태

2. Algorithm 특성

• 입력
• 출력
• 명확성
• 유한성
• 유효성

알고리즘 기법

1. 분할과 정복

• 버블 정렬이 있음

• 1. 분할(Divide):
     주어진 배열을 반으로 나눕니다. 이 과정을 배열의 크기가 1이 될 때까지 재귀적으로 반복합니다.
     예를 들어, 배열 [38, 27, 43, 3, 9, 82, 10]를 나누면 다음과 같습니다:
     [38, 27, 43]와 [3, 9, 82, 10]으로 나눕니다.
     다시 [38], [27, 43]와 [3, 9], [82, 10]으로 나눕니다.
     최종적으로는 각각의 요소가 하나씩 남게 됩니다.
• 2. 정복(Conquer):
     나눠진 배열을 정렬합니다. 이때 병합 과정에서 두 개의 정렬된 배열을 하나의 배열로 합치는 방식으로 진행합니다.
     예를 들어, [27]와 [43]를 병합하면 [27, 43]가 됩니다. 이 과정을 반복하여 모든 배열을 정렬하고 병합합니다.
• 3. 병합(Merge):
     두 개의 정렬된 배열을 비교하며 하나의 정렬된 배열로 만듭니다.
     예를 들어, [27, 43]와 [38]를 병합할 때:
     27이 38보다 작으므로 27을 결과 배열에 추가하고, 다음은 43와 38를 비교합니다.
     38이 43보다 작으므로 38을 추가합니다. 마지막으로 남은 43을 추가합니다.
     최종적으로는 정렬된 배열이 됩니다.

• 예제 코드

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 중간 인덱스
        left_half = arr[:mid]  # 왼쪽 절반
        right_half = arr[mid:]  # 오른쪽 절반

        merge_sort(left_half)  # 왼쪽 절반 재귀 호출
        merge_sort(right_half)  # 오른쪽 절반 재귀 호출

        # 두 절반을 병합
        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 남은 요소들 추가
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

2. 동적계획법

• 예제로 피고나치 수열이 있음.

def fibonacci(n):
    # DP 테이블 초기화
    dp = [0] * (n + 1)
    dp[1] = 1  # F(1) 초기화

    # DP 테이블을 채우기
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

3. 탐욕법

• 간단한 예제로 동전 바꾸기가 있다.

def min_coins(coins, amount):
    # 동전의 개수를 세기 위한 변수
    count = 0
    # 금액을 내기 위해 사용한 동전의 리스트
    used_coins = []

    # 동전을 큰 순서대로 정렬
    coins.sort(reverse=True)

    for coin in coins:
        while amount >= coin:  # 현재 동전으로 거슬러 줄 수 있는 만큼
            amount -= coin
            count += 1
            used_coins.append(coin)

    return count, used_coins

4. 백트래킹

• 재귀적 접근법으로 N- Queens 가 있다.

def print_solution(board):
    for row in board:
        print(" ".join("Q" if x else "." for x in row))
    print()

def is_safe(board, row, col):
    # 열 체크
    for i in range(row):
        if board[i][col] == 1:
            return False

    # 대각선 체크 (왼쪽 위)
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    # 대각선 체크 (오른쪽 위)
    for i, j in zip(range(row, -1, -1), range(col, len(board))):
        if board[i][j] == 1:
            return False

    return True

def solve_n_queens_util(board, row):
    if row >= len(board):
        print_solution(board)
        return

    for col in range(len(board)):
        if is_safe(board, row, col):
            board[row][col] = 1  # 퀸을 놓음
            solve_n_queens_util(board, row + 1)  # 다음 행으로 재귀 호출
            board[row][col] = 0  # 백트래킹

def solve_n_queens(n):
    board = [[0] * n for _ in range(n)]  # N x N 체스판 초기화
    solve_n_queens_util(board, 0)

• 장점: 모든 가능한 해를 탐색할 수 있으며, 문제의 해가 존재하는지 여부를 확인할 수 있습니다. 복잡한 조합 문제를 해결하는 데 유용합니다.
• 단점: 경우의 수가 많을 경우 비효율적일 수 있습니다. 따라서 가지치기(Pruning) 기법을 통해 불필요한 탐색을 줄이는 것이 중요합니다.

3. 시간 복잡도

• O(1)

• 상수형 복잡도
• 자료 크기와 무관하게 항상 같은 속도로 작동
• 알고리즘 수행 시간이 입력 데이터 수와 관계 없이 일정
• Ex) 해시 함수

• O(log2 n)

• 로그형 복잡도
• 문제를 해결하기 위한 단계의 수가 log2 n 번 만큼 수행 시간을 가짐
• Ex) 이진 탐색

• O(n)

• 선행 복잡도
• 입력 자료를 차례로 하나씩 모두 처리
• 수행 시간이 자료 크기와 직접 관계로 변형 정비례
• Ex) 순차 탐색

• O(n log2 n)

• 선행 로그형 복잡도
• 문제를 해결하기 위한 단계의 수가 nlogn번만큼의 수행 시간을 가짐
• Ex) 퀵, 합병(병합)정렬, 힙 정렬

• O(n**2)
• 제곱형 주요 처리 루트 구조가 2중인 경우
• n크기가 작을때 n2이 nlog2n보다 빠를 수 있음

• Ex) 거품,삽입,선택 정렬

4. Algorithm 설명

• 해싱 함수( Hashing Function)
  • 제산법
  • 제곱법
  • 숫자 분석법
  • 폴딩법
  • 거수변환법
  • 무작위방법