[Algorithm] 알고리즘과 APS 개요 : 기본 개념(Algorithm & APS Overview)

개발자로 취업준비를 하게되면 당연히 '코딩테스트'를 보게되고 그에따라 익숙해지는 것이 바로 '알고리즘'이다.
따라서, 알고리즘과 APS(Algorithm Problem Solving)은 자료구조에 대한 학습, 컴퓨터 사고력을 향상 시키는데 핵심적이다.
이 글에서는 알고리즘의 기본 개념부터 시간 복잡도, Big-O 표기법

알고리즘(Algorithm)

- 문제를 해결하기 위해 수행해야 하는 절차나 방법
- 컴퓨터 과학에서의 알고리즘은 원하는 결과를 얻기 위해 수행해야 하는 절차를 말함

APS(Algorithm Problem Solving)

APS는 단순히 알고리즘을 아는 것을 넘어, 프로그래밍을 이용해 실제 문제를 해결하는 과정을 말함

cf) APS의 핵심 요소는 자료구조 이해, 알고리즘 기법 학습, 문제해결 능력 향상, 코드 구현 능력 강화

알고리즘의 평가 기준

알고리즘은 아래와 같은 5가지 기준으로 주로 평가된다.

• 정확성 : 모든 입력에 대해 정확한 결과를 출력하는가?
• 작업량 : 얼마나 적은 연산으로 문제를 해결하는가?
• 메모리 사용량 : 얼마나 적은 메모리를 사용하는가?
• 단순성 : 다른 사람이 이해하기 쉬운가?
• 최적성 : 더이상 개선할 여지가 없는가?(최적화)

알고리즘 표현

1. 자연어 (Natural Language)

일상적인 언어(한국어, 영어 등)로 절차를 서술하는 방식

특징: 누구나 이해하기 쉽지만, 언어의 모호성 때문에 명확한 논리 전달에는 한계(기획/아이디어 단계)

2. 순서도 (Flowchart)

약속된 기호(도형)와 화살표를 사용하여 논리의 흐름을 도식화

특징: 제어 구조(분기, 반복)와 흐름을 시각적으로 파악하기 좋아 논리 오류 발견에 유리

3. 의사코드 (Pseudocode)

프로그래밍 언어의 형태를 빌려 논리적 절차만 간결하게 기술한 '가짜 코드'

특징: 특정 언어 문법에 구애받지 않고 알고리즘의 핵심 논리에만 집중할 수 있어, 연구 논문이나 설계 단계에서 표준적으로 사용

4. 프로그래밍 언어 (Programming Language)

컴퓨터가 실제로 실행할 수 있도록 특정 언어(Python, Java 등)의 엄격한 문법에 맞춰 작성한 코드

특징: 알고리즘의 최종 구현체이며, 기계가 해석 가능한 구체적인 명령어로 구성됨

시간 복잡도

• 시간 복잡도란 알고리즘이 문제를 해결하기 위해 얼마나 많은 연산(단계)을 수행하는지 나타내는 척도
• 입력 크기가 커졌을 때 알고리즘의 처리 시간이 어떻게 증가하는지를 파악함으로써 향후 대규모 데이터에 대해서도 효율적으로 동작할지 여부를 예측 가능

빅-오(Big-O) 표기법

• 빅-오 표기법은 시간 복잡도를 표현할 때 주로 사용되는 방법으로 시간 복잡도의 최대값을 나타냄

• 이는, 입력 크기 N이 매우 커졌을 때, 연산횟수가 얼마나 증가하는 지를 나타내는 방식

• 가장 영향력이 큰 항을 남김

• 계수(Coefficient)는 생략하여 표시
  ex1 ) O(N² + N) → O(N²)
  ex2 ) O(3N + 10) → O(N)

  표기	이름	설명	예
  $O(1)$	상수 시간	입력 크기와 관계없이 연산량이 일정	배열의 원소 접근 / 사칙연산 조건 비교 / 값 할당
  $O(\log n)$	로그 시간	연산량이 $\log n$에 비례	이진탐색
  $O(n)$	선형 시간	연산량이 $n$에 비례	1차원 for문 탐색 최대 / 최소 찾기
  $O(n \log n)$	선형 로그 시간	연산량이 $n \log n$에 비례	일부 정렬 알고리즘 (병합, 힙, 퀵) 우선순위 큐로 구현한 다익스트라 알고리즘
  $O(n^2)$	2차 시간	연산량이 $n^2$에 비례	2중 for 문 일부 정렬 알고리즘 (버블, 선택, 삽입)
  $O(n^3)$	3차 시간	연산량이 $n^3$에 비례	3중 for 문 플로이드-워셜 알고리즘
  $O(2^n)$	지수 시간	연산량이 $2^n$에 비례	부분집합 재귀함수로 구현한 피보나치 수열
  $O(n!)$	팩토리얼 시간	연산량이 $n!$에 비례	순열

  cf1) 시간복잡도 비교 그래프 w/ Big-O 표기법
  

  cf2) 계수를 생략할 수 있는 이유
  빅오 표기법은 하드웨어 성능이나 컴파일러 환경 같은 가변적인 요소를 배제하고, 데이터 급증($n \to \infty$)에 따른 알고리즘의 본질적인 확장성(Scalability)과 증가율(Growth Rate)만을 객관적으로 평가하기 위해 상수 계수를 생략