2과목 - 소프트웨어 개발[데이터 입,출력 구현]

• 자료 구조
  • 선형구조 : 한줄로 세울 수 있는것
    • 배열
      • 같은 크기로 나열된 집합(연속적으로 배치)
      • 정적자료 / 기억장소에 추가 어려움 / 메모리 낭비 심함
      • 인덱스로 접근 가능함
    • 선형리스트
      • 연결리스트
        • 포인트
        • 연속적이지 않음 / 접근 속도 느림 / 중간 노그 끊어지면 찾기 힘듬
        • 메모리상에 연속적으로 배치되지 않음
    • 큐
      • 한방향은 출구, 한방향은 입구
      • FIFO(First In First Out)
      • Front(Hearder) 삭제 / Tail(Rear) 삽입
      • 포인터가 2개인 것은 큐
      • 사용하는 시스템
        • 프린트 : 먼저, 인쇄 누른 순서대로 처리함
        • 프로그램, 시스템 스케줄링
    • 스텍 - 물컵 연상
      • 한쪽(입구/출구) 존재 
      • LIFO(List In First Out) : 마지막에 들어온 것이 처음에 나온다.
      • 더이상 OverFlow - 추가시 / UnderFlow - 삭제시 없을때...
      • 순차적인 작업 : 함수 호출/ 수식 계산 /컴파일
      • 추가 순서
        • Top = Top + 1 해주고, save
      • 삭제 순서
        • remove 해주고, Top = Top - 1
      • 스텍을 이용한 연산
        • 재귀호출, 후위표현, 깊이우선탐색
          • 깊이 우선 탐색
            • 노드와 실선으로 갈떄까지 간 것
    • 데크
      • 삽입, 삭제 양쪽 끝 모두 발생할 수 있는 상태
  • 비선형구조
    • 트리
      • 트리의 용어
        • 루트(부모)
        • 노드
        • 차수
          • 노드의 차수
            • 각각의 노드의 차수
          • 트리의 차수 
            • 전체 노드 중에 가장 자식이 많은 차수
          • 단말 노드
            • 자식이 없는 노드
      • 운행법 또는 순회라고 한다. 
        • 설명 : 다 방문하다는 뜻 
          • 전위(Pre) ,중위(In), 후위(Post)
      • 수식표기법
        • 전위(Pre) ,중위(In), 후위(Post)
         
    • 그래프
      • 노드(점선) = n 
      • 방향
        • n(n-1)
      • 무방향
        • n(n-1)/2
  • 정렬
    • 선택 정렬 : 가장 작은 수를 찾음 -> 앞으로 나보다 큰놈이랑 바꾼다. 그게 1회전
      
      • 재귀호출, 후위 표현, 깊이 우선 검색
    • 버블 정렬 :  왼쪽부터 인접한 2개의 숫자를 비교함 | 1회전시 가장 큰 수가 오른쪽에 위치함
      • 시간 복잡도O(n)
    • 삽입 정렬  : 왼쪽에서 두번째 숫자부터 비교 왼쪽부터 / 8 9 7 이면, 7하고 8하고 자리 바꾼다. 하지만, 8이 뒤로 가는 것이 아니라 9가 뒤로 밀고 그 자리에 8이 들어감
      • 예 : 8 | 9 | 7 인데, 7은 9하고 비교하고 9보다 7이 작으니, 9 앞으로 가고 그 다음 7은 8하고 비교하고 7은 8보다 작으니, 8 앞으로 삽입함
      • 시간 복잡도는 운이 좋다면, 짧게 O(n) 그렇지 않다면, 시간 복잡도O(n)2까지 간다.
    • 퀵 정렬
      • 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬한다.
  • 검색
    • 이분(이진)검색
      • 순서가 정해져 있어야 함
      • 가운데 중심으로 서브 파일 2개로 나누어 검색함으로써 검색횟수가 줄어
      • Key 값과 비교하여 검색함
    • 해싱
      • 제산법 또는 제산방법  - 양의 정수인 소수 나누어
        • 제산 함수라고도 한다. 
        • 나누어 나온 나머지를 통해서 값을 찾는다.
      • 중간 제곱 방법 또는 제곱법 - 중간 부분의 값
      • 중첩 방법 또는 폴딩법 : 배타적 논리합(XOR : Exclusive OR)
      • 기수 변환 방법 : 레코드 키값
      • 숫자 분석 함수
  • 알고리즘 설계 방법
    • 분할 정복(Divide and Conquer)
      • 작은 단위로 분리 문제 분할
    • 동적 프로그래밍(Dynamic)
      • 분할 정복과 나누는 부분은 같지만, 저장하여 사용함
    • 탐욕 알고리즘(Greedy)
      • 눈 앞에서 가장 적합한 것을 선택함(최적의 선택지를 선정함)
    • 백트래킹
      • 현재 해결책이 적합하지 않다면, 되돌아가는 것

수식 표기법

* 위에서 중요한 포인트

•  *나 /는 +와- 보다 우선순위이다 .하지만, 간혹 연산자 + 피연산자 + 피연산자 나 피연산자 + 피연산자 + 연산자로해서 +나 -가 먼저 될 경구가 존재한다. 그러면, ()를 주어 *와/ 보다 먼저라는 것을 표시하면 된다.
• A*(B+C) -> A*(BC+) -> A(BC+)*

운행법