자료구조(Data Structure)- 점검편 1

1. (Complexity) Big-O, Big-Ω, Big-Θ 의 정의

 Big O는 최대 이정도다라는 상한선을 의미, Big-Ω는 최소한의 하한선을 의미, Big-Θ 상한선과 하한선 둘 다 만족하는 것을 의

 

 

2. (Complexity) 다음 알고리즘의 worst-case time complexity T(N)을 N의 함수로 나타내고, Big-O로 표현하시오. 1) 번은 sum + list[j] 덧셈 연산의 총 수를, 2) 번은 key 와 list element 의 비교 횟수를 기준으로 한다.

(1)

int sum = 0; 
		for (i = 0; i < N; i++) { 
    			for (j = N - 1; j >= i; j--) { 
    				sum = sum + list[j]; 
    			} 
		}

T(N) 도출: 바깥 루프 I가 0부터 N-1까지 돌 때, 안쪽 루프 j는 N번, N-1번,..1번 실행된다. T(N)=N+(N-1)+..+1=N(N+1)/2 이고 Big-O로 표현하면 최고차항만 남긴 O(N^2)

 

 

(2)

list[] is an array of numbers  
		Search(list[0..N-1], key)
			l ← 0, r  ← N-1
			while (l ≤ r) do 
    				m ← (l + r) / 2
				if (key = list[m]) return m
				else 
					if (key < list[m]) r ← m-1
					else                     l ← m+1
    			return -1

T(N) 도출: 반복할 때마다 탐색 범위가 N->N/2->N/4...1)으로 줄어들어 최약의 경우 범위가 1이 될 때까지 나누므로 N/2^k = 1, 즉 k=log_2_N번 반복한다. 마지막 비교까지 포함하면

T(N)=|log_2_N|+１ 이고 Big-O로 표현하면 O(log_2_N)이다.

 

 

3. (Multidimensional Array) R x R pixel 크기의 greyscale 이미지들을 저장하는 array를 다음과 같이 정의한다고 하자. 각 pixel 값의 크기는 [0, 255]이다.

int images[100][R][R];

 

1) 배열의 시작 주소가 1000 이라면 images[2][10][20]의 주소는 무엇인가?

 

정답: 1000 + 4 * (2*R*R + 10*R + 20)     (int는 4byte)

 

2) 위와 같이 저장되어 있는 이미지들 중 주어진 이미지(key_image)와 가장 유사한 이미지를 찾는 알고리즘을 pseudocode로 나타내보시오. 두 이미지의 차이(= 각 pixel 값의 차이의 제곱의 합)가 작을수록 유사도는 높다고 정의한다.

 

FindSimilarImage(images[N][R][R], key_image[R][R])

 

FindSimilarImage(images[N][R][R]. key_image[R][R])
	min_diff = 무한대
	best_idx = -1

	for i=0 to N-1 do
		diff=0
		for r=0 to R–1 do
			for c=0 to R-1 do
				diff=diff+(images[i][r][c]-key_image[r][c])^2
		if diff < min_diff then
			min_diff = diff
			best_idx = i
	return best_idx

 

 

 

4. (Programming) ADT

 

어떤 application에서는 평면상의 여러 가지 도형을 다룬다. 아래와 같은 프로그램이 가능하도록 점(point), 선분(line), 사각형(rect)을 struct를 이용하여 새로운 데이터 타입으로 정의하고, 각각의 생성(make_point, make_line, make_rect), 선분의 길이 계산(line_length), 사각형의 면적 계산(rect_area)을 수행하는 함수들을 작성하시오.

 

Point p1, p2, p3;

Line s;

Rect r;

double length, area;

 

p1 = make_point(1, 1);

p2 = make_point(3, 3);

s = make_line(p1, p2); // p1, p2를 연결하는 선분

r = make_rect(p1, p2); // 왼쪽 아래 점이 p1, 오른쪽 위 점이 p2인 사각형

 

length = line_length(s); // 2.828

area = rect_area(r); // 4

 

#include <math.h>
typedef struct {double x, y; }Point;
typedef struct {Point p1, p2; } Line;
typedef struct {Point p1, p2; } Rect;

Point make_point(double x, double y){
	Point p = {x, y};
	return p;
}
Line make_line(Point p1, Point p2){
	Line l = {p1, p2};
	return l;
}
Rect make_rect(Point p1, Point p2){
	Rect r = {p1, p2};
	return r;
}

double line_length(Line s){
	return sqrt(pow(s.p2.x-s.p1.x, 2)+pow(s.p2.y-s.p2.y, 2));
}

double rect_area(Rect r){
	return fabs((r.p2.x-r.p1.x)*(r.p2.y-r.p1.y));
}

 

 

 

5. (Programming) Stack application

 

거꾸로 읽어도 같은 문자열이 되는 것을 Palindrome 이라고 한다. 예들 들어 “eye”, “radar”와 같은 단어, “Madam, I'm Adam”과 같은 문장이 이에 해당한다. 대소문자는 구분하지 않으며, 문장부호, 공백은 무시한다. Array를 이용하여 stack 자료구조를 정의하고, 아래와 같은 형태의 push, pop 등 함수를 구현한 후, 어떤 문자열이 Palindrome 인지를 확인하는 함수 is_palindrome(char *s)를 stack을 이용하여 작성하시오.

 

void init_stack(Stack* s);

is_empty(Stack* s);

is_full(Stack* s);

void push(Stack* s, char c);

char pop(Stack* s);

int is_palindrome(char* s);

 

문자열을 입력받아 palindrome인지 확인하는 프로그램을 작성하고 다음 문자열들로 테스트하시오.

 

“Kayak” - yes

“Eye for eye” - no

“Mr. Owl ate my metal worm” - yes

 

정답:

#include <stdio.h>
#include <ctype.h>
#define MAX 100

typedef struct {
	char data[MAX];
	int top;
} Stack;

void init_stack(Stack* s) { s->top = -1; }
int is_empty(Stack* s) { s->top == -1; } //비었으면 1 아니면 0 반환
int is_full(Stack* s) { s->top == MAX - 1; } //꽉 찼으면 1 아니면 0 반환
void push(Stack* s, char c) { s->data[++(s->top)] = c; }
char pop(Stack* s) { return (!is_empty(s)) ? s->data[(s->top)--] : '\0\''; }

int is_palindrome(char* s) {
	Stack stack;
	init_stack(&stack);
	char filtered[MAX];
	int len = 0;

	//알파벳만 가져와 소문자로 변환해서 배열과 스택에 저장
	for (int i = 0; s[i] != '\0'; i++) {
		if (isalpha(s[i])) {
			char lower_c = tolower(s[i]);
			filtered[len++] = lower_c; //filtered[len]에 저장, len은+1
			push(&stack, lower_c);
		}

		//스택에서 순서대로 빼기=문자열 중 알파벳만 거꾸로 확인하기
		//filtered과 비교, filtered는 문자열 중 알파벳만 추출해서 저장했음
		for (int i = 0; i < len; i++) {
			if (pop(&stack) != filtered[i]) {
				return 0; //회문 아님
			}
		}
		return 1; //회문 맞음
	}
}

int main() {
		char s1[] = "Kayak";
		char s2[] = "Eye for eye";
		char s3[] = "Mr.Owl ate my metal worm";

		printf("\"%s\" - %s\n", s1, is_palindrome(s1) ? "yes" : "no");
		printf("\"%s\" - %s\n", s2, is_palindrome(s2) ? "yes" : "no");
		printf("\"%s\" - %s\n", s3, is_palindrome(s3) ? "yes" : "no");

		return 0;

 

 

결과창