[자료구조] 1주차

[자료구조] 1주차

- 영남대학교 자료구조 수업 

- 더 깔끔한 정리: https://www.notion.so/1-770d055ad3314bf2ac739108244e8d9d?pvs=4 

 

자료구조란?

• 자료구조
  • 어떤 형태로 데이터를 저장할 것이냐
  • 문제 해결을 위해 데이터를 조직하여 표현하는 방법

(1) 자료구조 예시

• 전화번호부: 이름을 통해 전화번호를 찾아낼 수 있다
  • 배열, 연결리스트, 트리 등의 다양한 자료 형태를 사용할 수 있다
  • 어떤 자료 구조를 쓰냐에 따라 특징이 상이하다.

(2) 자료구조의 중요성

• 주어진 문제의 특성에 맞는 자료구조를 선택하면 프로그램의 개발이 쉽고, 성능이 향상된다.

 

 

추상 데이터 타입

• 자료구조를 기술할 때 사용하는 방법
• 데이터 객체의 연산의 명세와 데이터 객체의 내부 표현 양식 / 연산의 구현 내용을 분리
• 함수의 내부 동작과정 및 구현 방법은 은폐할 수 있다

   (1) 자연수

• Zero(), Is_Zero(), Add(x, y), Equal(x, y), Succeessor(x), Subtract(x, y) 등 존재
• 사용자는 자연수를 볼 수는 있지만 내부적으로 어떻게 연산이 수행되는지는 은폐된다.

 

 

알고리즘이란?

• 알고리즘: 문제 해결을 위해 특정한 일을 수행하는 명령어들의 집합

- 명확성/유한성/유효성: 명령어들이 충족해야 하는 조건

 

(1) 알고리즘 예시

• 코끼리를 냉장고에 넣는 방법
  1. 냉장고 문을 연다
  2. 코끼리를 냉장고에 넣는다 ( ← 구현 불가능한 명령어 )
  3. 냉장고 문을 닫는다
  • 2번이 실행 불가능하기 때문에 알고리즘이 안 된다
  • (입력: 냉장고와 코끼리 / 출력: 코끼리가 들어간 냉장고 )
• 라면을 끓이는 법
  1. 냄비에 물을 500ml 넣고 거품이 날 때까지 끓인다
  2. 라면과 스프를 함께 넣는다
  3. 거품이 나면 불을 끈다
  • 모두 실행 가능하고 유한번으로 종료되기 때문에 알고리즘이 된다
  • (입력: 라면 재료 / 출력: 맛있게 끓인 라면)

(2) 알고리즘의 표현

• 예시: 이진 검색
• 오름차순으로 정렬된 정수배열 list[] 에서 key 가 주어질 때, list[i] = key 인 i 를 발견하는 문제

• 위와 같이 알고리즘은 자연어 / 유사 코드 / 프로그래밍 언어로 표현할 수 있다.
• compare( 같다면 0, key가 크다면 -1, key가 작다면 1이 넘어오는 함수 )

 

순환 알고리즘

• 순환 알고리즘: 자기 자신을 다시 호출하는 알고리즘

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

  • 재귀 알고리즘 (순환 알고리즘)을 작성하는 방법
    • 재귀 호출을 종료하는 경계 조건을 설정
    • 각 단계마다 경계 조건에 접근하도록 알고리즘의 재귀 호출
  • 이진 검색을 순환 알고리즘으로 구현하기

  int binsearch(int list[], int key, int left, int right)
  {
  	int middle;
  	if ( left <= right ) {           // 중간을 넘어가지 않았다면
  		middle = (left + right) / 2;
  		switch (compare(list[middle], key)) {
  		case -1:   // key 가 middle 보다 크다
  			return binsearch(list, key, middle+1, right); // middle 이후 검사
  		case 0: return middle;
  		case 1:    // key 가 middle 보다 작다
  			return binsearch(list, key, left, middle-1); // middle 이전 검사
  		}
  	}
  	return -1;
  }
  

 

 

 

알고리즘의 복잡도

1. 성능 분석

(1) 프로그램의 평가 기준

• 주어진 문제를 해결        // 필수적인 요소
• 정확성                           // 필수적인 요소
• 문서화
• 모듈화                           // 함수를 체계적으로 잘 나누었는지
• 가독성                           // 누구나 쉽게 이해할 수 있는지, 함수/변수 이름
• 공간 효율성                  // 프로그램 성능과 관련
• 시간 효율성                  // 프로그램 성능과 관련

(2) 복잡도(Complexity)의 정의

• 공간 복잡도: 프로그램 실행에 사용되는 메모리
• 시간 복잡도: 프로그램 실행에 걸리는 시간

 

2. 시간 복잡도

• 실행에 걸리는 시간(Tp) = 컴파일 시간 + 실행 시간
  • 컴파일 시간은 고정 & 한 번만 필요
  • 질문: Tp를 어떻게 계산할까?
    • Tp는 컴파일러 option과 하드웨어 사양에 따라 가변
    • 프로그램 단계 수를 활용하자
  (1) 프로그램 단계 수 (Program Step)
  • 정의: 실행 시간이 프로그램의 특성과는 무관한 프로그램의 문법적인 혹은 논리적인 단위
  • 프로그램 단계 수의 계산
    • ㄱ. 프로그램에 count 를 증가시키는 문장을 추가  
    • ㄴ. 테이블 방식을 이용

• 무언가 일을 할 때마다 일을 하므로 1이 들어가도록 한다
• 스텝 수와 빈도 수를 곱한 다음 전체 스텝을 더하면 테이블 방식으로 단계 수를 구할 수 있다.

 

• 행열에 대해 계산하는 방법
• 결과 값으로 나온 2n+2 / 2n+3 등의 속도 차이를 객관적으로 판단할 수 있느냐에 대한 의문증 생김

•  

3. 점근 표기법

• 동기
  • 정확한 프로그램 단계 수를 계산하는 것은 쉽지 않다
  • 프로그램 단계 수의 정의 자체가 정확하지 않다
  • 100n + 10 과 30n + 30 의 비교를 할 수 있는가?
• 접근 방법
  • Tp(n) = n^2 + 100n 이라고 가정
  • n이 충분히 클 경우 임의의 c3에 대해 Tp(n) > c3n
  • 어느 순간 n이 충분히 커지면 n^2이 n보다 실행 시간이 훨씬 더 걸릴 것이라고 예측 가능
  • 이런 관점에서 점근 표기법/유사 표기법에 대해 알아본다

• Example
  • n이 2보다 클 때 3n은 항상 4n보다 작다
  • 100n + 6도 n이 6보다 크다면 항상 101n보다 작다
  • 밑에 것들도 이와 같다
  • Big-Oh는 g(n)이 충분히 크다면 황당한 결과가 나올 수도 있다
  • 그래서 오메가나 세타가 미세한 차이를 조정해 주기 위해 존재한다

 

 

• Example
  • 마지막 Example 을 보면 어쨌든 오메가는 하한선을 말하는 것이니까 저렇게 표기하는 것도 틀린 게 아니다.
  • 즉, 우리는 어디부터 어디까지인지 정확하게 경계선을 정의하는 것이 필요하다.
  • 그래서 나온 것이 세타 표기법이다.

 

 

• Example
  • 세타는 f(n)이 정확하게 g(n)의 사이에 있다고 정의하는 것이다.
  • 3n+2 는 n이 2보다 클 때 3n보다는 크고 4n보다는 작다. 따라서 Theta(n)이라고 적는다.
  • 최종적으로 프로그램 단계수를 단항식으로 표현하면 ‘가장 최고차항’에 따라 결정되게 된다.

 

 

• 최고차항에 따라 아주 큰 시간적 복잡도 차이가 나타나게 된다.

 

 

• 결국 시간 복잡도 차원에서는 반복문으로 구현하든 순환 알고리즘으로 구현하든 시간 복잡도가 동일하다는 것을 알 수 있다.
• 다만 Row * Col 은 다르게 나타난다
• 이진 검색은 전체 n 개 중에서 원하는 것을 찾는 시간이 ‘중간에 있는 것을 비교하는 시간 + 큰쪽이나 작은쪽에서 다시 찾는 시간’이므로 log2에 비례한다.
• O(1)은 n에 비례 관계 없이 시간이 상수적으로 동일하다는 것이다.

요약 정리

• 복잡도의 정의를 이해
• 알고리즘의 시간 복잡도를 분석하는 방법 이해
• 복잡도를 점근 표기법으로 표현하는 방법 이해