[F-Lab 페이백 모각코 43일차] (CS) CHAPTER 7 알고리즘

문제 해결을 위한 효율적인 방법과 절차

학습 목표

• 알고리즘의 의미와 조건을 알아본다.
• 선택 정렬, 삽입 정렬, 버블 정렬 등 정렬 알고리즘의 동작 과정을 알아본다.
• 선형 탐색, 이진 탐색 등 탐색 알고리즘의 동작 과정을 알아본다.
• 피보나치 수열, 하노이 탑, 퀵 정렬 등 재귀 알고리즘의 동작 과정을 알아본다.

TIL

• 알고리즘

 

 

알고리즘의 개요

• 알고리즘의 개념: 문제를 해결하기 위한 명확하고 구체적인 절차나 방법

정렬 알고리즘

• 선택 정렬
  • 선택 정렬의 동작 과정: 주어진 배열에서 최솟값을 찾아 첫 번째 위치와 교환, 그 다음으로 남은 배열에서 최솟값을 찾아 두 번째 위치와 교환... 이를 반복하여 정렬 완료
  • 파이선으로 구현한 선택 정렬
• 삽입 정렬
  • 삽입 정렬의 동작 과정: 주어진 배열에서 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후 원소를 뒤로 옮기고 지정된 자리에 삽입함. 이를 반복하여 정렬 완료
• 버블 정렬
  • 버블 정렬의 동작 과정: 인접한 두 원소를 비교하여 큰 값을 오른쪽으로 작은 값을 왼쪽으로 교환하며 정렬을 진행. 이를 반복하여 정렬 완료
  • 파이선으로 구현한 버블 정렬

탐색 알고리즘

• 선형 탐색
  • 선형 탐색 과정: 주어진 배열에서 찾고자 하는 값을 처음부터 순서대로 비교하여 찾음
  • 파이선으로 구현한 선형 탐색
• 이진 탐색
  • 이진 탐색 과정: 주어진 배열이 정렬되어 있는 경우, 배열의 중간값과 찾고자 하는 값을 비교하여 다음 탐색 대상 위치를 정하고, 이를 반복하여 찾음
  • 파이선으로 구현한 이진 탐색

재귀 알고리즘

• 피보나치 수열
  • 피보나치 수열 공식: 앞의 두 수를 더해서 다음 수를 만들어가는 수열
  • 파이선으로 구현한 피보나치 수열
• 하노이 탑
  • 하노이 탑의 풀이 과정: 큰 원반 n-1개를 기둥 2로 옮기기, 가장 큰 원반을 기둥 3으로 옮기기, 기둥 2에 있는 n-1개의 원반을 기둥 3으로 옮기기
  • 파이선으로 구현한 하노이 탑
• 퀵 정렬
  • 퀵 정렬의 동작 과정: 주어진 배열에서 하나의 원소를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하고, 각 부분 배열에서 다시 분할 및 정렬을 반복하여 정렬을 완료
  • 파이선으로 구현한 퀵 정렬