2과목 : 소프트웨어 개발 (1장. 데이터 입,출력 구현 : 주요 키워드 정리)

1장. 데이터 입, 출력 구현

 

1-0. 자료구조

- 일련의 자료들을 조직하고 구조화 하는 것

- 종류

• 선형구조 : 순서가 있는 구조
  • 배열 : 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합.
  • 선형리스트
    • 연속리스트(배열과 같이 연속되는 기억장소에 저장되는 자료구조)
    • 연결리스트(임의의 공간에 기억, 자료 항목 순서에 따라 노드와 포인터를 이용하여 서로 연결시킨 자료구조)
  • 스택 : 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조, 후입 선출
  • 큐 : 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료구조, 선입선출
• 비선형 구조 : 순서가 없는 구조
  • 그래프 : 간선의 방향성 유무에 따라 방향그래프와 무방향 그래프로 이루어짐.
  • 트리 : 정점(Node)와 선분(Branch)를 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
    • 노드 : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것
      • ex) A,B,C,D,E,F,G...
    • 근노드 : 트리 맨위에 있는 노드 ex) A
    • 디그리 : 각 노드에서 뻗어나온 가지의 수 ex) A=3, B=2, C=1, D=3
    • 단말노드 : 자식이 하나도 없는 노드 ex) K,L,F,G,M,I,J
    • 자식노드 : 어떤 노드에 연결된 다음 레벨의 노드들 ex) D의 자식노드(H,I,J)
    • 부모노드 : 어떤 노드에 연결된 이전 레벨의 노드들 ex) E,F의 부모노드(B)
    • 형제노드 : 동일한 부모를 갖는 노드들 ex) H의 형제 노드(I,J)
    • 트리의 운행법
      • Preorder 운행 (전위 순회) : Root - Left - Right 순서
      • Inorder 운행 (중위 순회) : Left - Root - Right 순서
      • Postorder 운행 (후위 순회) : Left - Right - Root 순서

트리 참고 사진

• 수식의 표기법
  • 전위 표기법 ( 연산자 - Left - Right)
  • 중위 표기법 (Left - 연산자 - Right)
  • 후위 표기법 (Left - Right - 연산자)

 

1-1. 정렬

• 삽입 정렬 : 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬.
  • 복잡도 : O(n^2)
  • 초기 상태 : 8 5 6 2 4
    • 1회전 : 5 8 6 2 4
    • 2회전 : 5 6 8 2 4
    • 3회전 : 2 5 6 8 4
    • 4회전 : 2 4 5 6 8
• 쉘 정렬 : 삽입 정렬을 확장한 개념, 복잡도 : O(n^2)
• 선택 정렬 : n개의 레코드 중에서 최소 값을 찾아 첫번째, 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두번째 레코드 위치에 놓는 방식을 반복하여 정렬.
  • 복잡도 : O(n^2)
  • 초기 상태 : 8 5 6 2 4
    • 1회전 : 5 8 6 2 4 - > 5 8 6 2 4 -> 2 8 6 5 4
    • 2회전 : 2 6 8 5 4 -> 2 5 8 6 4 -> 2 4 8 6 5
    • 3회전 : 2 4 6 8 5 -> 2 4 5 8 6
    • 4회전 : 2 4 5 6 8
• 버블 정렬 : 주어진 파일에 인접한 두개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환
  • 복잡도 : O(n^2)
  • 초기 상태 : 8 5 6 2 4
    • 1회전 : 5 8 6 2 4 -> 5 6 8 2 4 -> 5 6 2 8 4 -> 5 6 2 4 8
    • 2회전 : 5 6 2 4 8 -> 5 2 6 4 8 -> 5 2 4 6 8
    • 3회전 : 2 5 4 6 8 -> 2 4 5 6 8
    • 4회전 : 2 4 5 6 8
• 퀵정렬 : 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로, 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분해한다. 복잡도 : O(nlogn)
• 힙정렬 : 전이진 트리를 이용한 정렬 방식. 복잡도 : O(nlogn)
• 2- way 합병정렬 : 이미 정렬되어 있는 2개의 파일을 한 개의 파일로 합병하는 정렬방식. 복잡도 : O(nlogn)
• 기수정렬 : 큐를 이용하여 자릿수별로 정렬하는 방식. 복잡도 : O(dn)

 

1-2. 데이터베이스

- 데이터 저장소 : 소프트웨어 개발 과정에서 다루어야 할 데이터들을 물리적인 공간에 구축한 것

- 데이터베이스 : 특정 조직의 업무를 수행하는데 필요한 상호 관련된 데이터들의 모임

• 통합된 데이터 : 자료의 중복을 배제한 데이터의 모임
• 저장된 데이터 : 컴퓨터가 접근 가능한 저장매체에 저장된 자료
• 운영 데이터 : 업무를 수행하는데 존재 가치가 확실하고 없어서는 안될 반드시 필요한 자료
• 공용 데이터 : 여러 응용 시스템들이 공동으로 소유하고 유지하는 자료

 

- DBMS : 사용자와 데이터베이스 사이에서 사용자의 요구에 따라 정보를 생성해주고, 데이터베이스를 관리해주는 소프트웨어

- 스키마 : 데이터베이스의 구조와 제약조건에 관한 전반적인 명세를 기술한 메타데이터의 집합

• 외부스키마 : 사용자나 응용프로그래머가 각 개인의 입장에서 필요로 하는 데이터베이스의 논리적 구조
• 개념스키마 : 전체적인 논리적 구조로서, 모든 응용프로그램이나 사용자들이 필요로하는 조직 전체의 데이터베이스
• 내부스키마 : 물리적 저장장치의 입장에서 본 데이터베이스 구조

 

1-3. 데이터 입, 출력

- 데이터 입출력 : 소프트웨어 기능 구현을 위해 데이터베이스의 데이터를 출력하는 작업을 의미

- 관계 대수 : 원하는 정보와 그 정보를 검색하기 위해서 어떻게 유도하는가를 기술하는 절차적인 언어

- 관계 해석 : 관계 데이터의 연산을 표현하는 방법. 원하는 정보가 무엇인가만을 기술한 언어

- 데이터 접속 : 기능 구현을 위해 프로그래밍 코드와 데이터베이스의 데이터를 연결 하는 것

• SQL Mapping : 프로그램 코드 내에 SQL 직접 입력
• ORM : 객체지향 프로그래밍의 객체와 관계형 DB의 데이터를 연결 하는 것

- 트랜잭션 : 데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업 단위

• 원자성 : 트랜잭션 연산은 모두 반영되도록 완료되던지, 전혀 반양되지 않도록 복구되어야 함.
• 일관성 : 트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환함
• 독립성 : 둘 이상의 트랜잭션이 동시에 병행 실행되는 경우 어느 하나의 트랜잭션 실행중에 다른 트랜잭션이 끼어들 수 없음.
• 지속성 : 성공적으로 완료된 트랜잭션의 결과는 시스템이 고장나더라도 영구적으로 반영되어야 함.

 

1-4. 절차형 SQL

- C와 JAVA 등의 프로그래밍 언어와 같이 연속적인 실행이나 분기, 반복등의 제어가 가능한 SQL

• 프로시저 : 일종의 트랜잭션 언어로, 호출을 통해 실행되어 미리 저장해놓은 SQL작업을 수행
• 트리거 : 입력,갱신,삭제 등의 이벤트가 발생시 자동수행
• 사용자정의함수 : SQL을 사용하여 일련의 작업을 연속처리