Chap1 1.1 Algorithms : problem, solution, algorithm

1.1 Algorithms 요약

📌 1. 문제(Problem)

• 어떤 질문 또는 작업(task)에 대한 일반적인 기술
• 예시:
  • 정렬 문제: n개의 숫자가 있는 리스트 S를 비감소 순으로 정렬하라
  • 탐색 문제: 리스트 S 안에 x라는 값이 존재하는지 판단하라

📌 2. 인스턴스(Instance)

• 문제의 특정한 입력 값 집합
• 예:
  • 리스트 S = [10, 7, 8, 11, 5, 13]이고, n = 6인 경우 → 정렬 문제의 인스턴스
  • x = 11인 경우 → 탐색 문제의 인스턴스

📌 3. 해(Solution)

• 인스턴스를 해결한 결과
• 위 예에서 정렬의 결과는 [5, 7, 8, 10, 11, 13]
• 탐색 결과는 “Yes, x is in S”

📌 4. 알고리즘(Algorithm)

• 문제의 모든 인스턴스를 풀 수 있는 일반적인 단계별 절차
• essential 특성 5가지:
  1. 입력(Input): 0개 이상
  2. 출력(Output): 적어도 하나 이상
  3. 명확성(Definiteness): 각 단계는 명확히 정의되어야 함
  4. 유한성(Finiteness): 유한한 시간 내에 종료되어야 함
  5. 정확성(correctiness)
• optional 특성
  1. 효과성(Effectiveness): 각 단계는 실질적으로 수행 가능해야 함
  2. generality

"we must specify a general step-by-step procedure for producing the solution to each instance. This step-by-step procedure is called an algorithm. We say that the algorithm solves the problem."

👉 해석:

우리는 각 문제 인스턴스에 대한 해답을 도출하기 위한 일반적인 단계별 절차를 명확히 해야 한다. 이러한 단계별 절차를 알고리즘(algorithm) 이라고 부른다. 우리는 이 알고리즘이 해당 문제를 해결한다고 말한다.

 

즉, 어떤 문제를 해결하기 위해선 모든 경우에 적용할 수 있는 체계적인 단계들이 필요하고, 그것이 바로 알고리즘이라는 것이다.

---

🔎 예제: Sequential Search

Algorithm SequentialSearch(S, x)
  for i = 1 to n
    if S[i] == x then
      return i
  return 0  // not found

• 리스트에서 x를 처음부터 끝까지 비교
• 단순하지만 비효율적 (특히 리스트가 클 경우)

 

---

🧠 pseudocode(의사코드)란?

📌 정의

pseudocode는 프로그래밍 언어와 자연어의 중간 형태로 작성된 코드입니다.
즉, 사람이 이해하기 쉽게 쓴 코드 형태의 알고리즘 설명이에요.

• 실제로 실행되는 코드는 아니지만
• 컴퓨터 프로그래머가 쉽게 코드를 구현할 수 있도록
• 알고리즘의 논리적인 흐름만을 표현합니다.

---

📍 pseudocode의 특징

특징	설명
언어 중립적	특정 언어(C++, Java, Python 등)에 종속되지 않음
간결함	불필요한 문법을 제외하고 핵심 로직만 표현
명확성	알고리즘의 핵심 구조와 흐름이 잘 드러남
사람 중심	컴퓨터보다 사람이 이해하기 쉬움

---

🧾 예시 비교

💻 실제 C++ 코드

int sequentialSearch(int S[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (S[i] == x)
            return i;
    }
    return -1;
}

📄 pseudocode 버전

Algorithm SequentialSearch(S, x)
  for i = 1 to n
    if S[i] == x then
      return i
  return 0

→ 배열 인덱스도 1부터 시작할 수 있고, 타입 선언도 없고, ;나 {} 같은 문법도 없습니다.
→ 논리만 남기고 문법을 뺀 것이 바로 pseudocode입니다.

---

✨ 왜 pseudocode를 쓰는 걸까?

1. 알고리즘 설명에 집중하기 위해 (프로그래밍 언어 문법은 생략)
2. 다양한 언어 사용자에게 공통된 표현 제공
3. 알고리즘 교재, 논문, 시험 등에서 표준적으로 사용

---

📖 Pseudocode 관련 정리 (26페이지 기준)

---

배열 인덱스는 1부터 사용

• C++에서는 배열 인덱스를 0부터 시작하지만
• Pseudocode에서는 보통 1부터 시작
  → 사람이 리스트를 세는 방식과 자연스럽게 맞춰 설명이 쉬워짐

📌 예시:

Inputs: positive integer n, array of numbers S indexed from 1 to n

---

Pseudocode 문법 특징 정리

 

항목	Pseudocode표현	C++표현
배열 인덱스	1부터	0부터
조건식	if (low ≤ x ≤ high)	if (low <= x && x <= high)
값 교환	exchange x and y	temp = x; x = y; y = temp;

🔎 Pseudocode는 수학적 표현을 그대로 사용하여 간결함과 명확성을 추구함.

---

배열 선언과 사용

• 인덱스 범위를 명확히 표현: S[2..n] ← 2부터 n까지 인덱싱됨
• 2차원 배열도 자유롭게 인덱스 범위 지정 가능
• S[2..n] 표현은 C++에는 없고 pseudocode 전용 표기임

---

데이터 타입 표현 (추상적 표현)

Pseudocode에서는 C++처럼 구체적 타입보다 역할 중심의 타입 명시 사용

타입 이름설명

타입 이름	설명
keytype	정렬/탐색 대상이 되는 키 값 타입
index	배열을 인덱싱하는 정수형 변수
number	정수 또는 실수 모두 포함 가능한 숫자
bool	true / false 값을 가지는 논리형

---

반복문 표현

repeat n times
  ...

 

• C++에서는 for문을 써야 하지만 pseudocode는 의미 중심으로 간단히 표현
• 반복 횟수만 중요할 때 반복 제어 변수 생략 가능

---

함수 vs 프로시저 구분

구분	설명	예시
Function	값을 반환(return)	function Sum(S): number
Procedure	값을 반환하지 않음 (void)	procedure Sort(S)

• 배열 등은 자동으로 참조로 전달되므로 & 안 붙임
• const는 배열이 읽기 전용임을 의미

---

📝 핵심 요약

• pseudocode는 언어에 구애받지 않고 알고리즘 논리를 쉽게 표현하기 위한 도구
• 직관적 표현 + 간결함을 중시
• 수학적 표현 허용 (예: ≤, exchange, repeat 등)
• 구현보다는 알고리즘 이해에 집중해야 할 때 사용

---

💡 예제 알고리즘 정리

---

🔹 Algorithm 1.1: Sequential Search

문제: 배열 S 안에 key x가 있는지 찾아라
입력: 정수 n, 배열 S[1..n], key x
출력: x가 있으면 인덱스, 없으면 0

procedure SequentialSearch(S[1..n], x)
  for i = 1 to n
    if S[i] == x then
      return i
  return 0

📌 특징

• 배열 순서대로 x를 비교함
• 정렬되어 있지 않아도 사용 가능
• 시간복잡도:
  • 최악: O(n)
  • 최선: O(1)

---

🔹 Algorithm 1.2: Add Array Members

문제: 배열 S의 모든 원소의 합을 구하라
입력: 정수 n, 배열 S[1..n]
출력: 합계 sum

function AddArrayMembers(S[1..n]): number  // 함수가 반환하는 값(return value)의 타입
  sum ← 0
  for i = 1 to n
    sum ← sum + S[i]
  return sum

📌 특징

• 합계를 누적하는 단순 반복
• 항상 n번 반복 → 시간복잡도 O(n)

---

🔹 Algorithm 1.3: Exchange Sort

문제: 배열 S를 비감소 순(오름차순)으로 정렬
입력: 정수 n, 배열 S[1..n]
출력: 정렬된 배열 S

procedure ExchangeSort(S[1..n])
  for i = 1 to n-1
    for j = i+1 to n
      if S[j] < S[i] then
        exchange S[i] and S[j]

📌 특징

• 매우 기초적인 정렬 방식
• 모든 쌍을 비교하여 정렬
• 시간복잡도: O(n²)

---

🔹 Algorithm 1.4: Matrix Multiplication

문제: 두 정방 행렬 A, B를 곱하여 C를 구하라
입력: 정수 n, A[n×n], B[n×n]
출력: C[n×n] = A × B

procedure MatrixMultiplication(A[1..n,1..n], B[1..n,1..n], C[1..n,1..n])
  for i = 1 to n
    for j = 1 to n
      C[i,j] ← 0
      for k = 1 to n
        C[i,j] ← C[i,j] + A[i,k] × B[k,j]

 

🎯 목적

두 정방 행렬 A[n×n]과 B[n×n]를 곱하여 결과 행렬 C[n×n]을 구하라.

---

🔎 행렬 곱셈 정의 복습

두 행렬의 곱 C = A × B에서
C[i][j]의 값은 다음과 같이 계산됨:

C[i][j]=A[i][1]⋅B[1][j]+A[i][2]⋅B[2][j]+⋯+A[i][n]⋅B[n][j]C[i][j]=A[i][1]⋅B[1][j]+A[i][2]⋅B[2][j]+⋯+A[i][n]⋅B[n][j]

즉,

• A의 i번째 행과 B의 j번째 열을 곱해서 더한 값

pseudocode 분석

procedure MatrixMultiplication(A[1..n,1..n], B[1..n,1..n], C[1..n,1..n])
  for i = 1 to n                ⟶ C의 행 인덱스
    for j = 1 to n              ⟶ C의 열 인덱스
      C[i,j] ← 0                ⟶ C[i][j] 값 초기화
      for k = 1 to n            ⟶ A와 B의 곱셈에 필요한 인덱스
        C[i,j] ← C[i,j] + A[i,k] × B[k,j]

🔁 반복 구조 요약

반복문	의미
i 반복	A의 행 (C의 행)
j 반복	B의 열 (C의 열)
k 반복	A의 행 x B의 열 성분 하나씩 곱하면서 누적합 계산

📌 예제 (2×2 행렬 곱셈)

⏱ 시간 복잡도

• 3중 반복문 → n × n × n = O(n³)
• 행렬 크기가 커질수록 계산량 급격히 증가

---

📘 요약

 

항목	내용
핵심 아이디어	A의 행과 B의 열을 곱해서 누적
인덱스 역할	i: 행 / j: 열 / k: 누적 인덱스
복잡도	O(n³)
주의할 점	C[i][j]는 꼭 0으로 초기화해야 함

---

pseudocode 사용 방식 보충 설명

• exchange x and y 같이 직관적으로 쓰는 표현 사용
• 반복문도 repeat n times 같이 심플한 표현 허용
• 배열 인덱스는 1부터 시작하며, 범위 명시 (ex: S[2..n])
• 배열은 자동 참조 전달(call by address)
  → 별도로 & 붙이지 않음
• const는 배열이 읽기 전용임을 표시

---

🧠 시험 대비 체크포인트

체크내용

 

체크	내용
✅	pseudocode는 C++보다 간단하고 수학적 표현 허용
✅	배열 인덱스는 기본적으로 1부터 사용
✅	각 알고리즘의 입력/출력/기본 동작 파악
✅	시간복잡도는 반드시 기억할 것 (특히 O(n), O(n²), O(n³) 구분)