Algorithms: 1장 알고리즘 정리

유클리드 알고리즘

두 수의 차/나머지를 반복해서 구하는 빠른 방법

• 핵심 아이디어: 두 수의 GCD는 그 차의 GCD와 같다, 또는 gcd⁡(a,b)=gcd⁡(b,amod  b)gcd(a,b)=gcd(b,amodb)로 계산
• 반복해서 나머지가 0이 될 때까지 진행하면 최종적으로 GCD가 나옴

---

피보나치 수열

1️⃣ 피보나치 수열의 정의: 앞의 두 항을 더해 다음 항을 만드는 수열

2️⃣ 재귀적 접근 (Recursive)

3️⃣ 반복적 접근 (Iterative)

왜 i가 3부터 시작하는가?

• int a = 1, b = 1, temp;
• a → F(1)
• b → F(2)
• 즉, 이미 첫 번째와 두 번째 항을 변수로 가지고 있는 상태예요.
• 이제 3번째 항부터 계산을 시작해야 합니다.

4️⃣ 메모이제이션 (Memoization, 개선된 재귀)

정리

방식	코드구조	시간복잡도	공간복잡도	특징
반복 (Iterative)	for문	O(n)	O(1)	가장 효율적, 간단
재귀 (Recursive)	자기 호출	O(2^n)	O(n)	이해 쉬우나 매우 느림
메모이제이션	재귀 + 캐시	O(n)	O(n)	속도 빠르고 깔끔한 코드

 

---

주어진 정수 N이 소수인지 아닌지를 판별하는 방법

(1) 2부터 N-1까지 나눠보기

가장 단순한 방법이에요 👇

• 2부터 N-1까지의 모든 수로 N을 나눠서
  나머지가 0인 수가 하나라도 있으면 → 소수가 아님
• 끝까지 없으면 → 소수

📘 예: N = 7
→ 2, 3, 4, 5, 6으로 나눠봄
→ 나누어떨어지는 수 없음 → ✅ 소수

➡️ 하지만 이 방법은 비효율적 (시간 복잡도 O(N))

(2) 2부터 N/2까지만 검사

조금 더 효율적으로!

• N의 절반보다 큰 수는 N을 나눌 수 없어요.
• 왜냐하면 어떤 수 A가 N을 나누려면, B = N / A 도 존재해야 하는데
  만약 A가 N/2보다 크면 B는 2보다 작기 때문에 (1.x~) 정수가 안 됨.

📘 예: N=10
→ 2~5까지만 검사하면 됨.
6~9는 N/2보다 크니까 검사 불필요.

➡️ 계산 횟수가 절반으로 줄어요. (시간 복잡도 약 O(N/2))

(3) 2부터 √N까지만 검사

가장 효율적이고 정석적인 방법이에요 ⚡

왜 √N까지만 확인해도 될까?

• 만약 N이 소수가 아니라면,
  N은 두 수의 곱으로 표현될 수 있음:N=a×bN = a \times bN=a×b
• 그런데 두 수 중 하나는 반드시 √N보다 작거나 같아요.
  (예: 36 = 6 × 6, 또는 4 × 9 → 4는 √36=6보다 작음)
• 즉, √N 이하의 수에서 이미 약수가 나오지 않으면
  그 이상에서는 절대 약수가 안 나옵니다.

📘 예: N = 36
√N = 6
→ 2, 3, 4, 5, 6까지만 확인하면 충분해요.
→ 2로 나누어짐 → ❌ 소수 아님

---

에라토스테네스의 체 (Sieve of Eratosthenes)

소수를 찾는 효율적인 알고리즘.
소수가 아닌 수(합성수)를 ‘체로 걸러내듯이’ 지워 나가는 방식

 

🔹 기본 원리

1. 2부터 N까지의 모든 수를 “남아 있는 후보”로 둠
2. 2부터 시작해서, 아직 지워지지 않은 수를 소수로 확정
3. 그 소수의 배수들을 전부 제거 (2×2, 2×3, 2×4, …)
4. 다음으로 남은 수(지워지지 않은 첫 번째 수)를 소수로 확정
5. 이 과정을 √N까지만 반복
   (왜냐하면 √N보다 큰 수는 이미 작은 수의 배수로 걸러지기 때문)

🔹 예시: 53 이하의 수

1. 처음엔 모든 수를 남겨둔다.
   (2, 3, 4, 5, 6, 7, 8, 9, 10, ... , 53)
2. 소수 2 확정 → 2의 배수 제거 (4,6,8,10,...)
3. 다음 소수 3 → 3의 배수 제거 (9,12,15,18,...)
4. 다음 소수 5 → 5의 배수 제거 (25,30,35,...)
5. √53 ≈ 7이므로 7까지만 검사

🔹 시간 복잡도

• 각 소수 p마다 배수를 제거하는 연산: 약 N/p번
• 전체 연산 횟수:

---

제곱 ㄴㄴ 수 (BOJ 1016)

“어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때”
그 수를 제곱 ㄴㄴ 수(제곱 인수가 없는 수) 라고 해요.

 

예시:

10	없음	✅
12	4 (2²)로 나눠짐	❌
18	9 (3²)로 나눠짐	❌
30	없음	✅

문제 설명

• 주어진 구간 [min, max] 안에서
  제곱 ㄴㄴ 수의 개수를 구하는 문제
• 예: [1, 10] → 제곱 ㄴㄴ 수 = 7개 (1, 2, 3, 5, 6, 7, 10)

 접근 방법

1. min~max 범위를 배열로 표시 (check[])
2. 2², 3², 4², 5², … ≤ max 인 제곱수를 전부 구함
3. 각 제곱수의 배수를 모두 check에서 제거 (true로 표시)
4. 남은 수(=제곱수로 나누어지지 않은 수)를 카운트

예제

[min, max] = [11, 24]

1️⃣ 제곱수 후보: 2²=4, 3²=9, 4²=16
2️⃣ 각 제곱수의 배수 제거:

• 4의 배수: 12, 16, 20, 24
• 9의 배수: 18
• 16의 배수: 16 (이미 제거됨)

남는 수 → 11, 13, 14, 15, 17, 19, 21, 22, 23
✅ 9개

코드 구조 (C++)

핵심 로직 요약

i * i <= max	가능한 제곱수만 사용
start_index = min / pow (+1)	구간 내 첫 배수를 찾음
check[j * pow - min] = true	해당 수를 제곱수 배수로 표시
마지막에 check가 false인 수만 카운트	✅ 제곱 ㄴㄴ 수

시간 복잡도

• √max 이하의 제곱수만 탐색
• 각 제곱수의 배수 제거는 (max–min)/pow번 수행
• 전체적으로 O(√max) 정도로 빠름 
  (범위 [max–min] ≤ 1,000,000 조건 내에서 충분히 통과)

결론 요약

알고리즘	목적	핵심	복잡도
에라토스테네스의 체	소수 판별	배수 제거 방식	O(N log log N)
제곱 ㄴㄴ 수	제곱 인수 없는 수 개수	제곱수 배수 제거	O(√N)

---

재귀(Recursion)란?

“자기 자신을 호출하는 함수”

 

재귀는 큰 문제를 작은 문제로 쪼개서 푸는 방법

예를 들어 “1부터 n까지의 합”을 구하고 싶을 때:

• n = 5라면
  → 1 + 2 + 3 + 4 + 5
  → (1 + 2 + 3 + 4) + 5
  → 즉, “n-1까지의 합 + n” 형태로 반복됨

그래서 식으로는:
[sum(n) = n + sum(n-1)]
단, 끝나는 조건(종료 조건) 이 꼭 필요
그게 없으면 계속 자기 자신을 부르다가 “무한 호출 → Stack Overflow 오류”가 발생

 

예를 들어

if (n == 1)
  return 1;
else
  return n + sum(n-1);

이런 형태로 “언제 멈출지”를 명시해야 함

---

예시: 1부터 n까지의 합

 

반복문 버전

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

👉 단순히 for문으로 반복하면서 더해감.

 

재귀 버전

int sum(int n) {
    if (n == 1)
        return 1;            // 종료 조건
    else
        return n + sum(n - 1);  // 자신을 호출
}

예를 들어 sum(3)을 계산하면:

sum(3)
= 3 + sum(2)
= 3 + (2 + sum(1))
= 3 + (2 + 1)
= 6

➡ 이렇게 함수가 자기 자신을 계속 호출하다가, n==1일 때 멈추고 되돌아가며 계산이 완료

n이 0이면?

n이 0일 때는 “아무 것도 더할 게 없다”는 뜻이니까

if (n <= 0)
    return 0;

로 설정해두면 안전

---

예시: 팩토리얼 (Factorial)

팩토리얼은 “n! = n × (n-1) × (n-2) × … × 1” 

반복문 버전

int factorial(int n) {
    int fact = 1;
    for(int i = 2; i <= n; i++)
        fact *= i;
    return fact;
}

재귀 버전

int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

예:

factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * 1)
= 6

---

재귀가 메모리에서 작동하는 방식

 

프로그램이 실행될 때 메모리는 프로세스 주소 공간으로 나뉨

구역	설명
코드(code)	실행 명령어 저장
데이터(data)	전역 변수, static 변수
힙(heap)	new, malloc으로 생성된 동적 메모리
스택(stack)	함수 호출 시 임시 저장 공간 (매개변수, 지역 변수 등)

 

재귀 함수는 스택을 계속 쌓음

예를 들어 sum(3)을 호출할 때:

sum(3)	n=3
sum(2)	n=2
sum(1)	n=1

→ sum(1)에서 종료 조건을 만나면
스택이 하나씩 되돌아가며 (pop) 결과를 합침

그래서 재귀는 “메모리(스택)를 많이 사용한다”는 단점

---

반복문 vs 재귀의 메모리 효율

반복문	메모리 적게 사용	코드가 길어질 수 있음
재귀	코드 간결, 수학적 표현 쉬움	스택 많이 사용 (깊은 재귀 → StackOverflow 위험)

 

재귀 함수 실행 예시 (스택 변화 시각화)

sum(3) 실행 시:

main()
 └─ sum(3)
     └─ sum(2)
         └─ sum(1)

되돌아올 때:

sum(1) → 1 반환
sum(2) → 2 + 1 = 3 반환
sum(3) → 3 + 3 = 6 반환

---

배열 누적합 예시 (Java 버전)

public class SumMain {
    static int sumA(int[] arr, int index){
        if(index == 0)
            return arr[index];
        else{
            arr[index] += sumA(arr, index - 1);
            return arr[index];
        }
    }

    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5,6};
        int index = arr.length - 1;
        sumA(arr, index);
        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

 

실행 과정:

호출 순서 배열 상태

sumA(arr, 5)	arr[5] += sumA(arr, 4)
sumA(arr, 4)	arr[4] += sumA(arr, 3)
…
sumA(arr, 0)	리턴 1

마지막 결과:

[1, 3, 6, 10, 15, 21]

즉, 각 원소가 앞의 모든 원소의 누적합으로 바뀜