[TIL] 2025.5.30 알고리즘 기초

오늘 수업에서는 알고리즘에 대해서 배웠다

기존에 알던 내용이긴 하지만 중간중간 코딩테스트 팁도 같이 설명해주셔서 유용한 시간이였다!

 

알고리즘이란?

알고리즘이란, 주어진 문제를 해결하기 위한 단계적인 절차를 의미한다. 단순히 코드만 잘 짜는 것이 아니라, 문제 해결을 위한 논리적인 흐름을 설계하는 것이 핵심이다.

알고리즘이 갖춰야 할 조건

• 입력: 0개 이상의 입력이 있어야 한다.
• 출력: 1개 이상의 결과가 나와야 한다.
• 명확성: 각 단계는 모호하지 않고 명확해야 한다.
• 유한성: 알고리즘은 반드시 종료되어야 한다.
• 효과성: 실행 가능한 단순한 명령어로 구성되어야 한다.
• 독립성: 특정 프로그래밍 언어나 시스템에 종속되지 않는다.

좋은 알고리즘의 기준

좋은 알고리즘은 다음의 조건을 만족할수록 좋다.

• 정확하게 동작한다.
• 빠르다 (시간 효율성).
• 적은 메모리를 사용한다 (공간 효율성).
• 이해하기 쉽다.
• 다양한 문제에 재사용 가능하다.

알고리즘 표현 방법

알고리즘은 여러 가지 방식으로 표현할 수 있다.

• 자연어: 사람의 언어로 설명.
• 순서도(흐름도): 도형을 통해 알고리즘의 흐름을 시각적으로 표현.
• 프로그래밍 언어: 직접 실행 가능한 형태로 구현.
• 유사코드(의사코드): 코드처럼 보이지만 실제 문법에 얽매이지 않고 논리를 간단히 표현.

알고리즘 성능 평가

같은 문제를 해결하는 알고리즘이 여러 개 존재할 수 있기 때문에, 어떤 알고리즘이 더 효율적인지 판단할 필요가 있다.

평가 기준

• 연산량 (시간 효율성): 얼마나 빠르게 동작하는가.
• 메모리 사용량 (공간 효율성): 얼마나 적은 메모리로 동작하는가.

일반적으로 시간 효율성을 더 중요하게 보며, 실행 시간은 빅오(Big-O) 표기법을 통해 분석한다.

실행 시간 측정의 한계

단순히 코드 실행 시간을 측정하는 것에는 시스템 사양, 운영체제 상태 등에 따라 오차가 발생한다. 따라서 입력 크기(n)에 따른 시간 복잡도 분석을 통해 이론적으로 비교하는 것이 일반적이다.

 

단, 실제 문제를 풀 때는 처음부터 시간 복잡도만 신경 쓰기보다는 문제 해결 자체에 집중하고, 그 후 성능 개선을 고민하는 방식이 좋다.

알고리즘 유형 분류

정렬	데이터를 정해진 순서로 정렬. (퀵정렬, 병합정렬 등)
탐색	원하는 데이터를 찾는 과정. (선형탐색, 이진탐색)
그래프	노드-간 연결 탐색 (DFS, BFS, 다익스트라 등)
그리디	매 순간 최선의 선택을 통해 전체 최적 해를 구함
동적 프로그래밍	부분 문제의 결과를 저장하며 문제를 해결 (메모이제이션)
문자열 처리	문자열 검색, 비교, 패턴 매칭 등
스택/큐	자료구조 기반 문제 (LIFO/FIFO)
백트래킹	모든 경우를 탐색하면서 가지치기
비트 조작	비트 연산을 활용한 효율적인 문제 해결
수학	최대공약수, 소수 판별, 조합 등 수학 문제 해결

 

정렬 알고리즘

버블 정렬

• 인접한 두 값을 비교해 정렬하는 방식
• 구현이 간단하나, 느림 (시간복잡도 O(n²))

선택 정렬

• 매 회 가장 작은 값을 선택하여 앞에서부터 정렬
• 모든 경우 O(n²)의 시간복잡도를 가짐

Arrays.sort()

• Java에서 제공하는 고성능 정렬 함수
• 기본형 배열은 Dual Pivot Quick Sort (O(n log n))
• 객체 배열은 Comparator를 통한 사용자 정의 정렬 가능
• 컬렉션(List, Set 등)은 Collections.sort()나 스트림을 사용

검색 알고리즘

순차 검색 (선형 검색)

• 처음부터 끝까지 차례대로 비교
• 정렬 여부와 무관, 시간복잡도 O(n)

이진 검색 (이분 탐색)

• 정렬된 배열에서만 사용 가능
• 중간값과 비교하며 범위를 절반씩 줄여나감
• 시간복잡도 O(log n)

완전 탐색 (Brute-force)

• 가능한 모든 경우의 수를 전부 탐색
• 항상 정답은 보장되나 매우 비효율적
• DFS, 순열, 조합, 비트마스크 등으로 구현

문자열 처리

문자열은 내부적으로 정수로 표현된다. 일반적으로 UTF-8 인코딩이 사용되며, 문자열을 다루는 기본적인 메서드는 다음과 같다:

• 문자열 → 정수: Integer.parseInt(str)
• 정수 → 문자열: Integer.toString(num)
• 문자열 뒤집기: new StringBuilder(text).reverse().toString()

스택 (Stack)

• 후입선출(LIFO) 구조
• 삽입(push), 삭제(pop), 확인(peek), 비었는지 검사(isEmpty)
• 자바는 java.util.Stack 클래스 제공

재귀 함수

• 함수가 자기 자신을 호출하는 구조
• 종료 조건(Base Case)이 반드시 있어야 함
• 호출은 스택 메모리에 저장되며, 반복적으로 호출되면 StackOverflowError 발생 가능
• 중복 호출 시 메모이제이션(Memoization)으로 최적화

사용 예: 피보나치 수열, 팩토리얼, 하노이탑, 백트래킹

큐 (Queue)

• 선입선출(FIFO) 구조
• front에서 꺼내고 rear에 삽입
• 순차 처리에 적합

선형 큐

• 배열 기반 큐
• front와 rear가 앞뒤로 이동
• 한계: 공간 낭비 발생 가능

원형 큐 (Circular Queue)

• 배열의 끝과 처음을 연결해 공간을 재활용
• 상태: 공백(==), 포화((rear+1)%n == front)

우선순위 큐 (Priority Queue)

• 우선순위가 높은 요소부터 먼저 처리
• 힙 구조를 사용해 O(log n) 시간 복잡도
• 스케줄링, 다익스트라 알고리즘 등에 사용됨