자료 구조

1. 일상생활에서의 사물의 조직화

2. 일상생활과 자료구조의 비교

3. 자료구조와 알고리즘

• 프로그램 = 자료구조 + 알고리즘
• 예) 최대값 탐색 프로그램 = 배열 + 순차탐색

4. 알고리즘

1) 알고리즘 (algorithm)

• 컴퓨터로 문제를 풀기 위한 단계적인 절차

2) 알고리즘의 조건

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

5. 알고리즘의 기술 방법

• 1. 영어나 한국어와 같은 자연어
• 1. 흐름도 (flow chart)
• 1. 유사 코드 (pseudo-code)
• 1. C와 같은 프로그래밍 언어
• 예) 배열에서 최대값 찾기 알고리즘 …ArrayMax(A,n)

1) 자연어로 표기된 알고리즘

• 인간이 읽기가 쉽다.
• 그러나 자연어의 단어들을 정확하게 정의하지 않으면 의미 전달이 모호해질 우려가 있다.
• 예) 배열에서 최대값 찾기 알고리즘

ArrayMax(A,n)

1. 배열 A의 첫번째 요소를 변수 tmp에 복사
2. 배열 A의 다음 요소들을 차례대로 tmp와 비교하면 더 크면 tmp로 복사
3. 배열 A의 모든 요소를 비교했으면 tmp를 변환

2) 흐름도로 표기된 알고리즘

• 직관적이고 이해하기 쉬운 알고리즘 기술 방법
• 그러나 복잡한 알고리즘의 경우, 상당히 복잡해짐

3) 유사코드로 표현된 알고리즘

• 알고리즘의 고수준 기술방법
• 자연어보다는 더 구조적인 표현 방법
• 프로그래밍 언어보다는 덜 구체적인 표현방법
• 알고리즘 기술에 가장 많이 사용
• 프로그램을 구현할 때의 여러가지 문제들을 감출 수 있다.
• 즉, 알고리즘의 핵심적인 내용에만 집중할 수 있다.

  ArrayMax(A,n)

  tmp <- A[0];
  for i<- 1 to n-1 do
            if tmp < A[i] then
                    tmp <- A[i];
  return tmp;

4) C로 표현된 알고리즘

• 알고리즘의 가장 정확한 기술이 가능
• 반면 실제 구현시의 많은 구체적인 사항들이 알고리즘의 핵심적인 내용들의 이해를 방해할 수 있다.

  #define MAX_ELEMENTS 100
  int score[MAX_ELEMENTS];
  int find_max_score(int n)
  {
    int i,tmp;
    tmp = score[0];
    for(int i; i<n ; i++){
      if(score[i] > tmp){
        tmp = score[i];
      }
    }
    return tmp;
  }