[Algorithm] 문제를 해결하기 위한 절차

김윤환·2024년 7월 27일

UpstageAILab 국비지원 업스테이지패스트캠퍼스 패스트캠퍼스 패스트캠퍼스AI부트캠프 패스트캠퍼스업스테이지부트캠프 패스트캠퍼스업스테이지에이아이랩

알고리즘이란?

특정 문제를 해결하기 위해 수행되는 절차나 단계

알고리즘은 문제를 해결하기 위한 단계적인 절차나 방법을 말합니다. 컴퓨터 과학에서 알고리즘은 특정 작업을 수행하기 위해 필요한 일련의 명령어로 구성되어 있으며, 프로그래밍 언어를 통해 구현됩니다. 효율적인 알고리즘은 적은 자원을 사용하여 빠르게 문제를 해결하는 데 중점을 둡니다.

알고리즘의 조건

일반적으로 알고리즘은 입력, 출력, 명확성, 유한성, 효율성 등의 조건을 만족하여야 합니다.

입력: 외부로부터 입력되는 자료가 0개 이상 존재합니다.
출력: 적어도 1개 이상의 결과가 출력됩니다.
명확성: 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 합니다.
유한성: 유한 번의 명령어를 수행 후 종료되어야 합니다.
효율성: 모든 과정은 명백하게 실행 가능한 것이어야 합니다.

알고리즘의 기술 방법

자연어 기술 방법

말이나 글을 이용하여 표현하는 방법

우리가 일상적으로 사용하는 말이나 글을 이용하는 방법입니다. 자연어 기술 방법은 말과 글이 지니는 애매모호한 성질 때문에 알고리즘의 조건 중 명확성을 지키지 못할 가능성이 있습니다. 다음 예는 두 변수의 값을 더해서 그 결과를 출력하는 알고리즘을 자연어 기술 방법으로 표현한 것입니다.

정수값 5를 A 변수에 대입한다.
정수값 4를 B 변수에 대입한다
A 변수의 값과 B변수의 값을 더해서 C변수에 대입한다.
C 변수의 값을 출력한다

순서도 표현 방법

기호와 그림을 사용하여 표현한는 방법

알고리즘의 처리 순서를 알기 쉽도록 약속된 기호를 사용 하여 그림으로 나타낸 것을 순서도(flowchart)라고 하며, 순서도를 그릴 때 많이 쓰이는 기호는 다음과 같습니다.

유사코드(Pseudo-code)

논리와 흐름을 프로그래밍 언어와 유사하게 표현하는 방법

자연어 기술 방법과 그래픽적인 표현 방법을 쓰는 것보다 좀더 개선된 방법으로 의사 코드 (pseudo code) 기술 방법이 있습니다. 의사 코드는 자연어 기술 방법을 보다 간략화한 것으로서 프로그래밍 언어의 문법을 적용하여 쉽게 프로그래밍 언어로 표현할 수 있다는 장점이 있으며, 언어 독립적인 특징과 기계 독립적인 특징이 있습니다.

program ADDING
A <- 5
B <- 4
	C <- A + B
print(C)
end ADDING

프로그램코드

알고리즘을 실제 프로그래밍 언어로 구현한 코드입니다.

알고리즘을 프로그램 코드로 설명하는 방법은 알고리즘의 동작을 명확하고 정확하게 이해할 수 있게 해줍니다. 이를 통해 알고리즘의 논리뿐만 아니라 구체적인 구현 방법까지 명확히 알 수 있습니다. 코드로 구현된 알고리즘은 정확성을 보장하며, 실행 가능하여 실제 결과를 확인할 수 있습니다.

# Python Code
a = 5  
b = 4
c = a + b
print(c)

알고리즘 종류

알고리즘의 종류는 굉장히 많지만, 이번 콘텐츠에서는 정렬 알고리즘과 탐색 알고리즘에 대하여 소개하겠습니다.

정렬 알고리즘

데이터를 일정한 순서로 정렬하는 알고리즘

대표적인 정렬 알고리즘으로는 버블 정렬, 삽입 정렬, 선택 정렬, 퀵 정렬, 병합 정렬 등이 있습니다. 이 중 대표적으로 버블정렬과 선택 정렬에 대해서 알아보겠습니다

선택 정렬

선택 정렬은 가장 작은(또는 큰) 요소를 찾아 첫 번째 요소와 교환하고, 그 다음 작은 요소를 찾아 두 번째 요소와 교환하는 과정을 반복하여 배열을 정렬하는 알고리즘

선택 정렬은 배열의 첫 번째 요소부터 시작하여 가장 작은 요소를 찾아 첫 번째 요소와 교환합니다. 그 다음 두 번째 요소로 이동하여 다시 가장 작은 요소를 찾아 교환하는 과정을 배열의 끝까지 반복합니다. 이 과정에서 이미 정렬된 부분은 제외하고 나머지 부분에서 가장 작은 요소를 찾아 교환합니다. 데이터 양이 많을 때 비효율적일 수 있습니다.

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

버블 정렬

인접한 두 요소를 비교하여 교환하는 과정을 반복하여 배열을 정렬하는 알고리즘

버블 정렬은 인접한 두 요소를 비교하여 잘못된 순서일 경우 교환하는 방식으로 동작합니다. 이는 리스트가 정렬될 때까지 반복됩니다. 배열의 첫 번째 요소와 두 번째 요소를 비교하여 더 큰 요소를 뒤로 보내고, 두 번째 요소와 세 번째 요소를 비교하여 교환하는 과정을 반복합니다. 이 과정을 배열의 끝까지 반복하여 가장 큰 요소가 마지막에 위치하게 됩니다. 그런 다음 다시 첫 번째 요소부터 시작하여 반복합니다. 이 과정을 배열이 완전히 정렬될 때까지 반복합니다.

# python code
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

퀵 정렬 (Quick Sort)

분할 정복 기법을 이용하여 피벗을 기준으로 배열을 분할하고, 각 부분 배열을 재귀적으로 정렬하는 알고리즘

퀵 정렬은 배열에서 하나의 요소를 피벗(pivot)으로 선택하고, 피벗보다 작은 요소들은 피벗의 왼쪽에, 큰 요소들은 피벗의 오른쪽에 위치시키는 방식으로 동작합니다. 이 과정을 통해 배열을 두 부분으로 분할한 후, 각 부분 배열을 다시 퀵 정렬을 사용하여 정렬합니다.

def quick_sort(arr):
    if len(arr) <= 1:  # 배열의 길이가 1 이하이면 이미 정렬된 상태
        return arr
    
    pivot = arr[len(arr) // 2]  # 피벗을 배열의 중간 값으로 선택
    left = [x for x in arr if x < pivot]  # 피벗보다 작은 요소들
    middle = [x for x in arr if x == pivot]  # 피벗과 같은 요소들
    right = [x for x in arr if x > pivot]  # 피벗보다 큰 요소들
    
    # 분할된 배열을 다시 퀵 정렬을 사용하여 정렬하고 병합
    return quick_sort(left) + middle + quick_sort(right)

탐색 알고리즘

특정 데이터를 찾는 알고리즘

대표적인 탐색 알고리즘으로는 순차 탐색, 이진 탐색, 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)이 대표적입니다.

순차 탐색

배열의 처음부터 끝까지 순차적으로 탐색하여 원하는 값을 찾는 알고리즘

선형 탐색은 배열의 첫 번째 요소부터 시작하여 마지막 요소까지 순차적으로 하나씩 비교하여 원하는 값을 찾습니다. 원하는 값을 찾으면 탐색을 종료하고, 배열의 끝까지 탐색해도 값을 찾지 못하면 값이 없음을 반환합니다. 이 알고리즘은 배열이 정렬되지 않은 경우에도 사용할 수 있습니다.

def linear_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

# 예시 사용
array = [64, 25, 12, 22, 11]
target = 22
result = linear_search(array, target)
if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found in array")

이진 탐색

정렬된 배열에서 중간 요소를 기준으로 탐색 범위를 반씩 줄여가며 원하는 값을 찾는 방식

이진 탐색은 정렬된 배열에서만 사용할 수 있는 효율적인 탐색 알고리즘입니다. 배열의 중간 요소를 피벗으로 선택하여 찾고자 하는 값과 비교합니다. 찾고자 하는 값이 피벗보다 작으면 왼쪽 부분 배열을, 크면 오른쪽 부분 배열을 대상으로 다시 중간 값을 선택하여 비교합니다. 이 과정을 반복하여 원하는 값을 찾을 때까지 탐색 범위를 절반으로 줄여갑니다.

# python code
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


```

효율적인 알고리즘이란?

리소스를 적게 사용하면서 전체 실행시간을 짧게 하는 알고리즘

처리할 데이터 양이 급속히 증가하지만 여전히 빠른 프로그램을 선호하므로, 시간 효율성과 공간 효율성을 가지는 알고리즘이 필요합니다. 알고리즘은 특정 문제를 해결하기 위해 다양한 접근 방식과 방법을 사용할 수 있으며, 효율적인 알고리즘을 설계하는 것은 컴퓨터 과학에서 매우 중요한 과제입니다. 각 문제에 맞는 최적의 알고리즘을 선택하는 능력은 소프트웨어 개발자에게 필수적인 기술입니다.