[105] 자료구조 06차시 구조체와 재귀호출

1. 구조체 개념

가. 구조체 개념

구조체도 배열처럼 여러 개의 데이터를 그룹으로 묶어서 하나의 자료형으로 정의하고 사용하는 자료형

배열은 같은 자료형 만을 그룹으로 묶을 수 있지만, 구조체는 서로 다른 자료형을 그룹으로 묶을 수 있으므로 복잡한 자료 형태를 정의하는데 유용하게 사용됨.

자료를 체계적으로 관리하려면 일정한 단위 형식으로 구성해야 하는데, 이러한 단위 형식을 레코드라고 함.

레코드를 구성하는 하위 항목을 필드라고 함.

레코드가 여러 개 모이면 파일이 됨.

여러 형태의 필드를 묶어 하나의 구성단위 역할을 하는 레코드는 구조체를 사용하여 정의할 수 있음.

즉, 여러 자료형의 필드를 가지고 있는 레코드를 만들 때 구조체를 사용함.

나. 구조체 선언

구조체는 여러 자료형의 변수들을 그룹으로 묶어서 하나의 자료형으로 선언하여 사용함.

1) 구성 요소

구조체 이름: 구조체로 정의하는 새로운 자료형의 이름

항목: 구조체를 구성하는 내부 변수들의 이름

구조체의 항목은 배열의 각 배열요소에 해당

배열요소는 모두 같은 자료형으로 되어있으므로 배열요소에 대한 선언 없이 사용이 가능하지만, 구조체에서는 각 항목이 다른 자료형을 가질 수 있기 때문에 항목별로 자료형과 항목이름(변수이름)을 선언해야 함.

다. 구조체형의 선언과 사용 형식

1) 선언 형식

struct 구조체형이름 {
    자료형 항목1;
    자료형 항목2;
    ...
    자료형 항목n;
}

2) 사용 형식

struct 구조체이름 구조체변수이름;

3) 구조체 사용 단계

구조체형 선언: 내부 구조를 정의

구조체 변수 선언: 구조체형에 따른 변수를 선언

구조체 변수의 사용: 내부 항목에 데이터를 저장하고 사용

4) 구조체 사용 예

struct employee {
    char name[10];
    int year;
    int pay;
} // 구조체형 선언

struct employee Lee, Kim, Park; // 구조체 변수 선언

라. 구조체 변수의 선언 방법

1) 구조체형을 선언한 후에 구조체 변수 선언

struct employee {
    char name[10];
    int year;
    int pay;
}

struct employee Lee;

2) 구조체형과 구조체 변수를 연결하여 선언

struct employee {
    char name[10];
    int year;
    int pay;
} Lee;

3) 구조체형 이름을 생략하고 구조체 변수 이름만 선언

struct {
    char name[10];
    int year;
    int pay;
} Lee;

마. 구조체의 변수의 초기화

일반 변수 초기화와 마찬가지로 구조체 변수 초기화를 하려면 구조체 변수를 선언하면서 변수의 초기값을 지정함.

일반 변수는 값을 하나만 가지므로 초기값도 하나지만, 구조체는 내부 항목이 여러 개일 수 있으므로 내부 항목의 자료형과 개수를 순서에 맞추어 초기값 리스트로 지정하고 중괄호({})를 사용함.

중괄호({})에 담긴 각 값은 순서대로 구조체 변수의 내부 데이터 항목에 대입됨.

struct employee {
    char name[10];
    int year;
    int pay;
} // 구조체형 선언
struct employee Lee = { "Ann", 2015, 4200 }; // 구조체 변수의 초기화

2. 구조체 연산

가. 구조체 변수의 데이터 항목 참조하는 방법

구조체 연산자를 사용하여 구조체 변수에 있는 각 데이터 항목을 참조함.

나. 구조체 연산자

1) 점 연산자: .

구조체 변수에 있는 데이터 항목을 개별적으로 지정할 때 사용함.

struct employee {
    char name[10];
    int year;
    int pay;
} // 구조체형 선언

struct employee Lee; // 구조체 변수 선언

Lee.name = "Ann";
Lee.year = 2015;
Lee.pay = 4200;

2) 화살표 연산자: ->

구조체 포인터 변수에서 포인터가 가리키는 구조체 변수의 데이터항목을 지정하기 위해서 화살표 연산자를 사용함.

struct employee {
    char name[10];
    int year;
    int pay;
} // 구조체형 선언

struct employee Kim; // 구조체 변수 선언
struct employee *Sptr = &Kim;

Sptr->name = "susan";
Sptr->year = 2014;
Sptr->pay = 4300;

다. 구조체 포인터를 이용한 구조체 변수의 데이터 항목 지정 방법

// (1)
Sptr->name = "susan";
Sptr->year = 2014;
Sptr->pay = 4300;

// (2)
(*Sptr).name = "susan";
(*Sptr).year = 2014;
(*Sptr).pay = 4300;

 

(1)과 같은 화살표연산자를 (2)와 같이 포인터 참조 연산자(*)를 사용하여 표현할 수도 있음.

점 연산자(.)가 참조연산자(*)보다 연산 우선순위가 높으므로 (2)와 같이 참조연산자(*)를 먼저 처리할 수 있도록 괄호를 사용해야 함.

라. 구조체 연산 활용

구조체에서는 데이터 항목 참조 연산, 구조체 변수복사, 구조체 변수의 주소 구하기 연산 등을 사용할 수 있음.

1) 데이터 항목 참조 연산

점연산자와 화살표연산자를 이용하여 구조체 데이터 항목을 개별적으로 참조함.

struct employee Lee;
struct employee *Sptr;
Sptr = &Lee;
Lee.year = 2015;
Sptr->pay = 3000;
Sptr->name = "Ann";

2) 구조체 변수 복사 연산

같은 구조체에 있는 구조체 변수들끼리 내용을 한 번에 복사하는 연산

struct employee Lee, Kim, team[5];
Lee = Kim;
Lee = team[2];
team[2] = team[3];

3) 구조체 변수의 주소 구하기 연산

포인터의 주소연산자를 사용하여 구조체 변수의 주소를 구하거나, 구조체 변수가 배열인 경우에는 배열의 특성에 따라 구조체 배열 변수의 이름에서 주소를 구할 수 있음.

struct employee Lee, team[5];
struct employee *Sptr1, *Sptr2;
Sptr1 = &Lee;
Sptr2 = team;

3. 재귀호출

가. 재귀호출(순환호출)

함수가 자기 자신을 호출하여 순환 수행되는 것으로 순환호출 또는 recursion 이라고 함.

함수 실행 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성 가능함.

내가 나를 호출하는 것이므로 내 현재 작업을 처리하기 위해 같은 유형의 하위 작업이 필요함.

전체 문제를 한 번에 해결하기보다 같은 유형의 하위 작업으로 분할하여 작은 문제부터 해결하는 방법이 효율적인 경우에 사용함.

1) 베이스케이스(Base case)

한 번에 해결할 수 없는 현재 작업을 한 단계 작게 분할한 하위작업에 대해 재귀 호출하는 과정을 반복하다 보면, 한 번에 해결할 수 있을 정도로 분할되어 작업 단위가 충분히 작아지는 단계를 만나게 되는데 이 단계를 베이스케이스라고 함.

베이스케이스에서 구한 답을 재귀 호출자에 반환하는 과정이 재귀호출의 역순으로 반복되어 결국 처음의 문제에 대한 답을 구하게 되는 것이 재귀호출을 이용한 문제 해결의 원리

나. 팩토리얼 함수

대표적인 재귀호출 함수

n에 대한 팩토리얼 함수는 1부터 n까지 모든 자연수를 곱하는 연산

\(n! = n \times (n-1)!\) 이므로 하위 값에 대한 팩토리얼을 구하는 작업을 1!(베이스케이스)까지 반복해야함.

1! 값을 알게 되면 그 값을 이용하여 바로 상위 값을 구하고, 구한 값을 이용하여 다시 그 상위 값을 구하기를 반복하여 결과적으로 n! 값을 구함.

1) 재귀호출을 이용한 팩토리얼 함수

int fact(int n) {
    if (n <= 1) 
        return (1);
    else
        return (n * fact(n - 1));
}

2) 반복문을 이용한 팩토리얼 함수

int fact(int n) {
    int i, f = 1;
    if (n <= 1) 
        return (1);
    else {
        for (i = n; i >= 0; i++)
            f = f * i;
        return f;
    }
}

다. 하노이 탑

팩토리얼 함수는 단순한 반복 구조라 재귀 호출 방식을 사용하지 않고 반복문으로 구현할 수 있음.

하지만 복잡한 재귀 구조 문제는 재귀호출을 해야 해결할 수 있음.

대표적인 예가 하노이 탑 퍼즐

https://ko.wikipedia.org/wiki/하노이의_탑

하노이의 탑 - 위키백과, 우리 모두의 백과사전