SW 문제해결 기본 - Array 2

 

1. 2차원 Array

① 2차원 Array의 선언

• 2차원 이상의 다차원 Array는 차원에 따라 인덱스를 선언한다.
• 2차원 Array의 선언은 세로 길이(행의 개수), 가로 길이(열의 개수)를 필요로 한다.

② 2차원 Array의 순회

• 순회란 Array의 모든 원소를 모두 조회하는 것을 말한다.
• 행 우선 순회, 열 우선 순회, 지그재그 순회가 있다.

지그재그 순회

첫 행은 우측으로, 다음 행은 좌측으로 진행하여 Array의 원소를 조사하는 방법

 

int i;	// 행의 좌표
int j;	// 열의 좌표

for i from 0 to n-1
	for j from 0 to m-1
    	Array[i][j + (m-1-2*j) * (i%2)];

③ 델타를 이용한 2차 Array 탐색

• 델타의 개념을 이용하여 2차 Array의 한 좌표에서 4방향으로 검색한다.

④ 전치 행렬

• 행과 열의 위치가 반대인 행렬을 전치 행렬이라고 한다.

int ary[3][3]	// 3*3 행렬
int i;	// 행의 좌표
int j;	// 열의 좌표

for i from 0 to 2
	for j from 0 to 2
    	if (i < j)
        	swap(ary[i][j], ary[j][i]);

i < j 조건을 쓰는 이유: 모든 좌표에 대하여 행과 열의 값을 바꾸게 되면 본래의 모습으로 되돌아 온다.

---

2. 부분 집합

① 부분 집합 문제

• 완전 검색 방법을 적용하여 부분 집합을 구한다.
• 집합의 원소가 n개 일 때 모든 부분 집합의 개수는 2^n개이다.

② 부분 집합 문제 알고리즘 1

• 반복문을 이용하여 집합의 모든 부분 집합을 구할 수 있다.
• 집합의 원소의 유무를 Array로 표현하여 부분 집합을 출력한다.

{1, 2, 3, 4}로 이루어진 집합의 경우

* bit는 해당 원소를 보여줄지 보여주지 않을지 결정

for i from 0 to 1 {
    bit[0] <- (i%2==0)? 0:1;		// 0번째 원소
    for j from 0 to 1 {
        bit[1] <- (j%2==0)? 0:1;		// 1번째 원소
        for k from 0 to 1 {
            bit[2] <- (k%2==0)? 0:1;	// 2번째 원소
            for l from 0 to 1 {
            	bit[3] <- (l%2==0)? 0:1;	// 3번째 원소
            }
        }
    }
}

③ 부분 집합 문제 알고리즘 2

• Bit 연산을 이용하여 보다 효율적으로 부분 집합을 구할 수 있다.

#include <stdio.h>

void main(void) {
    int i, j;
    int arr[] = {3, 6, 7, 1, 5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);	// n: 원소의 개수
    
    for (int i=0; i<(1<<(n)); i++) {	// 1<<n: 부분 집합의 개수
        for (int j=0; j<n; j++) {	// 원소의 수만큼 Bit를 비교함
            if (i&(1<<j)) {	// i의 j번째 Bit가 1이면 j번째 원소 출력
                printf("%d, ", arr[j]);
            }
        }
        print("\n");
    }
}
    

---

3. 검색

① 검색의 개요

• 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업이다.
• 순차 검색, 이진 검색, 인덱싱 등이 있다.

② 순차 검색

• 가장 간단하고 직관적인 검색 방법이다.
• Array나 연결 리스트 등 순차 구조로 구현된 자료 구조에서 원하는 항목을 찾을 때 유용하다.
• 자료가 정렬되어 있는 경우와 비 정렬되어 있는 경우로 나눌 수 있다.
• 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행 시간이 급격히 증가하여 비효율적이다.

정렬되지 않은 자료의 검색 과정

1. 첫번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지를 비교하여 찾음
2. 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환
3. 자료구조의 마지막에 갈 때까지 검색 대상을 찾지 못하면 검색 실패

• 평균 비교 횟수: (1+2+3+...+n)/n = (n+1)/2
• 시간 복잡도: O(n)

sequentialSearch(a[], n, key)
    i <- 0;
    while(i<n and a[i]!=key) do {
        i <- i+1;
    }
    if(i<n) then return i;
    else return -1;
end sequentialSearch();

정렬된 자료의 검색 과정

1. 자료가 오름차순으로 정렬된 상태에서 검색을 실시한다고 가정
2. 자료를 순차적으로 검색하면서 키 값을 비교함
3. 원소의 키 값이 검색 대상의 키 값보다 크면 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료함

• 정렬되어 있으므로, 검색 실패를 반환하는 경우 평균 비교 횟수가 반으로 줄어듬
• 시간 복잡도: O(n)

sequentialSearch2(a[], n, key)
    i <- 0;
    while(a[i]<key) do {
        i <- i+1;
    }
    if(a[i]=key) then return i;
    else return -1;
end sequentialSearch2();

③ 이진 검색

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법이다.
• 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행한다.
• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.
• 이진 검색의 경우, 자료에서 삽입이나 삭제가 발생했을 때 Array의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다.

이진 검색의 검색 과정

1. 자료의 중앙에 있는 원소를 선택
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교
3. 목표값 < 중앙 원소 값: 자료의 왼쪽 반, 목표값 > 중앙 원소값: 자료의 오른쪽 반에 대해서 새로 검색을 수행
4. 찾고자 하는 값을 찾을 때까지 과정을 반복

• 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행함
• 자료에 삽입이나 삭제가 발생했을 때 Array의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요함

binarySearch(a[], key)
    start <- 0, end <- length(a)-1;
    while(start <= end) {
        middle = start + (end-start)/2;
        if(a[middle] == key) {
            return true;
        }
        else if(a[middle] > key) {
            end = middle-1;
        }
        else start = middle+1;
    }
    return false;
end binarySearch();

 

재귀 함수 이용

binarySearch(a[], low, high, key)
    middle <- (low+high)/2;
    if(key = a[middle]) then
        return true;
    else if(key < a[middle]) then
        binarySearch(a[], low, middle-1, key);
    else if(key > a[middle]) then
        binarySearch(a[], middle+1, high, key);
    else
        return false;	// 검색 실패
end binarySearch();

 

④ 인덱스

• 인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블을 저장하는데 필요한 디스크 공간보다 작다.
• 보통 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들을 갖고 있지 않기 때문이다.
• 원본 데이터 Array와 별개로 Array 인덱스를 추가하면 원본 데이터에 데이터가 삽입될 경우 상대적으로 크기가 작은 인덱스 Array를 정렬하기 때문에 속도가 빠르다.

---

4. 정렬

① 셀렉션 알고리즘

• 저장되어 있는 자료로부터 k번째로부터 큰 혹은 작은 원소를 찾는 방법이다.
• 최소값, 최대값 혹은 중간값을 찾는 알고리즘을 의미하기도 한다.

k번째로 작은 원소를 찾는 알고리즘

- 1번부터 k번째까지 작은 원소들을 찾아 Array의 앞쪽으로 이동시키고, Array의 k번째를 반환

- k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 함

Select(list[], k)
    for i from 1 to k
        minIndex = i;
        minValue = list[i];
        for j from i+1 to n
            if(list[j] < minValue)
                minIndex = j;
                minValue = list[j]
        swap(list[i], list[minIndex]);
    return list[k]
end Select();

선택 과정

- 정렬 알고리즘을 이용하여 자료를 정렬한다.

- 원하는 순서에 있는 원소를 가져온다.

 

② 선택 정렬

• 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식이다.
• 앞서 살펴본 셀렉션 알고리즘을 전체 자료에 적용한 것이다.

선택 정렬 과정

- 주어진 리스트 중에서 최소값을 찾는다.

- 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.

- 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.

• 시간 복잡도: O(n^2)

SelectionSort(a[], size) {
    i, j, t, min, temp;
    for i from 0 to size-2 {
        min <- i;
        for j from i+1 to size-1 {
            if(a[j]<a[min]) min <- j;
        }
        temp <- a[i];
        a[i] <- a[min];
        a[min] <- temp;
    }
}