TIL-25.12.19

이준연·2025년 12월 19일

Today I learned

학습 키워드

알고리즘

알고리즘

문제를 해결하기 위한 단계적 절차나 규칙입니다.

알고리즘의 중요성

논리적 사고력 향상

알고리즘을 배우는 가장 큰 이유는 논리적 사고력을 기르기 위해서입니다.
문제를 해결하는 과정에서 체계적이로 논리적인 사고방식을 기를 수 있습니다.

효율적인 문제 해결

알고리즘 학습을 통해 더 빠르고 효율적인 코드를 작성할 수 있게 되며, 복잡한 문제를 분석하고 해결하는 능력을 향상시킬 수 있습니다.

취업에서의 중요성

현재 대부분의 IT 기업들은 코딩 테스트를 통해 지원자의 능력을 평가합니다. 그리고 코딩 테스트는 단순이 지식을 평가하는 것이 아닙니다. 제한된 시간 내에 다음의 역량을 종합적으로 평가합니다.
- 문제 이해도
- 코드 구현 능력
- 효율적인 해결 방안 도출 능력

알고리즘의 표현 방법

알고리즘을 다른 사람에게 전달하거나 구현하려면, 그 과정을 명확하고 간결하게 표현하는 것이 중요합니다. 이를 위해 자주 사용하는 대표적인 방법이 의사코드와 자연어 표기법입니다.

의사코드란

의사코드는 프로그래밍 언어와 유사하지만 더 자유로운 형태의 표현 방식입니다.

특징

특정 프로그래밍 언어의 문법을 엄격히 지키지 않아도 됩니다.
단계별 논리 흐름을 구조적으로 표현하기에 좋습니다.
실제 코드로 옮기기 수월합니다.

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

자연어 표기법이란

자연어 표기법은 일상적인 언어를 사용하여 알고리즘을 설명하는 방식입니다.

특징

비전문가도 쉽게 이해할 수 있습니다.
전체적인 흐름이나 핵심 아이디어를 빠르게 전달하기 좋습니다.
다만, 문장이 모호해질 수 있으므로 정확한 표현에 신경 써야 합니다.

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

좋은 알고리즘의 조건

정확성

입력한 값에 대해 올바른 결과가 나와야 합니다.
정해진 단계를 따라 실행되고, 반드시 멈추는 시점이 있어야 합니다.
같은 입력값이면 항상 같은 결과가 나와야 합니다.

효율성

시간 복잡도: 실행 시간이 너무 오래 걸리지 않아야 합니다.
공간 복잡도: 컴퓨터의 메모리를 적절하게 사용해야 합니다.

명확성

각 단계가 명확하고 이해하기 쉬워야 합니다.
다른 사람도 읽고 이해할 수 있어야 합니다.
필요한 경우 주석으로 설명을 추가하면 좋습니다.

확장성

다양한 상황에서 사용할 수 있어야 합니다.
나중에 수정하거나 개선하기 쉬워야 합니다.
문제가 생겼을 때 어디가 잘못됐는지 찾기 쉬워야 합니다.

알고리즘 성능 분석

알고리즘이 얼마나 효율적으로 동작하는지를 측정하는 방법입니다. 주로 시간과 공간을 기준으로 평가합니다.

빅오 표기법

알고리즘의 시간 복잡도를 수학적으로 표현한 방법입니다. 주로 입력데이터의 크기가 늘어날 때 알고리즘의 실행 시간이 어떤 비율로 증가하는지를 표현합니다. 즉, 정확한 실행 시간이 아닌, 입력 데이터의 크기에 따라서 실행 시간의 증가 추세를 표현합니다.

시간복잡도	대표 알고리즘	특징
O(1)	배열 인덱스 접근, 스택/큐 삽입/삭제	입력 크기와 관계없이 항상 같은 시간
O(log N)	이진 탐색, 균형 이진 탐색 트리	입력이 커져도 시간이 로그 값으로 증가
O(N)	배열 순차 탐색, 최대/최소값 찾기	입력과 시간이 비례하여 증가
O(N log N)	병합정렬, 퀵소트, 힙정렬	가장 효율적인 비교 기반 정렬 알고리즘
O(N²)	버블정렬, 삽입정렬, 선택정렬	입력이 커지면 입력 크기의 제곱으로 시간 증가
O(2^N)	부분 집합 생성	입력이 커지면 지수적으로 증가
O(N!)	순열 생성	입력이 증가할 때마다 시간이 팩토리얼로 폭발적 증가

시간 복잡도

명령문 개수 계산
- 반복문, 조건문, 대입문 등 명령문이 실행되는 횟수를 계산합니다.
- 각 줄의 실행 횟수를 더하여 전체 실행 횟수를 구합니다.

   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² 번 실행됨
           }
       }
   }
}

알고리즘 풀이 방법

알고리즘 문제를 해결할 때 가장 큰 실수는 문제를 제대로 이해하지 않고 바로 코딩을 시작하는 것입니다. 이는 문제의 전체 흐름을 파악하지 않고 부분적으로만 구현하게 됩니다.

문제 분석의 중요성

문제의 제약 조건을 놓치면 정확성과 효율성 모두를 놓치게 됩니다.
문제의 전체 구조를 보지 못하고 부분적인 해결에만 집중하게 됩니다.
잘못된 방향의 구현은 디버깅과 수정에 많은 시간이 소요됩니다.

문제 해결 아이디어 설계의 중요성

문제의 전체 흐름을 파악해야 모든 예외 상황을 고려할 수 있습니다.
복잡한 문제일수록 전체적인 로직을 먼저 설계하고, 이를 단계별로 구현하는 것이 중요합니다.
실무에서도 체계적인 설계없이 구현하념 유지보수가 어려워지고, 버그 발생 가능성이 높아집니다.

알고리즘 문제 해결 5단계

1단계: 문제 이해 및 요구사항 분석하기
     - 문제를 천천히 정독하기
     - 예제 입출력을 통해 문제의 의도 파악하기
     - 주어진 입력과 출력 형식을 정확히 파악하기
     - 제약 조건과 요구사항, 규칙 정리하기

2단계: 접근 방법 구상하기
     - 비슷한 유형의 문제 생각하기
     - 어떠한 유형의 알고리즘을 사용할지 정하기
     - 문제를 해결하기 위한 기본 아이디어 고안 혹은 문제 해결 절차에 대해 단계별로 나누기 및 도식화
     
3단계: 세부 구현 설계 및 검토하기
     - 문제 해결 절차의 각 단계를 의사코드로 표현하기
     - 발생할 수 있는 예외 상황 찾아보기
     - 극단적인 케이스 고려하기
     - 시간 복잡도 분석하기 

4단계: 코드 작성 및 구현하기
     - 세부 구현으로 표현된 아이디어를 실제 코드로 작성하기
     - 구현 과정에서 변수명, 함수명을 명확하게 작성하기

5단계: 테스트와 디버깅
     - 다양한 테스트 케이스를 통해 코드의 정확성을 검증하기
       * 예시 입출력으로 테스트하기
       * 극단적인 케이스로 테스트하기
     - 오류가 발생하면 디버깅하기
     - 시간 초과의 경우 아이디어 수정 및 코드 최적화하기
       * 효율적인 입력 처리 고려
       * 적절한 자료구조 선택
       * 중복 계산 방지 (메모이제이션) 
       * 유망하지 않은 탐색 가지치기 (백트래킹)

알고리즘 유형

구현 & 시뮬레이션

구현: 문제의 요구사항을 실제 동작하는 코드로 구현하는 능력이 중요합니다.
시뮬레이션: 문제에서 요구하는 시나리오, 절차를 차례대로 실행하는 능력이 요구됩니다.

특징

코딩 테스트에서 가장 기본이 되는 문제 유형입니다.
알고리즘적 난이도보다는 구현의 정확성이 중요합니다.
요구사항을 빠짐없이 코드로 옮기는 것이 핵심입니다.
문제의 조건과 제약을 정확히 이해하고 처리해야 합니다.

주의

구현 과정에서 자잘한 실수를 하기 쉽기 때문에 꼼꼼함이 중요합니다.
디버깅을 통한 중간 결과 검증이 매우 중요합니다.
구현 / 시물레이션 문제를 해결할 때 가장 많이 하는 실수는 문제의 전체 흐름을 파악하지 않고 부분적으로 구현하는 것입니다.

구현 및 시뮬레이션의 주요 유형

단순 구현: 주어진 알고리즘이나 규칙을 그대로 코드로 옮기는 문제입니다.
완전 시뮬레이션: 문제에서 제시된 과정을 처음부터 끝까지 실행하여 결과를 도출하는 문제입니다.
상태 변환 시뮬레이션: 특정 조건에 따라 시스템의 상태가 변화하는 과정을 구현하는 문제입니다.
규칙 찾기 및 구현: 문제의 숨겨진 규칙을 찾아 이를 코드로 구현하는 문제입니다.

완전 탐색

모든 경우의 수를 빠짐없이 조사하여 정답을 찾는 방법입니다.

특징

모든 경우를 시도하므로, 정답을 놓칠 가능성이 없습니다.
입력 규모가 작을 때 유리하며, 구현이 비교적 간단합니다.

구현 방법

반복문을 이용한 구현
재귀 함수를 이용한 구현

대표적인 문제 유형

순열 / 조합 계산
부분집합 계산
그래프 전체 탐색

그리디 알고리즘

매 순간 가장 최선의 선택을 함으로써 전체 최적해를 구하는 방식입니다.

특징

다른 알고리즘 보다 일반적으로 구현이 간단하고, 빠른 시간 안에 결과를 얻을 수 있습니다.

적용 조건

탐욕 선택 속성: 매 순간이 최선의 선택이 전체 문제의 최적해가 되어야 합니다.
최적 부분 구조: 부분 문제의 최적해들을 결합해 전체 문제의 최적해를 구할 수 있어야 합니다.

대표적인 문제 유형

거스름돈 계산
회의실 배정 문제
최소 신장 트리

백트래킹

완전 탐색을 기반으로 하되, 유망하지 않은 경우는 미리 배제하여 탐색 효율을 높이는 기법입니다.

특징

조건을 만족할 수 없는 상황을 빠르게 배제할 수 있어, 탐색 범위를 크게 축소할 수 있습니다.
대부분 재귀 함수로 구현합니다.

적용 조건

상태 공간 트리 구성 가능성
- 문제의 해결 과정을 트리 형태로 구조화할 수 있어야 합니다.
- 각 단계별 선택지를 명확하게 정의할 수 있어야 합니다.
유망성 판단 기준
- 현재 상태에서 더 진행할 가치가 있는지 판단할 수 있는 명확한 기준이 있어야 합니다.
가지치기 효율성
- 유망하지 않은 경우를 제외했을 때 탐색 범위가 충분히 줄어들어야 합니다.
- 가지치기 조건 검사가 너무 복잡하지 않아야 합니다.

대표적인 문제 유형

N-Queen 문제
스도쿠 문제 풀이
부분집합의 합

분할 정복

문제를 작거나 유사한 하위 문제로 분할하고, 각 문제를 해결한 뒤 결과를 합쳐 최종 해를 구하는 방식입니다.

특징

분할 → 정복 → 병합 단계를 거칩니다.
분할된 각 부분 문제는 서로 독립적이어야 합니다.

적용 조건

분할 가능성
- 문제가 동일한 유형의 더 작은 하위 문제들로 나눠질 수 있어야 합니다.
- 분할된 문제는 원래 문제와 같은 성질을 가져야 합니다.
하위 문제의 독립성
- 분할된 하위 문제들은 서로 독립적이어야 합니다.
- 어떤 하위 문제의 해결이 다른 하위 문제의 해결에 영향을 주지 않아야 합니다.
병합 가능성
- 하위 문제들의 해답을 병합하여 원래 문제의 해답을 만들 수 있어야 합니다.

대표적인 문제 유형

병합 정렬
퀵 정렬
이진 탐색

동적 계획법

큰 문제를 작은 부분 문제들로 나누고, 각 부분 문제의 해를 저장하여 재활용함으로써 전체 문제의 최적 해를 구하는 알고리즘 설계 기법입니다.

특징

중복 계산을 획기적으로 줄일 수 있어, 지수 시간이 걸리는 문제도 다항 시간 안에 풀 수 있는 경우가 많습니다.
Top-Down 방식 또는 Bottom-up 방식으로 구현합니다.
점화식을 올바르게 세우는 것이 핵심입니다.

적용 조건

최적 부분 구조
- 작은 부분 문제들의 최적해들을 조합하여 큰 문제의 최적해를 구할 수 있어야 합니다.
중복되는 부분 문제
- 동일한 작은 무제들이 반복적으로 나타나야 합니다.
- 이러한 중복 문제들의 해를 저장해두고 재활용할 수 있어야 합니다.

대표적인 문제 유형

수열문제
최적화 문제
경로 문제

이준연

반갑습니다!

이전 포스트

TIL-25.12.18

다음 포스트

TIL-25.12.19

학습 키워드

알고리즘

알고리즘의 중요성

알고리즘의 표현 방법

좋은 알고리즘의 조건

알고리즘 성능 분석

알고리즘 풀이 방법

알고리즘 유형

TIL-25.12.18

TIL-25.12.22

0개의 댓글