2. Arrays & Structures (2) - 활용

배열과 구조체를 활용한 응용 예제 다뤄보기

---

1. Polynomial (다항식)  - 덧셈 연산

다항식(Polynomial)은 수학적으로 다음과 같이 표현할 수 있음:

 

3x³ + 2x² + x + 5

 

프로그래밍에서는 이를 계수(coefficient) 와 지수(exponent) 쌍으로 표현함

 

방법 1)  배열(Array) 활용

: 인덱스가 지수를 나타내고 값이 계수를 의미하게 할 수 있음.

 

 

지수(index)	0	1	2	3
계수(value)	5	1	2	3

int poly1[4] = {5, 1, 2, 3}; // 3x^3 + 2x^2 + x + 5

 

배열의 크기는 최대 차수 + 1 이 된다.

 

이때 다항식을 계산하는 방법은 단순하게 서로 같은 차수끼리 더하거나 빼고 인덱스별로 합산하면 됨.

void addPoly(int A[], int B[], int C[], int size) {
    for (int i = 0; i < size; i++) {
        C[i] = A[i] + B[i];
    }
}

int A[4] = {5, 1, 2, 3};  // 3x³ + 2x² + x + 5
int B[4] = {2, 0, 4, 1};  // x³ + 4x² + 2
int C[4];

addPoly(A, B, C, 4);

// C = {7, 1, 6, 4} → 4x³ + 6x² + x + 7

 

 

=> 하지만 이 방법은 x의 차수가 띄엄띄엄 있거나 차수가 커지면 배열의 공간이 낭비되어 비효율적이 됨.

예를들어, 3x^10 + x + 5 이러면 항은 3개인데 인덱스는 11개를 써야해서 8개나 공간이 낭비됨.

그래서 더 효율적으로 쓸 수 있는 방법이

 

방법 2)  구조체(struct) 활용

: 다항식을 구조체로 표현하여 계산

typedef struct {
    int coef; // 계수
    int exp;  // 지수
} Term;

예: 3x³ + 2x² + 1 → {(3,3), (2,2), (1,0)} 로 저장

 

이때 다항식을 계산하는 방법은 지수가 큰 항부터 비교하면서 같은 지수끼리 연산하면 됨.

Term A[] = {{3, 3}, {2, 2}, {1, 0}};
Term B[] = {{4, 2}, {2, 1}, {3, 0}};
Term C[10]; // 결과 저장용

int addPoly(Term A[], int a, Term B[], int b, Term C[]) {
    int i = 0, j = 0, k = 0;

    while (i < a && j < b) {
        if (A[i].exp == B[j].exp) {
            C[k].coef = A[i].coef + B[j].coef;
            C[k++].exp = A[i].exp;
            i++; j++;
        } else if (A[i].exp > B[j].exp) {
            C[k++] = A[i++];
        } else {
            C[k++] = B[j++];
        }
    }
    // 남은 항 복사
    while (i < a) C[k++] = A[i++];
    while (j < b) C[k++] = B[j++];
    return k; // 결과 항 개수
}

// 결과: A + B = 3x³ + 6x² + 2x + 4

 

 

C++로 다항식 덧셈 구현하기 :: 바바썬  ; 예전에 관련해서 공부해둔거 있어서 첨부함

---

2. Sparse Matrix (희소 행렬)

: 희소 행렬(Sparse Matrix)은 대부분의 원소가 0인 행렬을 의미한다.
모든 원소를 저장하면 메모리 낭비가 심하기 때문에, 0이 아닌 원소만 저장하는 방식으로 효율화한다.

 

예를 들어, 아래와 같은 배열을

0 0 5
0 8 0
0 0 3

→ (0,2,5), (1,1,8), (2,2,3) 형태로 저장하면 더 효율적이 됨.

= 수가 있는 곳만 저장하는 것!

 

조금 더 자세히 설명하면

숫자가 지금 9칸 중에 3개(5, 8, 3) 밖에 없으니까 숫자가 있는 부분만 저장한다

(5가 위치한 col, 5가 위치한 row, data 값) = > (0, 2, 5) 이런식으로

 

코드로 표현해보면 이렇게 된다

typedef struct {
    int row;
    int col;
    int value;
} Element;

typedef struct {
    int rows;
    int cols;
    int terms; // 0이 아닌 항의 개수
    Element data[100];
} SparseMatrix;

 

++++ 전치(Transpose)

희소 행렬의 전치(Transpose) 는 행과 열을 바꾸는 연산이다.
예를 들어, (row, col, value) → (col, row, value) 이렇게 

SparseMatrix transpose(SparseMatrix a) {
    SparseMatrix b;
    b.rows = a.cols;
    b.cols = a.rows;
    b.terms = a.terms;

    for (int i = 0; i < a.terms; i++) {
        b.data[i].row = a.data[i].col;
        b.data[i].col = a.data[i].row;
        b.data[i].value = a.data[i].value;
    }
    return b;
}

빠른 전치 (Fast Transpose)

• 각 열(column)별로 원소 개수를 미리 세어, 바로 해당 위치에 복사함
• 시간복잡도: O(terms + cols)

---

3. String (문자열) — Pattern Matching Algorithm

: 문자열에서 특정 패턴을 찾는 알고리즘

예를 들어 문자열 T = "ABABABABC" 에서 P = "ABABC" 를 찾는 문제.

 

방법 1)  Naive (Brute Force) 방식

: 가장 단순한 방법으로, 모든 위치에서 패턴을 하나씩 비교한다.

문자열	A	B	A	B	A	B	A	B	C
	A	B	A	B	C(불일치)
한칸이동		A (불일치)
한칸이동			A	B	A	B	C(불일치)
...
일치!					A	B	A	B	C

int bruteForce(char *text, char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text[i + j] == pattern[j]) j++;
        if (j == m) return i; // 패턴 발견
    }
    return -1; // 없음
}

• 시간복잡도: O(n × m)
• 구현이 단순하지만, 긴 문자열에서는 비효율적

방법 2)  KMP (Knuth–Morris–Pratt) 알고리즘

: Naive 방식은 불일치 시 처음부터 다시 비교하지만 KMP는 이전의 비교 정보를 활용해 불필요한 비교를 건너뛴다.

 

** LPS[i] = P[0..i]까지의 부분 문자열 중, 접두사 == 접미사가 되는 가장 긴 길이

인덱스	문자	부분문자열	LPS**
0	A	A	0
1	B	AB	0
2	A	ABA	1 (A)
3	B	ABAB	2 (AB)
4	A	ABABA	3 (ABA)

즉, LPS = [0, 0, 1, 2, 3]

이제 마지막 값이 3이니까 패턴을 3칸 이동시켜서 이어서 비교함

 

!! 부분 일치 테이블 (LPS: Longest Prefix Suffix)

• 현재까지의 패턴 중 접두사 == 접미사 길이를 미리 계산
• 불일치가 발생하면 해당 길이만큼 점프

void computeLPS(char *pat, int M, int *lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len - 1];
        } else {
            lps[i++] = 0;
        }
    }
}

int KMP(char *text, char *pat) {
    int N = strlen(text), M = strlen(pat);
    int lps[M];
    computeLPS(pat, M, lps);

    int i = 0, j = 0;
    while (i < N) {
        if (pat[j] == text[i]) { i++; j++; }
        if (j == M) return i - j; // 패턴 발견
        else if (i < N && pat[j] != text[i]) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
    return -1;
}

• 시간복잡도: O(n + m)
• 효율적이며 실제 문자열 검색에서 자주 사용됨