알고리즘 학습 - 1

KYJTHEYJ

Dec 23, 2025

Contents

좋은 알고리즘을 위해 시간 복잡도, 공간 복잡도 알고리즘 유형

좋은 알고리즘을 위해

자연어 표기법으로 논리적 사고를 늘려볼 것
정확성
- 입력한 값에 대해 항상 같은 결과가 도출되어야 함
- 정해진 단계를 실행하고 멈추는 단계가 있어야함
효율성
- 시간 복잡도
  - 실행 시간이 적어야 한다
- 공간 복잡도
  - 메모리의 사용이 남발되지 않아야 한다
명확성
- 각 단계가 명확해야 한다
- 타인도 이해하기 쉬워야 한다
확장성
- 다양한 상황에서 사용 가능해야 한다
- 재사용성이 용이해야 한다
- 디버깅이 쉬워야 한다

시간 복잡도, 공간 복잡도

Big-O 표기법

알고리즘의 시간 복잡도를 수학적으로 표현한 것

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

명령문 개수에 따라 계산이 달라진다

반복문, 조건문, 대입문 등 각각 명령문이 실행되는 횟수를 계산

각 실행 횟수를 더하여 전체 실행 횟수를 구함

가장 큰 항만 남겨 계산

for(int i = 0; i < n; i++) {
  sum += i;
}

System.out.println(sum);

- i 변수 초기화 1번 -> 1
- for 반복문 순차 탐색 -> n+1
- sum 초기화 -> 1

가장 큰 항 -> for 반복문 순차 탐색 n

즉, O(N)

시간복잡도	데이터 크기 상한	알고리즘 예시	비고
O(log N)	10^18 (64비트 정수 최대값)	이진 탐색, 균형 이진 탐색 트리	N이 매우 커도 빠르게 동작
O(N)	10^8 (1억)	배열 순회, 1중 반복문	1초에 수행 가능
O(N log N)	10^6 (백만)	병합정렬, 퀵정렬	N=10^7에서 2.3초 소요
O(N^2)	10^4 (만)	버블정렬, 2중 반복문	1초 정도 소요
O(2^N)	20	부분집합 생성	N=30만 되어도 10초 소요
O(N!)	10	순열 생성	N이 조금만 커져도 시간이 기하급수적 증가

알고리즘 유형

구현(Implementation) & 시뮬레이션(Simulation)
- 요구사항을 정확히 코드로 구현, 시나리오를 차례대로 실행하고자 하는 경우
  - 코딩 테스트의 기본, 정확성이 중요, 요구사항을 전부 코드로 만들기
  - 단순 구현, 완전 시뮬레이션, 상태 변화, 규칙 찾기 문제에 사용
완전 탐색(Brute Force)은 입력 규모가 작고 모든 경우를 시도해도
시간 내에 해결 가능한 경우 확실한 해법을 보장하는 방법
- 모든 경우의 수를 빠짐 없이 조사하여 정답을 찾는 방법
  - 순열/조합 계산, 부분집합 계산, 그래프 탐색 문제에 사용
그리디(Greedy)는 탐욕 선택 속성 및 최적 부분 구조를 만족할 때
빠르고 직관적인 해법을 제공
- 매 순간 가장 최선의 선택을 하여 최적해를 구하는 방법
- 구현이 간단하고 빠른 시간 안에 결과를 얻음
  - 거스름돈 계산하기 → 큰 동전 부터 사용하기, 회의실 배정 하기 문제
  - 크루스칼, 프림 알고리즘
백트래킹(Backtracking)은 가지치기를 통한 효율적 완전 탐색에 적합
- 스도쿠, 부분집합의 합, 퀸이 서로 공격하지 않게하는 N-Queen 문제
분할 정복(Divide and Conquer)은
문제를 독립된 하위 문제로 분할할 수 있을 때 사용
- 문제를 작고 유사한 하위 문제로 분할, 각 문제를 해결하고 결과를 합침
- 분할 → 정복 → 병합의 과정을 거친다
- 이 때 하위로 나뉘어진 문제는 서로 독립적이여야함
- 병합시 원래 문제의 해답을 만들 수 있어야 함
  - 병합 정렬, 퀵 정렬, 이진탐색 문제
동적 계획법(DP)은 최적 부분 구조와 중복되는 부분 문제가 존재할 때 사용
- 큰 문제를 작은 부분 문제로 나누고, 각 부분의 문제 해를 저장하여 재활용
- 탑-다운 방식, 바텀-업 방식, 점화식
  - 피보나치 수열, 배낭 무게제한 문제, 미로찾기 문제

알고리즘 문제를 바로 코딩 하지 말고 흐름을 파악해야 전체적으로 구현이 가능하다

Contents

좋은 알고리즘을 위해 시간 복잡도, 공간 복잡도 알고리즘 유형

좋은 알고리즘을 위해

자연어 표기법으로 논리적 사고를 늘려볼 것

정확성

입력한 값에 대해 항상 같은 결과가 도출되어야 함
정해진 단계를 실행하고 멈추는 단계가 있어야함

효율성

시간 복잡도
- 실행 시간이 적어야 한다
공간 복잡도
- 메모리의 사용이 남발되지 않아야 한다

명확성

각 단계가 명확해야 한다
타인도 이해하기 쉬워야 한다

확장성

다양한 상황에서 사용 가능해야 한다
재사용성이 용이해야 한다
디버깅이 쉬워야 한다

시간 복잡도, 공간 복잡도

Big-O 표기법

알고리즘의 시간 복잡도를 수학적으로 표현한 것

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

명령문 개수에 따라 계산이 달라진다

반복문, 조건문, 대입문 등 각각 명령문이 실행되는 횟수를 계산

각 실행 횟수를 더하여 전체 실행 횟수를 구함

가장 큰 항만 남겨 계산

for(int i = 0; i < n; i++) {
  sum += i;
}

System.out.println(sum);

- i 변수 초기화 1번 -> 1
- for 반복문 순차 탐색 -> n+1
- sum 초기화 -> 1

가장 큰 항 -> for 반복문 순차 탐색 n

즉, O(N)

시간복잡도	데이터 크기 상한	알고리즘 예시	비고
O(log N)	10^18 (64비트 정수 최대값)	이진 탐색, 균형 이진 탐색 트리	N이 매우 커도 빠르게 동작
O(N)	10^8 (1억)	배열 순회, 1중 반복문	1초에 수행 가능
O(N log N)	10^6 (백만)	병합정렬, 퀵정렬	N=10^7에서 2.3초 소요
O(N^2)	10^4 (만)	버블정렬, 2중 반복문	1초 정도 소요
O(2^N)	20	부분집합 생성	N=30만 되어도 10초 소요
O(N!)	10	순열 생성	N이 조금만 커져도 시간이 기하급수적 증가

알고리즘 유형

구현(Implementation) & 시뮬레이션(Simulation)

요구사항을 정확히 코드로 구현, 시나리오를 차례대로 실행하고자 하는 경우
- 코딩 테스트의 기본, 정확성이 중요, 요구사항을 전부 코드로 만들기
- 단순 구현, 완전 시뮬레이션, 상태 변화, 규칙 찾기 문제에 사용

완전 탐색(Brute Force)은 입력 규모가 작고 모든 경우를 시도해도
시간 내에 해결 가능한 경우 확실한 해법을 보장하는 방법

모든 경우의 수를 빠짐 없이 조사하여 정답을 찾는 방법
- 순열/조합 계산, 부분집합 계산, 그래프 탐색 문제에 사용

그리디(Greedy)는 탐욕 선택 속성 및 최적 부분 구조를 만족할 때
빠르고 직관적인 해법을 제공

매 순간 가장 최선의 선택을 하여 최적해를 구하는 방법
구현이 간단하고 빠른 시간 안에 결과를 얻음
- 거스름돈 계산하기 → 큰 동전 부터 사용하기, 회의실 배정 하기 문제
- 크루스칼, 프림 알고리즘

백트래킹(Backtracking)은 가지치기를 통한 효율적 완전 탐색에 적합

스도쿠, 부분집합의 합, 퀸이 서로 공격하지 않게하는 N-Queen 문제

분할 정복(Divide and Conquer)은
문제를 독립된 하위 문제로 분할할 수 있을 때 사용

문제를 작고 유사한 하위 문제로 분할, 각 문제를 해결하고 결과를 합침
분할 → 정복 → 병합의 과정을 거친다
이 때 하위로 나뉘어진 문제는 서로 독립적이여야함
병합시 원래 문제의 해답을 만들 수 있어야 함
- 병합 정렬, 퀵 정렬, 이진탐색 문제

동적 계획법(DP)은 최적 부분 구조와 중복되는 부분 문제가 존재할 때 사용

큰 문제를 작은 부분 문제로 나누고, 각 부분의 문제 해를 저장하여 재활용
탑-다운 방식, 바텀-업 방식, 점화식
- 피보나치 수열, 배낭 무게제한 문제, 미로찾기 문제

알고리즘 문제를 바로 코딩 하지 말고 흐름을 파악해야 전체적으로 구현이 가능하다