자료구조 실습 4주차

4주차 자료구조실습

알고리즘 =/= 프로그램
알고리즘과 프로그램의 차이점 : 유한성과 무한성
알고리즘 - 문제해결(유한성)
프로그램 - 명령어(유한성,무한성)

자료구조의 정의
1. 문제분석
2. 문제식 도출
3. 절차정의(순서도)
4. 로직분석(검증)
이후 코딩 및 실행, 수정

자료구조시간에는 절차정의,로직분석까지만 한다.

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

포인터
주소값을 저장하는 특별한 변수

연결연산자와 값연산자
int *ptr = &i;
"&" = 주소
"*" = 값

이중포인터는 add 100 -> 105(10)처럼 2번 이상 이동해야하는 경우를 이중포인터라고 부름.

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

개인 = 레코드 = 논리레코드
개인들을 묶은것을 물리레코드(Block)

구조체 선언
여러 자료형의 변수들을 그룹으로 묶어서 하나의 자료형으로 선언
구조체이름,자료형,데이터 항목으로 구성됨

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

구조체 사용 단계
1. 구조체형 선언 : 내부 구조를 정의한다.
2. 구조체 변수 선언 : 구조체형에 따른 변수를 선언한다.
3. 구조체 변수의 사용 : 내부 항목에 데이터를 저장하고 사용한다.

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

재귀호출(순환호출)
자기 자신을 호출하여 순환 수행되는 것
함수 실행 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성가능
내가 나를 호출하는 것이므로 내 현재 작업을 처리하기 위해 같은 유형의 하위 작업이 필요
하위 작업 : 현재 수행 중인 작업의 하위 단계, 즉 좀 더 작은 단위 작업
전제 문제를 한 번에 해결하기보다 같은 유형의 하위 작업으로 분할하여 작은 문제부터 해결하는 방법이 효율적인 경우 사용
베이스 케이스base case
재귀호출하는 과정 반복하다 보면, 한 번에 해결할 수 있을 정도로 분할된 작업 단위가 최대로 작아지는 단계

팩토리얼 함수
n에 대한 팩토리얼 함수는 1부터 n까지 모든 자연수를 곱하는 연산
5! = 5*4*3*2*1 = 120

문제 3. 1!+3!+5!+...+19!의 합을 구하세요.
1. 어떻게 카운터 하는가?  1  3   5   ……. 19까지  
2. 카운터 증가 치(값)? 매번 카운터 시 2씩 증가 함 팩토리얼 증가치 2씩 증가 (분석 : 5! = 3!*4*5, 7!=5!*6*7)
3. 카운터 시작 숫자?(0부터, 1부터, -1부터)
4. 카운터 변수는 무엇으로 ? (C =Counter, i=integer … )
5. 합계 변수는 무엇으로 ? (S =Sum,  HAP,  … )

1. 문제분석
- 증가치 +2
- F => 3! = 3 * 2 * 1!
         5! = 5 * 4 * 3!
         7! = 7 * 6 * 5!
F=F+2 | K=K*(F-1)*F         | S=S+K                | N
3=1+2 | 6=1*(3-1)*3           | 7=1+6                 | N=3
5=3+2 | 120=6*(5-1)*5       | 127=7+120         | N=5
7=5+2 | 5040=120*(7-1)*7 | 5167=127+5040 | N=7
....

프로세스 실행 도중 예기치 않은 상황이 발생할 때 발생한 상황을 처리한 후 실행 중인 작업으로 복귀하는 것을 인터럽트라고 말한다.

순차 -> 배열(다항식)
연결 -> 포인터

순차 자료구조의 개념
구현할 자료들을 논리적 순서로 메모리에 연속 저장하는 구현 방식
논리적인 순서와 물리적인 순서가 항상 일치해야 함
C 프로그래밍에서 순차 자료구조의 구현 방식 제공하는 프로그램 기법은 배열

순차자료구조
프로그램 기법 : 배열을 이용한 구현
메모리 저장방식 : 순서대로 연속적으로 저장
연산 특징 : 삽입 및 삭제 연산을 해도 순서대로 연속적으로 저장되고, 변경된 논리적인 순서와 저장된 물리적인 순서가 일치함.

연결자료구조
프로그램 기법 : 포인터를 이용한 구현
메모리 저장방식 : 순서 상관없이 링크에 의해 논리적인 순서로 저장
연산 특징 : 삽입 및 삭제 연산을 하여 논리적인 순서가 변경되어도 링크 정보만 변경되고 물리적인 순서는 변경되지 않음.

순서가 있다 -> 연산자가 있다.
+AB  ->Preorder  (전위)
A+B  ->Imorder   (중위)
AB+  ->Postorder(후위)

A=1, ++A = 전위연산자
A=0, A++ = 후위연산자