반응형
포맷(개념 → 절차/의사코드 → 수행 과정/핵심 논리 → 복잡도/정리 → 주의점)으로 요약 없이 체계적 재배열로 정리합니다.
0. 알고리즘의 유래와 개념
유래
- “알고리즘(algorithm)”은 9세기 페르시아 수학자 **알콰리즈미(al-Khwarizmi)**의 이름에서 유래.
- 최초의 알고리즘 예: 기원전 300년경 유클리드의 최대공약수(GCD) 알고리즘.
알고리즘이란?
- 문제를 해결하기 위한 단계적 절차(요리 레시피와 유사: 정해진 순서대로 수행하면 해에 도달).
- 효율성이 핵심: 같은 문제라도 더 적은 자원(시간/공간)으로 해결하는 방법이 중요.
1.1 최대 숫자 찾기 — 순차 탐색(최댓값)
문제
- 카드/배열의 값들 중 가장 큰 숫자 찾기.
절차
- max ← -∞(또는 첫 원소).
- 왼쪽부터 차례대로 보며 max = max(max, A[i]).
- 끝까지 보면 max가 답.
의사코드
BinarySearch(A[1..n], K):
L=1; R=n
while L ≤ R:
mid = ⌊(L+R)/2⌋
if A[mid] == K: return mid
elif A[mid] > K: R = mid-1
else: L = mid+1
return NOT_FOUND
복잡도
- 시간: 모든 원소 1회 확인 → O(n)
- 공간: O(1)
1.2 임의의 숫자 찾기 — 순차 탐색 vs 이진 탐색
A. 순차 탐색 (정렬 정보 없이)
- 왼쪽부터 차례대로 비교하여 찾음(최대 n번 비교).
- 시간 O(n), 공간 O(1).
B. 이진 탐색 (정렬되어 있을 때)
아이디어
- 정렬(오름차순)된 배열에서 중간값과 K 비교:
- 같으면 성공,
- K가 작으면 왼쪽 절반,
- 크면 오른쪽 절반을 재귀/반복.
의사코드
BinarySearch(A[1..n], K):
L=1; R=n
while L ≤ R:
mid = ⌊(L+R)/2⌋
if A[mid] == K: return mid
elif A[mid] > K: R = mid-1
else: L = mid+1
return NOT_FOUND
복잡도
- 매 단계 1/2로 줄임 → O(log n)
- 배열 임계조건: 정렬되어 있어야 함.
1.3 동전 거스름돈 — 그리디
문제
- 금액 W를 동전 개수 최소로 거슬러 주기(예: 500,100,50,10,1원).
그리디 절차
- 남은 금액을 넘지 않는 범위에서 가장 큰 액면부터 최대한 사용.
- 남은 금액을 다음 액면으로 반복.
예: W=730
- 500×1 → 100×2 → 10×3 → 총 6개.
복잡도
- 액면 종류가 상수면 **O(W/최대액면)**에 비례(실무적으론 상수 시간).
- 주의: 임의의 화폐 체계에서는 항상 최적이 아님(반례 존재). 실제 통화는 보통 그리디가 최적이 되도록 설계.
1.4 한붓그리기 — 오일러 경로/서킷 관점
문제
- 연필을 떼지 않고, 모든 간선을 정확히 한 번씩 지나 출발점으로 돌아오기(또는 한 번만 통과) 가능한가?
핵심 개념(그래프 이론)
- 오일러 서킷: 모든 간선을 한 번씩 지나 시작=끝으로 돌아옴.
- 오일러 경로: 모든 간선을 한 번씩 지나지만 시작≠끝 가능.
- 조건
- 서킷: 모든 정점의 차수 짝수, 그래프 연결.
- 경로: 홀수 차수 정점이 정확히 2개, 그래프 연결.
진행 규칙(직관적 전략)
- 현재 정점에서 돌아오는 사이클이 있으면 그 방향으로 진행,
- **외길(인접 1개)**이면 사이클 체크 없이 진행.
- 직감적 규칙은 Hierholzer 알고리즘과 연결됨.
1.5 미로 찾기 — 오른손 법칙
문제
- 표식/실타래 없이 미로 출구 찾기.
전략
- 오른손(또는 왼손) 법칙: 한 손을 항상 벽에 댄 채 전진.
- 종이상 한 면(벽)이 쭉 연결된 단일 경계를 따라가면 언젠가 출구에 도달.
- 단, 분리된 벽(섬)이 있는 미로나 출구가 내부 섬 상황 등 일부 구조에서는 실패할 수 있음(일반 “단순 연결 경계” 가정에서 유효).
구현 팁
- 실제 구현은 방향 유지 + 좌/전/우/후 우선순위 규칙으로 시뮬레이션 가능.
1.6 가짜 동전 찾기 — 분할정복(저울)
문제
- 겉보기 동일, 하나만 가벼운 가짜. 양팔 저울 최소 횟수로 가짜 찾기.
나이브 아이디어들의 한계
- 1개씩 비교: 최악 n-1회.
- 두 개씩 짝지어 비교: 최악 n/2회.
분할정복(반으로 나누어 달기)
- 동전을 두 더미로 1/2:1/2 나눠 저울.
- 가벼운 쪽에 가짜 존재 → 다시 반으로 분할 반복.
- 1개 남으면 가짜.
복잡도
- 매번 1/2로 감소 → ⌈log₂ n⌉ 번 저울질.
- 예: n=1024 → 10번.
1.7 독이 든 술단지 — 비트 코딩(단 1주 안에 탐지, 희생 최소)
문제
- 많은 술단지 중 정확히 1개에 독.
- 아주 조금만 마셔도 1주일 뒤 사망.
- 조건: 일주일 만에 독이 든 단지를 알아내야 하며, 희생 신하 수 최소.
핵심 통찰
- 한 신하가 한 단지만 맛보아야 한다는 제약은 없다.
- 단 한 번의 실험(1주)로 결과가 나와야 하므로, 이진(비트) 코딩으로 병렬 측정한다.
절차(비트 할당)
- 단지에 0..n-1 번호 부여(이진수).
- k번째 비트가 1인 단지들의 술을 신하 k가 섞어서 마심(신하는 여러 단지를 맛볼 수 있음).
- 1주 뒤 죽은 신하들의 비트 위치가 1, 산 신하는 0 → 죽음 패턴의 이진수가 독 단지 번호.
필요한 신하 수
- 단지 수 n이면, 신하 수 = ⌈log₂ n⌉ (모두 생존 포함 2^k 패턴으로 n개 식별).
- 예: 8개 → 신하 3명 (A,B,C). 예시처럼 A/B/C가 맛본 집합을 구성.
장점
- **단 1회의 실험(1주)**으로 식별.
- 희생자 수 최대 ⌈log₂ n⌉(상황에 따라 일부 생존).
부록: 각 절 핵심 알고리즘/공식 모음
- 순차 탐색(최댓값/임의값): O(n)
- 이진 탐색: O(log n), 정렬 전제
- 그리디 거스름돈: 표준 액면 체계에서 최적, 반례 주의
- 한붓그리기(Euler):
- 서킷: 모든 정점 짝수 차수
- 경로: 홀수 2개
- 미로 오른손 법칙: 단순 연결 경계에서 항상 출구 도달
- 가짜 동전(저울): **⌈log₂ n⌉**번
- 독 술단지(1주 내 식별): 신하 ⌈log₂ n⌉, 비트 코딩