[TIL] 알고리즘 기초 개념 정리

카테고리 없음

[TIL] 알고리즘 기초 개념 정리

mooncommit 2026. 4. 3. 20:58

😎 알고리즘 강의 챕터 1-2

알고리즘 시간복잡도 빅오표기법 코딩테스트

1. 알고리즘이란?

알고리즘(Algorithm) : 문제를 해결하기 위한 단계적 절차나 규칙

요리 레시피처럼, 시작부터 끝까지 순서대로 무엇을 해야 하는지 적어놓은 것.

알고리즘을 왜 배울까?

논리적 사고력 향상	체계적·논리적인 사고방식을 기를 수 있음
효율적인 문제 해결	더 빠르고 효율적인 코드 작성 가능
취업 (코딩테스트)	문제 이해도 + 구현 능력 + 효율적 해결 능력을 종합 평가

알고리즘 표현 방법

𖠌 의사코드 (Pseudocode)

프로그래밍 언어와 유사하지만 문법에 얽매이지 않음
단계별 논리 흐름을 구조적으로 표현하기 좋음
실제 코드로 옮기기 쉬움

FUNCTION findMax(numbers):
    max ← numbers[0]
    FOR i = 1 TO length(numbers) - 1
        IF numbers[i] > max THEN
            max ← numbers[i]
    RETURN max

Ꙭ̮ 자연어 표기법

일상적인 언어로 설명 → 비전문가도 쉽게 이해
전체 흐름과 핵심 아이디어를 빠르게 전달
단, 모호한 표현이 생기지 않도록 주의

1. 첫 번째 숫자를 최댓값으로 저장한다.
2. 두 번째 숫자부터 순서대로 확인한다.
   - 현재 숫자가 최댓값보다 크면, 최댓값을 갱신한다.
3. 모든 숫자 확인 후, 최댓값을 반환한다.

자신만의 언어로 문제 해결 아이디어를 표현하는 것이 중요. 의사코드와 자연어를 혼용해도 OK!

2. 좋은 알고리즘의 조건

조건핵심 내용예시

정확성	같은 입력 → 항상 같은 올바른 결과	[1,3,2] 정렬 → 항상 [1,2,3]
효율성	시간·공간 복잡도가 적절해야 함	버블정렬 대신 퀵정렬
명확성	각 단계가 누가 봐도 이해하기 쉬움	변수명 tmp → totalAmount
확장성	다양한 상황에 적용 가능, 수정·디버깅 용이	새로운 로그인 방식을 쉽게 추가 가능한 구조

3. 알고리즘 성능 분석

📌 시간복잡도란?

알고리즘이 문제를 해결하는 데 얼마나 많은 시간이 필요한지를 표현하는 방법 → 정확한 실행 시간이 아닌,

입력 크기 증가에 따른 실행 시간의 증가 추세를 나타냄.

공간복잡도(메모리)도 있지만, 사용자가 직접 체감하기 어렵기 때문에 시간복잡도를 더 중요하게 봄.

📌 빅오(Big-O) 표기법

O(1)	배열 인덱스 접근, 스택/큐 삽입·삭제	입력 크기와 무관, 항상 동일한 시간
O(log N)	이진 탐색	입력이 커져도 로그 값으로만 증가
O(N)	배열 순차 탐색, 최대/최솟값 찾기	입력과 시간이 비례
O(N log N)	병합정렬, 퀵정렬, 힙정렬	가장 효율적인 비교 기반 정렬
O(N²)	버블/삽입/선택 정렬, 2중 반복문	입력의 제곱으로 시간 증가
O(2^N)	부분집합 생성	지수적으로 증가
O(N!)	순열 생성	팩토리얼로 폭발적 증가

📌 시간복잡도 계산 방법

명령문 개수를 세고 → 가장 큰 항만 남기기

// 실행 횟수 분석 예시 : 1부터 n까지의 합
int sum = 0;           // 1회
for(int i = 0; i < n; i++) {   // 초기화 1회 + 조건 n+1회 + 증감 n회
    sum += i;          // n회
}
System.out.println(sum); // 1회

// 전체 : 1 + 1 + (n+1) + n + n + 1 = 3n + 4
// → 최고차항만: O(n)

n 이 매우 커지면 작은 항들의 영향은 미미해짐
상수항은 실행 환경에 따라 달라지므로 제거
증가 추세가 핵심이지, 정확한 횟수는 중요하지 않음

T(n) = 5n³ + 100n² + 200n + 1000
→ 최고차항: 5n³
→ 계수 제거: n³
→ 최종: O(n³)

📌 코딩테스트 시간 제한 기준 (테스트 케이스당 1~2초)

시간복잡도데이터 크기 상한비고

O(log N)	10^18	N이 매우 커도 빠름
O(N)	10^8 (1억)	1초에 수행 가능
O(N log N)	10^6 (백만)	N=10^7이면 약 2.3초
O(N²)	10^4 (만)	2중 반복문 주의
O(2^N)	20	N=30만 돼도 10초 이상
O(N!)	10	N이 조금만 커져도 불가

문제의 입력 크기 N을 먼저 파악하고, 허용 시간 안에 드는 알고리즘을 선택해야 한다!

4. 알고리즘 문제 풀이 5단계

절대 문제를 읽자마자 코딩하지 말 것!
문제를 제대로 이해하지 않고 시작하면 → 잘못된 방향으로 구현 → 디버깅에 몇 배의 시간 소요

STEP 1. 문제 이해 및 요구사항 분석

문제를 천천히 정독
예제 입출력으로 의도 파악
입력/출력 형식 정확히 파악
제약 조건과 규칙 정리

STEP 2. 접근 방법 구상

비슷한 유형의 문제 떠올리기
어떤 알고리즘 유형인지 판단
문제 해결 절차를 단계별로 도식화

STEP 3. 세부 구현 설계 및 검토

의사코드로 각 단계 표현
예외 상황과 극단적인 케이스 고려
시간복잡도 분석

STEP 4. 코드 작성 및 구현

설계한 아이디어를 실제 코드로
변수명·함수명을 명확하게

STEP 5. 테스트와 디버깅

예시 입출력 테스트
극단적인 케이스 테스트 (0, 음수, 최대값 등)
시간 초과 시 → 아이디어 수정, 자료구조 최적화, 메모이제이션, 백트래킹 고려

5. 알고리즘 주요 유형 정리

🐶 구현 & 시뮬레이션

구현 : 요구사항을 그대로 코드로 옮기는 능력
시뮬레이션 : 주어진 시나리오·규칙을 차례대로 실행
인덱스 범위, 예외 처리 실수가 많으니 꼼꼼하게!

🐼 완전 탐색 (Brute Force)

모든 경우의 수를 탐색해 정답 도출
입력 규모가 작을 때 유리, 정답 보장
반복문 or 재귀 함수로 구현

🐹 그리디 (Greedy)

매 순간 가장 최선의 선택 → 전체 최적해
적용 조건: 탐욕 선택 속성 + 최적 부분 구조
빠르고 직관적이지만 조건 불만족 시 오답

🐰 백트래킹 (Backtracking)

완전 탐색 + 유망하지 않은 경우 가지치기
탐색 범위를 줄여 효율 향상
주로 재귀 함수로 구현

🦊 분할 정복 (Divide and Conquer)

분할 → 정복(해결) → 병합
분할된 하위 문제들은 서로 독립적이어야 함
대표: 병합정렬, 퀵정렬, 이진탐색

🐻 동적 계획법 (DP)

큰 문제 → 작은 부분 문제로 나눠 해결 결과를 저장(메모이제이션) 후 재활용
적용 조건: 최적 부분 구조 + 중복되는 부분 문제
점화식을 올바르게 세우는 것이 핵심!

📊 알고리즘 선택 가이드

문제 파악
  ↓
입력 크기 N 확인 → 시간복잡도 허용 범위 계산
  ↓
- 요구사항 그대로 구현 → 구현/시뮬레이션
- N이 작고 모든 경우 탐색 → 완전 탐색
- 매 순간 최선 선택이 전체 최적 → 그리디
- 완전 탐색 + 가지치기 → 백트래킹
- 독립적 하위 문제로 분할 가능 → 분할 정복
- 중복 부분 문제 + 최적 부분 구조 → DP
  ↓
필요 시 알고리즘 조합 (예: 백트래킹 + DP)

6. 실습 문제 풀이

실습 1 - 배열에서 최댓값 찾기 (O(N))

문제 : 정수 배열에서 최댓값을 찾아라.

자연어 풀이 설계

1. 배열의 첫 번째 원소를 최댓값으로 설정한다.
2. 두 번째 원소부터 마지막 원소까지 순서대로 비교한다.
   - 현재 원소가 최댓값보다 크면, 최댓값을 갱신한다.
3. 모든 비교가 끝나면 최댓값을 반환한다.

Java 구현

public class FindMax {
    public static int findMax(int[] numbers) {
        int max = numbers[0]; // 첫 번째 원소를 최댓값으로 초기화

        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] > max) {
                max = numbers[i]; // 더 큰 값 발견 시 갱신
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {3, 7, 1, 9, 4, 6};
        System.out.println("최댓값: " + findMax(arr)); // 출력: 9
    }
}
// 시간복잡도: O(N) - 배열을 한 번 순회

실습 2 - 1부터 N까지의 합 (O(N) vs O(1) 비교)

문제 : 1부터 N까지의 합을 구하는 두 가지 방법을 비교하라.

자연어 풀이 설계

방법 1 - 반복문:
  1. sum = 0으로 초기화한다.
  2. 1부터 N까지 반복하며 sum에 더한다.
  3. sum을 반환한다.

방법 2 - 가우스 공식:
  1. N * (N+1) / 2 를 계산하여 바로 반환한다.

Java 구현

public class SumComparison {

    // 방법 1: 반복문 - O(N)
    public static int sumLoop(int n) {
        int total = 0;
        for (int i = 1; i <= n; i++) {
            total += i;
        }
        return total;
    }

    // 방법 2: 가우스 공식 - O(1)
    public static int sumGauss(int n) {
        return n * (n + 1) / 2;
    }

    public static void main(String[] args) {
        int n = 1000000;
        long start, end;

        // 방법 1 시간 측정
        start = System.nanoTime();
        int result1 = sumLoop(n);
        end = System.nanoTime();
        System.out.println("반복문 결과: " + result1);
        System.out.println("반복문 실행 시간: " + (end - start) + " ns");

        // 방법 2 시간 측정
        start = System.nanoTime();
        int result2 = sumGauss(n);
        end = System.nanoTime();
        System.out.println("\n가우스 공식 결과: " + result2);
        System.out.println("가우스 공식 실행 시간: " + (end - start) + " ns");
    }
}
// → N이 클수록 가우스 공식의 압도적인 속도 차이를 체감할 수 있음

실습 3 - 거스름돈 문제 (그리디 알고리즘)

문제 : 500원, 100원, 50원, 10원 동전으로 N원을 거슬러줄 때 최소 동전 개수를 구하라.

자연어 풀이 설계

1. 동전을 큰 단위부터 작은 단위 순으로 준비한다: [500, 100, 50, 10]
2. 남은 금액을 N으로 초기화한다.
3. 가장 큰 동전부터 순서대로:
   - 현재 동전으로 최대한 많이 거슬러준다 (나눗셈)
   - 남은 금액을 업데이트한다 (나머지)
   - 남은 금액이 0이면 즉시 종료
4. 사용된 동전 개수를 반환한다.

핵심 아이디어 : 큰 단위가 작은 단위의 배수 → 탐욕 선택 속성 성립

Java 구현

import java.util.*;

public class CoinChange {

    public static int coinChange(int[] coins, int target) {
        Arrays.sort(coins); // 오름차순 정렬

        int remaining = target;
        int count = 0;

        // 큰 단위부터 (뒤에서부터 순회)
        for (int i = coins.length - 1; i >= 0; i--) {
            count += remaining / coins[i];   // 해당 동전으로 거슬러줄 수 있는 개수
            remaining %= coins[i];           // 남은 금액 갱신

            if (remaining == 0) return count; // 0원이면 조기 종료
        }
        return count;
    }

    public static void main(String[] args) {
        int[] coins = {500, 100, 50, 10};
        Scanner scanner = new Scanner(System.in);
        int target = scanner.nextInt();
        System.out.println(coinChange(coins, target));
    }
}

테스트 케이스 (입력출력설명)

1260	6	500×2 + 100×2 + 50×1 + 10×1
830	7	500×1 + 100×3 + 10×3
0	0	거스름돈 없음
500	1	500원 1개

시간복잡도 : O(K) — K는 동전 종류 수 (이 경우 K=4이므로 사실상 O(1))

🍬 핵심 정리

알고리즘 공부의 핵심은 코드 암기가 아니라, 문제를 보고 "어떤 방식으로 접근할지" 생각하는 능력을 키우는 것이다.

알고리즘 = 문제를 해결하는 단계적 절차
좋은 알고리즘 = 정확성 + 효율성 + 명확성 + 확장성
시간복잡도 → 빅오 표기법으로 증가 추세 파악
문제 풀이 순서 : 이해 → 구상 → 설계 → 구현 → 테스트 (코드 먼저 X!)
알고리즘 유형 : 구현, 완전탐색, 그리디, 백트래킹, 분할정복, DP

다음 챕터에서는 자료구조와 탐색 알고리즘을 다룰 예정⎝⍢⎠

현재글[TIL] 알고리즘 기초 개념 정리

MoonCommit DevLog

mooncommit-dev 님의 블로그 입니다.

cookie, HashMap, 일정관리앱, 객체지향, Spring, git, 프로젝트, spring boot, Session, til, 트러블슈팅, 알고리즘, github, 메서드, 자료구조, java, 내일배움캠프, 예외처리, for,

Today :
Yesterday :

일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

MoonCommit DevLog