036 자료구조 - 1장 데이터 입출력 - 2과목 소프트웨어 개발

1. 자료구조의 정의
   1. 자료구조란
      1. 기억장치 공간 내에 저장하는 방법
      2. 그룹 내에 존재하는 자료 간의 관계
      3. 처리 방법
   2. 프로그램 작성시 가장 우선적 고려사항
      1. 저장 공간의 효율성
      2. 실행시간의 신속성
2. 자료 구조 분류
   1. 선형 구조
      1. 배열
      2. 선형 리스트
         1. 연속 리스트(Contiguous List)
         2. 연결 리스트(Linked List)
      3. 스택
      4. 큐
      5. 데크
   2. 비선형 구조
      1. 트리
      2. 그래프
3. 배열
   1. 동일한 자료형의 데이터들
   2. 같은 크기로 나열되어 순서를 가지고 있는 집합
   3. 정적인 자료 → 추가가 어렵다
   4. 삭제된 데이터의 기억장소가 null로 남아 메모리 낭비 발생
   5. 첨자를 이용해 데이터 접근
   6. 반복적인 데이터 처리 작업에 적합
   7. 데이터마다 동일한 이름의 변수를 사용하여 처리가 간편
   8. 사용한 첨자의 개수에 따라 n차원 배열이라고 부름
      1. 크기가 n인 1차원 배열a[0] a[1] a[2] .... a[n-1]

         a[0]

         a[1]

         a[2]

         ...

         a[n-1]

      2. 크기가 n * n인 2차원 배열
      
      

      a[1][0]	a[1][1]	a[1][2]	...	a[1][n-1]
      a[2][0]	a[1][1]	a[2][2]	...	a[2][n-1]
      a[n-1][0]	a[n-1][1]	a[n-1][2]	...	a[n-1][n-1]

4. 선형 리스트(Linear List)
   1. 일정한 순서에 의해 나열된 자료 구조
   2. 빈 공간 없이 차례차례 데이터가 저장된다
   3. 연속 리스트
      1. 배열을 이용
      2. 장점) 기억장소 이용 효율 밀도 1*
         1. 밀도가 높다 = 기억장소를 빈공간없이 꽉 차게 사용한다
      3. 단점) 중간에 데이터 삽입, 삭제 시 자료 이동이 필요 = 시간이 오래걸림
   4. 연결 리스트
      1. 포인터*를 이용
         1. *현재의 위치에서 다음 노드의 위치를 알려주는 요소
      2. 반드시 연속적이지 않음
      3. 포인터로 서로를 연결시킨 자료 구조
      4. 삽입, 삭제 작업 용이
      5. 포인터 부분 때문에 순차 리스트에 비해 공간 이용 효율 및 접근 속도 낮음
      6. 중간에 노드가 끊어지면 다음 노드 찾기 어려움
5. 스택
   1. 리스트의 한쪽 끝으로만 삽입, 삭제가 이루어지는 자료 구조
   2. 후입선출(LIFO)
   3. 스택의 용도 : 재귀 호출, 후위(Postfix) 표기법, 서브루틴 호출, 인터럽트 처리, DFS
   4. 스택 오버플로우 : 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 발생
   5. 스택 언터플로우 : 삭제할 데이터가 없는 상태에서 데이터를 삭제 시 발생
   6. TOP : 가장 마지막에 삽입된 자료
   7. Bottom : 가장 밑 자료
   8. 자료 삽입 방식(push)
      

      

   9. 자료 삭제 방식
      
      

      

6. 큐
   1. 리스트의 한쪽에서는 삽입
   2. 다른 한쪽에서는 삭제 작업
   3. 선입선출(FIFO)
   4. 프런트(F, Front) 포인터 : 가장 먼저 삽입된 자료
   5. 리어(R, Rear) 포인터 : 가장 마지막에 삽입된 자료
   6. 운영체제의 작업 스케줄링에 사용
7. 그래프
   1. 정점(V, Vertex)와 간선(E, Edge)의 두 집합으로 이루어짐
   2. 간선의 방향성 유무에 따라
      1. 방향 그래프
         1. 최대 간선수 (n개의 정점) → n(n-1)
      2. 무방향 그래프
         1. 최대 간선수 (n개의 정점) → n(n-1)/2
   3. 통신망(네트워크), 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향선분 해법 등에 응용됨
   4. 트리는 사이클이 없는 그래프이다.