자료구조와 알고리즘

1.1 자료구조와 알고리즘

자료구조란?

프로그램에서 자료들을 정리하여 보관하는 여러가지 구조를 자료구조라한다.

컴퓨터 프로그램은 무엇으로 이루어져있을까?

프로그램=자료구조+알고리즘
대부분의 프로그램에서 자료를 처리하고 있고 이들 자료는 자료구조를 사용하여 저장된다.
또한 주어진 문제를 처리하는 절차가 필요하다.이것은 알고리즘이라고 불린다.

자료구조와 알고리즘은 밀접한 관계가 있어서 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정된다.
컴퓨터가 복잡한 자료들을 빠르게 저장,검색,분석,전송,갱신하기 위해서는 자료구조가 효율적으로 조직화되어 있어야 한다.
각 응용에 가장 적합한 자료구조와 알고리즘을 선택해야한다.

알고리즘이란?

컴퓨터로 문제를 풀기 위한 단계적인 절차
문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 밤법을 장치가 이해할수있는 언어로 기술한 것
특정한 일을 수행하는 명령어(컴퓨터에서 수행되는 문장)들의 집합

알고리즘이 되기 위한 조건

입력:0개이상의 입력이 존재하여야 한다.
출력:1개 이상의 출력이 존재하여야 한다.
명백성:각 명령어의 의미는 모호하지않고 명확해야 한다.
유한성:한정됨 수의 단계 후에는 반드시 종료되어야 한다.
유효성:각 명령어들은 종이와 연필,또는 컴퓨터로 실행 가능한 연산이어야 한다.

알고리즘을 기술하는 4가지 방법

한글이나 영어같은 자연어
흐름도(folwchart)
의사코드(pseudo-code):자연어보다 더 체계적이고 프로그래밍 언어보다는 덜 엄격한 언어로서 알고리즘을 기술하는 데만 사용되는 코드를 말한다.다만 대입연산자가 =가 아닌 <-임을 유의하라.
프로그래밍 언어:예약어들은 모두 명백한 의미를 가지고 있음.

quiz(p.17)

문제를 풀기위한 단계적인 절차는 [알고리즘]이다.
알고리즘을 기술하기 위한 방법에는 자연어,흐름도,[의사코드],프로그래밍 언어가 있다.
알고리즘이 되기 위한 조건이 아닌것은?[4]
1. 출력
2. 명백성
3. 유효성
4. 반복성

1-2 추상 자료형

C언어에서 제공하는 자료형

정수
실수
문자
배열(동일한 자료형이 여러개 모인 것)
구조체(다른 자료형이 여러개 모인 것)

자료형이라하면 데이터뿐만아니라 데이터간에 가능한 연산도 고려하여야한다

추상화란?

어떤 시스템의 간략화된 기술 또는 명세
시스템의 정말 핵심적인 구조나 동작에만 집중하는 것
좋은 추상화는 사용자에게 중요한 정보는 강조되고 반면 중요하지않은 구현 세부사항은 제거되는 것
이를 위해 정보은닉 기법이 개발->추상자료형(ADT)의 개념으로 발

ADT(추상자료형,캡슐화,정보은닉)

실제적인 구형으로부터 분리되어 정의된 자료형을 뜻함
자료형을 추상적으로 정의함을 의미
데이터나 연산이 무엇인지는 정의되지만 데이터나 연산을 어떻게 컴퓨터상에서 구현할 것인지는 정의되지 않음
연산을 정의할 떄 연산의 이름,매개 변수,반환형은 정의하지만 연산을 구현하는 구체적인 코드는 주어지지않는것
다만 연산을 정의하는 추상적인 의사 코드는 주어질 수 있음
ADT안에는 객체와 함수들이 정의된다.
객체는 주로 집합의 개념을 사용하여 정의되고, 이후 함수(연산)들이 정의된다.
구현 세부사항은 외부에 알리지않고 외부와의 인터페이스만을 공개하게된다.
사용자는 구현세부사항이 아닌 인터페이스만 사용하기 떄문에 추상 자료형의 구현방법은 언제든지 안전하게 변경될 수 있다.
인터페이스만 정확하게 지켜진다면 ADT가 여러가지 방법으로 구현될 수 있음을 뜻한다.
전체 프로그램을 변경가능성이 있는 구현의 세부사항으로부터 보호하는 것이다.
구현으로부터 명세의 분리가 ADT의 핵심 아이디어이다.
adt의 객체는 클래스의 속성으로 구현되고 adt의 연산은 클래스의 멤버함수로 구현된다.
객체 지향언어에서는 private나 protected키워드를 이용하여 내부 자료의 접근을 제한할 수 있다.
클래스는 계층구조(상속개념사용)로 구성될 수 있다.

quiz(p.21)

01.자료형은 객체와 이객체간의 연산의 집합으로 정의된다.
02.추상자료형은 객체와 연산들의 명세가 구현으로부터 분리된 자료형을 말한다.
Nat_No추상자료형에 is_greater(x,y)연산을 추가하여보자.

is_greater(x,y) ::= if(x>y) return TRUE;
                   else return FALSE;
특수 기호인'::='는 '정의된다'를 의미한다.
구문 구조 이름인 좌측이 '::='기호 다음에 따르는 우측으로 대체될 수 있다는 의미이다.

1.3 알고리즘 성능 분석

최근 상용 프로그램의 규모가 이전에 비해서 엄청나게 커지고 있어 처리해야할 자료의 양이 많기 떄문에 알고리즘의 효율성은 더욱 중요하게 된다.
사용자들은 빠른 프로그램을 선호하기 때문에 프로그래머는 하드웨어와 상관없이 소프트웨어적으로 최선의 효율성을 갖는 프로그램을 제작하도록 노력하여야 할 것 이다.
효율적인 알고리즘이란 알고리즘을 시작하여 결과가 나올 때까지의 수행시간이 짧으면서 컴퓨터 내에 있는 메모리와 같은 자원을 덜 사용하는 알고리즘이다.

알고리즘 복잡도 분석 방법

알고리즘 복잡도 분석은 구현하지 않고도 모든 입력을 고려하는 방법이고 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.

시간 복잡도 함수

알고리즘의 수행시간 분석을 시간 복잡도(time complexity)라고 하고 알고리즘이 사용하는 기억 공간 분석을 공간 복잡도(space complexity)라고 한다.
알고리즘의 복잡도를 이야기할때 대게는 시간 복잡도를 말한다.
알고리즘이 차지하는 공간보다는 수행시간에 더 관심이 있기 때문이다.
일반적으로 연산의 수행횟수는 고정된 숫자가 아니라 n에 대한 함수가 된다.
연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수라고 하고 T(n)이라고 표기한다.

빅오 표기법

입력 자료의 개수가 큰경우에는 차수가 가장 큰 항이 전체의 값을 주도하기때문에 시간 복잡도 함수에서 차수가 가장 큰 항만을 고려하면 충분하다.
시간 복잡도 함수에서 중요한것은 n이 증가하였을 때에, 연산의 총 횟수가 n에 비레하여 증가하는지,아니면 n²에 비례하여 증가하는지,아니면 다른 증가추세를 가지는지가 더 중요하다.
시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 한다.
알고리즘이 n에 비례하는 수행시간을 가진다고 말하는 대신에 시간복잡도가O(n)이라고 한다.('빅오 of n'이라고 읽음)
빅오 표기법을 사용하면 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략함으로쎠 시간 복잡도를 간단하게 표시할 수 있다.

두개의 함수 f(n)과 g(n)이 주어졌을때, 
n>n₀에 대하여 |f(n)|<=c|g(n)|을 만족하는 2개의 상수 c와 n₀가 존재하면 
f(n)=O(g(n))이다.
위의 그래프에서 f(n)의 값은 n이 매우 커지게 되면 결국 g(n)보다 작거나 같게 된다.
따라서 이 정의는 g(n)이 f(n)의 상한값이라는것을 의미한다.

빅오표기법 이외의 표기법

빅오 표기법은 상한을 표기한것이므로 상한은 여러개가 존재할 수 있다.그러나 빅오표기법이 최소 함수로 표기되었을 경우만 의미가 있다.
이와 같은 문제점을 보완하기 위하여 빅오메가와 빅쎄타 표기 법이 있다.
빅오메가는 어떤 함수의 하한을 표시하는 방법이다.

빅쎄타는 동일한 함수로 상한과 하한을 만들 수 있는 경우,즉 f(n)=O(g(n))이고,f(n)=Ω(g(n))인 경우를 f(n)=Θ(g(n))이라 한다.

최선,평균,최악의 경우

수행시간을 얘기할때 평균적인 수행시간을 구하는것이 가장 좋아보이지만,광범위한 자료집합에 대하여 알고리즘을 적용시켜서 평균값을 계산하는것은 상당히 힘들다
따라서 최악의 경우의 수행시간이 알고리즘의 시간 복잡도 척도로 많이 쓰인다.
최악의 경우란 입력 자료 집합을 알고리즘에 최대한 불리하도록 만들어서 얼마만큼의 시간이 소모되는 지를 분석하는 것이다.

(quiz,p.35)다음의 시간 복잡도 함수를 빅오 표기법으로 표시하라

9n²+8n+1

답:O(n²)
n!+2ⁿ

답:O(n!)
n²+nlog₂n+1

답:O(n²)
$\sum_{i=1}^{n}i^{2}$
$=\frac{n(1+n^{2})}{2}$

답:O($n^{3}$)

연습문제(p.36)

2개의 정수를 서로 교환하는 알고리즘을 의사코드로 작성해보자.
```
 swap(a,b)
     tmp<-a
     a<-b
     b<-tmp
     return(a,b)
```
사용자로부터 받은 2개의 정수 중에서 더 큰 수를 찾는 알고리즘을 의사코드로 작성해보자.
```
 max(a,b)
     if (a>b) then
         return a
     else
         return b
```
1부터 n까지의 합을 계산하는 알고리즘을 의사코드로 작성해보자.
```
 sum(n)
     for i<-1 to n do
         sum<-sum+i
     return sum
```

Set(집합) 추상 자료형을 정의하라. 다음과 같은 연산자들을 포함 시켜라.(Create,Insert,Remove,Is_In,Union,Intersection,Difference)

 객체 정의 : 집합은 원소(element)라 불리우는 데이터 요소들의 모임 

 연산 정의 : 

 Create() := 집합을 생성하여 반환한다. 

 Insert(S, item) := 원소 item을 집합 S에 저장한다. 

 Remove(S, item) := 원소 item를 집합 S에서 삭제한다. 

 Is_In(S, item) := 집합 S에 item이 있는지를 검사한다. 

 Union(S1, S2) := S1과 S2의 합집합을 구한다. 

 Intersection(S1, S2) := S1과 S2의 교집합을 구한다. 

 Difference(S1, S2) := S1과 S2의 차집합을 구한다.

Boolean 추상자료형을 정의하고 다음과 같은 연산자들을 포함 시켜라.

 객체정의 : 0과 1 

 연산정의 :

 And(b1, b2) := b1=1 이고 b2=1 이면 1을 반환하고, 아니면 0을 반환한다. 

 Or(b1, b2) := b1=1 이거나 b2=1이면 1을 반환하고, 아니면 0을 반환한다.

 Not(b) := b=0 이면 1을 반환한다. b=1이면 0을 반환한다. 

 Xor(b1, b2) := (b1=1 이고 b2=1) 이거나 (b1=0 이고 b2=0) 이면 0을 반환하고, 아니면 1을 반환한다.

다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자.
```
 for(i=1,i<n;i*=2)--->log₂n
     print("hello")--->1

 f(n)=log₂n+1
 O(n)=log₂n
```

다음과 같은 코드의 시간 복잡도는?여기서 n이 프로그램의 입력이라고 가정하자.

 for (i=0,i<n;i++)------->n
     for(j=1,j<n;j*=2)---->log₂n
         print("hello")---->1

 f(n)=nlog₂n+1
 O(n)=nlog₂n

시간 복잡도 함수 n²+10n+8를 빅오 표기법으로 나타내면?(답:3.O(n²))
1. O(n)
2. O(nlog₂n)
3. O(n²)
4. O(n²log₂n)
시간 복잡도 함수가 7n+10이라면 이것이 나타내는 것은 무엇인가?(답:1.연산의 횟수)
1. 연산의 횟수
2. 프로그램의 수행시간
3. 프로그램이 차지하는 메모리의 양
4. 입력 데이터의 총개수
O(n²)의 시간 복잡도를 가지는 알고리즘에서 입력의 개수가 2배로 되었다면 실행시간은 어떤 추세로 증가하는가?(답:3.4배)
1. 변함없다.
2. 2배
3. 4배
4. 8배
f(n)에 대하여 엄격한 상한을 제공하는 표기법은 무엇인가?(답:2.빅오)
1. 빅오메가
2. 빅오
3. 빅세타
4. 존재하지않음

다음의 빅오 표기법들을 수행시간이 적게 걸리는것부터 나열하라.

O(1)    O(n)    O(log n)    O(n²)   O(nlog n)    O(n!)    O(2ⁿ)
답:O(1) ,O(log n),O(n),O(nlog n),O(n²),O(2ⁿ),(n!)

두 함수 30n+4와 n²를 여러가지 n값으로 비교하라. 언제 30n+4가 n²보다 작은 값을 갖는지를 구하라.그래프를 그려보라.

풀이:30n+4 < n² 근의 공식을 이용하여 n을 구하면 n=30.x이후부터 30n+4가 작아지는것을 알수있다.
답:n이 30보다 클경우 30n+4가 n²보다 커진다.

다음은 실제로 프로그램의 수행시간을 측정하여 도표로 나타낸 것이다.

입력의 개수n	수행시간(초)
2	2
4	8
8	25
16	63
32	162

f(n)=an+b라고 하고 n을 대입후 a,b를 구하면 f(n)=3n-4가 나온다.
g(n)=n이므로 이 프로그램의 시간 복잡도는 O(n)이다.

빅오 표기법의 정의를 사용하여 다음을 증명하라.

5n²+3=O(n²)
g(n)=n²

빅오표기법의 정의에 따르면,n>n₀에 대하여 |f(n)|<=c|g(n)|을 만족하는 2개의 상수 c와 n₀가 존재하면 f(n)=O(g(n))이다.
그러므로 n> $\sqrt 3$ 에 대하여|5n²+3|<=6|n²|을 만족하므로 5n²+3=O(n²)이다.
빅오 표기법의 정의를 이용하여 6n²+3n이 O(n)이 될수 없음을 보여라.
```
빅오표기법의 정의에 따르면,n>n₀에 대하여 |f(n)|<=c|g(n)|을 만족하는 2개의 상수 c와 n₀가 존재하면 f(n)=O(g(n))이다.
```
여기서 g(n)=n이다.
n>n₀에 대하여 |6n²+3n|<=c|n|을 만족하는 c와 n₀가 없으므로,
6n²+3n이 O(n)이 될수 없다.
배열에 정수가 들어있다고 가정하고 다음의 작업의 최악,최선의 시간 복잡도를 빅오 표기법으로 말하라.
1. 배열의 n번째 숫자를 화면에 출력한다.[최선:O(1),최악:O(1)]
2. 배열안의 숫자 중에서 최소값을 찾는다.[최선:O(1),최악:O(n)]
3. 배열의 모든 숫자를 더한다.[최선:O(n),최악:O(n)]

'자료구조' 카테고리의 다른 글

04.스택 (0)	2023.11.23
배열,구조체,포인터 (0)	2023.11.23
02.순환 (0)	2023.11.22
01.자료구조와 알고리즘 (0)	2023.11.22

nyeongha's logfile

자료구조와 알고리즘

1.1 자료구조와 알고리즘

자료구조란?

컴퓨터 프로그램은 무엇으로 이루어져있을까?

알고리즘이란?

알고리즘이 되기 위한 조건

알고리즘을 기술하는 4가지 방법

quiz(p.17)

1-2 추상 자료형

C언어에서 제공하는 자료형

추상화란?

ADT(추상자료형,캡슐화,정보은닉)

quiz(p.21)

1.3 알고리즘 성능 분석

알고리즘 복잡도 분석 방법

시간 복잡도 함수

빅오 표기법

빅오표기법 이외의 표기법

최선,평균,최악의 경우

(quiz,p.35)다음의 시간 복잡도 함수를 빅오 표기법으로 표시하라

연습문제(p.36)

'자료구조' 카테고리의 다른 글

티스토리툴바

자료구조와 알고리즘

1.1 자료구조와 알고리즘

자료구조란?

컴퓨터 프로그램은 무엇으로 이루어져있을까?

알고리즘이란?

알고리즘이 되기 위한 조건

알고리즘을 기술하는 4가지 방법

quiz(p.17)

1-2 추상 자료형

C언어에서 제공하는 자료형

추상화란?

ADT(추상자료형,캡슐화,정보은닉)

quiz(p.21)

1.3 알고리즘 성능 분석

알고리즘 복잡도 분석 방법

시간 복잡도 함수

빅오 표기법

빅오표기법 이외의 표기법

최선,평균,최악의 경우

(quiz,p.35)다음의 시간 복잡도 함수를 빅오 표기법으로 표시하라

연습문제(p.36)

'자료구조' 카테고리의 다른 글

관련글

티스토리툴바