알고리즘 개념

1️⃣ 알고리즘

1. 알고리즘이란?

• 문제를 해결하기 위한 단계적 절차나 규칙(레시피)
• 예시

1단계: 장바구니 상품 목록을 입력받는다
2단계: 총 금액 변수를 0으로 설정
3단계: 각 상품에 대해 반복:
         - 상품의 가격 × 수량을 계산
         - 계산 결과를 총 금액에 더함
4단계: IF 총 금액이 50,000원 이상이면
          배송비 = 0
       ELSE
          배송비 = 3,000
5단계: 최종 결제 금액 = 총 금액 + 배송비
6단계: 최종 결제 금액 출력

 

2. 알고리즘 표현 방법 : 다른 사람에게 전달 / 구현 > 과정을 명확하고 간결하게 표현

 

1) 의사코드

• 프로그래밍 언어와 유사
• 예시) 최댓값 찾기

FUNCTION findMax(numbers):
    max ← numbers[0] // 첫 번째 값 > max = 이게 제일 크다고 치자.
    FOR i = 1 TO length(numbers) - 1 // [1] ~ [마지막]
        IF numbers[i] > max THEN
            max ← numbers[i] // 최댓값 > max
        END IF
    END FOR
    RETURN max
END FUNCTION

 

2) 자연어 표기법

• 비전문가도 이해 가능
• 문장이 모호해질 수 있으므로 정확한 표현에 신경 써야 함
• 예시) 최댓값 찾기

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

 

2️⃣ 좋은 알고리즘

1. 조건

 

1) 정확성: 정확하게 동작하는가

• 입력한 값에 대해 올바른 결과
• 정해진 단계를 따라 실행, 반드시 멈추는 시점 O
• 같은 입력 값이면 항상 같은 값 정확성(정확하게 동작)

2) 효율성

• 시간 복잡도: 실행시간이 너무 오래 걸리지 X
• 공간 복잡도: 메모리를 적절하게 사용

3) 명확성: 이해하기 쉬운가

• 각 단계가 명확하고 이해하기 쉬워야 함
• 다른 사람도 읽고 이해 O
• 주석으로 설명 추가하면 좋음 명확성(이해하기 쉬운가)

4) 확장성: 실용적이고 관리하기 좋은가

• 다양한 상황에서 사용 O
• 나중에 수정하거나 개선하기 쉬운가

3️⃣ 알고리즘 성능 분석

1. 성능 분석이란

• 얼마나 효율적으로 동작하는지 측정 방법
• 기준: 시간(실행 속도) + 공간(메모리 사용량)

2. 시간복잡도: 알고리즘이 문제를 해결하는데 얼마나 많은 시간이 필요한지 표현하는 방법

 

1) 빅오(Big-O) 표기법

• 시간 복잡도를 수학적으로 표현하는 방법
• 입력 데이터 크기가 늘어날 때 실행 시간이 어떤 비율로 증가하는지 표현
• 입력 데이터 크기에 따라 실행 시간 증가 추세 표현

 

3. 시간 복잡도 구하기

 

1) 명령문 개수 계산

• 반복문, 조건문, 대입문 등 각각의 명령문이 실행되는 횟수 계산
• 각 줄의 실행 횟수를 더하여 전체 실행 획수를 구한다
• 예시

public class TimeComplexityExamples {
   
   /**
    * O(1) - 상수 시간 복잡도
    * 입력값 n에 상관없이 항상 동일한 시간이 걸립니다.
    * 단순 출력문 하나만 실행되므로 실행 시간이 일정합니다.
    */
   public void constantTime(int n) {
       System.out.println(n); // 단 한 번의 연산만 수행
   }
   
   /**
    * O(n) - 선형 시간 복잡도
    * 입력값 n에 비례하여 실행 시간이 증가합니다.
    * n이 2배가 되면 실행 시간도 약 2배가 됩니다.
    */
   public void linearTime(int n) {
       for(int i = 0; i < n; i++) {
           System.out.println(i); // n번 실행됨
       }
   }
   
   /**
    * O(n²) - 제곱 시간 복잡도
    * 입력값 n의 제곱에 비례하여 실행 시간이 증가합니다.
    * n이 2배가 되면 실행 시간은 4배가 됩니다.
    */
   public void quadraticTime(int n) {
       // 외부 루프: n번 반복
       for(int i = 0; i < n; i++) {
           // 내부 루프: 각 i에 대해 n번 반복
           for(int j = 0; j < n; j++) {
               System.out.println(i + j); // n * n = n² 번 실행됨
           }
       }
   }
}

 

2) 가장 큰 항만 남기기

• 빅오 표기법에서 큰 항만 고려하는 이유
  : 입력 크기(n)가 매우 커질 때는 작은 항들의 영향력 미미
  : 상수항은 실제 실행 환경에 따라 달라질 수 있어 제외
  : 증가 추세를 파악하는 것이 목적
• 예시) 입력 데이터 크기가 n일 때 명령어 실행횟수가 T(n)인 경우 시간 복잡도 계산

T(n) = 5n³ + 100n² + 200n + 1000

단순화 과정
1. 최고차항 선택: 5n³
2. 계수 제거: 5
3. 다른 항 제거: n², n, 상수항 제거
4. 최종 표기: O(n³)

• 예시) 1부터 n까지 합을 구하는 알고리즘 / 실행 횟수 분석 및 시간 복잡도 계산

/* 1부터 n까지의 합을 구하는 알고리즘
   실행 횟수 분석 및 시간 복잡도 계산 */

int sum = 0; // 초기화: 대입 연산 1회

/* 반복문 실행 분석
   - 초기화 (i = 0): 대입 연산 1회
   - 조건 검사 (i < n): 조건 연산 n+1회
   - 증감식 (i++): 증감 연산 n회 */
for(int i = 0; i < n; i++) {    
    sum += i; // 덧셈 연산 n회        
}

System.out.println(sum); // 출력: 함수실행 1회

/* 전체 실행 횟수 계산
   = 1 + 1 + (n+1) + n + n + 1
   = 3n + 4

   시간 복잡도: O(n)
   - 실행 횟수가 n에 비례하여 선형적으로 증가 */

 

4️⃣ 더 좋은 알고리즘

1. 시간 복잡도 차이

• 배열의 모든 원소의 합과 최댓값을 구하기 위해
  반복문을 한 번만 사용 vs  반복문 두 번 사용

public class SimpleTimeComplexity {
    public static void main(String[] args) {
        int n = 10000;
        int[] numbers = new int[n];
        
        // 배열 초기화
        for (int i = 0; i < n; i++) {
            numbers[i] = i + 1;
        }
        
        // 방법 1: 하나의 반복문으로 두 연산 수행
        System.out.println("방법 1: 하나의 반복문");
        int sum1 = 0;
        int max1 = 0;
        for (int i = 0; i < n; i++) {
            sum1 += numbers[i];    // 합계 구하기
            if (numbers[i] > max1) {
                max1 = numbers[i]; // 최댓값 찾기
            }
        }
        
        // 방법 2: 두 개의 반복문으로 각각 연산 수행
        System.out.println("방법 2: 두 개의 반복문");
        int sum2 = 0;
        for (int i = 0; i < n; i++) {
            sum2 += numbers[i];    // 합계 구하기
        }
        
        int max2 = 0;
        for (int i = 0; i < n; i++) {
            if (numbers[i] > max2) {
                max2 = numbers[i]; // 최댓값 찾기
            }
        }
    }
}

• 둘 다 O(n)
• 과도하게 하나의 반복문에 모든 로직 처리할 필요 X / 코드의 가독성과 유지보수성을 고려해 분리 O

2. 1~1000까지 합 구하기

• 예시

public class SumAlgorithms {

    // 방법 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 = 1000;
        
        // 각 방법의 실행 시간 측정을 위한 변수
        long startTime, endTime;
        
        // 방법 1: 반복문
        startTime = System.nanoTime();
        int result1 = sumLoop(n);
        endTime = System.nanoTime();
        System.out.println("반복문 결과: " + result1);
        System.out.println("실행 시간: " + (endTime - startTime) + " ns");
        
        // 방법 2: 가우스 공식
        startTime = System.nanoTime();
        int result2 = sumGauss(n);
        endTime = System.nanoTime();
        System.out.println("\n가우스 공식 결과: " + result2);
        System.out.println("실행 시간: " + (endTime - startTime) + " ns");
    }
}

 

3. 시간 복잡도 비교 차트

• Y축: 연산량, X추기: n의 크기

• 빅오 시간 복잡도에 따른 실제 실행 시간 비교표(N=10억)

• 시간 제한에 따른 알고리즘 가능 여부

 

5️⃣ 알고리즘 유형

 

1. 구현 & 시뮬레이션

 

1) 구현 문제: 문제의 요구사항을 실제 동작하는 코드로 구현하는 능력

    시뮬레이션 문제: 문제에서 요구하는 시나리오, 규칙, 절차를 차례대로 실행하는 능력

 

2) 특징

• 코딩 테스트에서 가장 기본이 되는 문제 유형
• 구현의 정확성
• 요구사항을 빠짐없이 코드로 옮기는 것
• 문제의 조건과 제약을 정확히 이해, 처리
• 꼼꼼함 / 중간 결과 검증 / 문제의 전체 흐름 파악 중요

3) 주요 유형

 

• 단순 구현 : 주어진 알고리즘이나 규칙을 그대로 코드로 옮기는 것
  → 날짜 계산, 문자열 처리, 진법 변환
• 완전 시뮬레이션 : 문제에서 제시된 과정을 처음부터 끝까지 실행하여 결과를 도출
  → 게임 진행, 주사위/카드/보드 시뮬레이션
• 상태 변화 시뮬레이션 : 특정 조건에 따라 시스템의 상태가 변화하는 과정을 구현
  → 로봇 이동, 뱀 게임
• 규칙 찾기 : 문제의 숨겨진 규칙을 찾아 이를 코드로 구현
  → 달팽이 배열, 패턴 문제

2. 완전 탐색 : 모든 경우의 수를 전부 시도해서 정답을 찾는 방식

 

1) 특징

• 정답을 놓칠 가능성이 없음
• 대신 입력 크기가 작을 때만 유리
• 구현이 비교적 단순

2) 구현 방법

• 반복문 이용
• 재귀 함수 이용 = 자기 자신을 다시 호출하는 함수 + 종료조건 필수

3) 대표 유형

 

• 순열 / 조합 계산
  → N개 중 K개를 고르는 모든 조합, N개 전부를 나열하는 모든 순열
• 부분집합 계산
  → 부분집합의 합으로 특정 값을 만드는 모든 경우 확인
• 그래프 전체 탐색
  → 모든 경로 찾기, 모든 노드 방문 시뮬레이션, DFS/BFS를 통한 모든 가능성 확인

3. 그리디 알고리즘 : 매 순간 가장 좋아 보이는 선택을 하는 방식

 

1) 특징

 

• 구현이 쉽고 빠름

2) 적용 조건

 

• 탐욕 선택 속성 : 지금 제일 좋아 보이는 선택을 해도 괜찮은 성질
• 최적 부분 구조 : 작은 문제도 최선이어야 함

3) 대표 문제 유형

 

• 거스름돈 문제
  > 동전 단위가 특정 조건에 부합할 때, 큰 단위 동전부터 사용
• 회의실 배정
  > 종료 시간이 빠른 회의부터 배정하는 방식 / 최대 개수를 찾는 문제
• 최소 신장 트리 (Kruskal, Prim) : 최소 비용
  > 크루스칼(Kruskal) - 싼 것부터 고름(사이클x) , 프림(Prim) 알고리즘 - 최소 비용으로 넓혀가기

4. 백트래킹

 

1) 개념

• 완전 탐색 기반 + 조건 불만족은 미리 배제
• 탐색 효율 높이는 기법

2) 특징

 

• 재귀로 구현하는 경우가 많음
• 탐색 범위를 크게 줄일 수 있음

3) 적용조건

• 상태 공간 트리 구성 가능성 : 문제 해결 과정 > 트리 형태 / 단계별 선택지를 명확하게 정의
• 유망성 판단 기준: 더 진행할 가치가 있는지 판단
• 가지치기 효율성: 조건 불만족 제외했을 때 탐색 범위가 줄어야 함 / 조건 검사가 복잡x

4) 대표 문제

 

• N-Queen : 퀸이 서로 공격하지 않도록 배치하는 경우의 수 찾기
• 스도쿠
• 조건 있는 부분집합 문제

5. 분할 정복

 

1) 개념

 

• 문제를 비슷한 하위 문제로 나누고
• 각각 해결한 뒤 결과를 합침

2) 구조

• 분할 → 정복 → 병합
• 각 부분 문제는 독립접

3) 적용 조건

• 분할 가능성
• 하위 문제의 독립성
• 병합 가능성

4) 대표 문제 유형

 

• 병합 정렬
• 퀵 정렬
• 이진 탐색

 

6. 동적 계획법

 

1) 개념

• 작은 문제의 해를 저장해두고 재사용
• 중복 계산 제거

2) 특징

• Top-Down 방식(메모이제이션) 또는 Bottom-up 방식(타뷸레이션)으로 구현
• 점화식(Recurrence Relation)을 올바르게 세우는 것이 핵심

3) 적용 조건

 

• 최적 부분 구조
• 중복되는 부분 문제

4) 대표 문제 유형

 

• 피보나치 수열
• 배낭 문제
• LIS (최장 증가 부분 수열)
• 최단 경로