TIL - 알고리즘 기초
1. 알고리즘이란?
알고리즘은 문제를 해결하는 절차(방법)이다.
같은 문제라도 어떤 방식으로 해결하느냐에 따라 실행 속도와 효율이 크게 달라진다.
문제 분석부터 아이디어 도출 및 구현까지의 체계적인 접근방식을 가져야한다.
- 단순히 “동작하는 코드”보다
- “효율적으로 동작하는 코드”가 더 중요하다
2. 시간복잡도 (Big-O)
시간복잡도는 입력 크기(n)가 증가할 때 실행 시간이 얼마나 증가하는지를 나타낸다.
대표 유형
O(1) → 입력 크기와 상관없이 일정
O(n) → 데이터 수에 비례
O(n²) → 이중 반복문 (성능 급격히 저하)
판단 기준
반복문 1개 → O(n)
반복문 2개 → O(n²)
절반씩 줄어들면 → O(log n)
‼️n의 10승 1억 <- 계산구하는 기준점이 많이된다
중요한 점
Big-O는 정확한 시간이 아니라
- “증가하는 패턴(성장률)”을 보는 개념
3. 완전탐색 (Brute Force)
가능한 모든 경우를 하나씩 직접 확인하는 방법
🔔 특징
구현이 직관적이고 쉽다
정답을 놓치지 않는다
경우의 수가 많으면 느려진다
🔔 사용 상황
경우의 수가 많지 않을 때
모든 값을 비교해야 할 때
for (int i = 1; i <= n; i++) {
if (조건) {
result++;
}
}⚠️ 주의
시간초과 발생 가능
불필요한 반복 줄이는 것이 중요
4. 그리디 (Greedy)
매 순간 가장 최선이라고 생각되는 선택을 하는 방법
🔔 특징
빠르고 구현이 간단하다
항상 정답이 되는 것은 아니다
🔔 사용 조건 (중요)
현재 선택이 전체 최적해로 이어질 때만 사용 가능
🔔 예시
거스름돈 문제 → 큰 단위부터 사용
회의실 문제 → 끝나는 시간이 빠른 순서
⚠️ 주의
문제에 따라 틀릴 수 있음
반드시 “이 선택이 항상 맞는지” 검증 필요
5. 자료구조
데이터를 효율적으로 저장하고 접근하기 위한 구조
🔔 종류 및 특징
List → 순서 O / 중복 O / 탐색 O(n)
Set → 중복 X / 빠른 포함 여부 확인
Map → key-value / 탐색 O(1)
🔔 선택 기준
순서 필요 → List
중복 제거 → Set
빠른 조회 → Map
🔔 심화
계층구조 → 트리
연결 관계 → 그래프
👉 자료구조 선택이 성능에 직접적인 영향
6. 알고리즘 유형 (확장 개념)
✔ 백트래킹
모든 경우를 탐색하되 조건에 맞지 않으면 되돌아감
(DFS 기반)
✔ 분할정복
문제를 작은 단위로 나눠 해결 후 합침
(예: 정렬 알고리즘)
✔ 동적계획법 (DP)
동일한 계산 반복을 줄이기 위해 결과 저장
성능 개선에 매우 효과적
👉 현재는 개념 이해 단계
7. 오늘 배운 점
알고리즘은 단순 구현이 아니라 접근 방법이 중요하다
완전탐색은 안정적이지만 비효율적일 수 있다
그리디는 빠르지만 항상 정답이 아니다
자료구조 선택이 성능에 영향을 준다
시간복잡도를 고려하지 않으면 실제 환경에서 문제가 발생할 수 있다
8. 오늘 느낀 점
문제를 보면 바로 코드를 작성하기보다
👉 어떤 방식으로 해결할지 먼저 고민하는 과정이 중요하다는 것을 느꼈다.
특히 완전탐색과 그리디의 차이를 이해하면서
👉 문제 유형에 따라 접근 방법이 달라진다는 점이 인상적이었다.
한줄 정리
❗️ 알고리즘 = 문제 해결 방법
❗️ 시간복잡도 = 효율 판단 기준
❗️ 자료구조 = 데이터 관리 방법
내일은 오늘강의에서 진행한 예시코드포함 몇개의 예제문제를 풀어봐야겠다
