정보처리기사_2과목_소프트웨어개발(0)

데이터 입출력 구현

자료구조   정의 = 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라 분류하여 구성하고 저장 및 처리하는 모든 작업  구성   1. 선형 구조 : 데이터 항목 사이의 관계가 1:1 >> ex) 배열,리스트,스택,큐,데크   2. 비선형 구조 : 데이터 항목 사이의 관계가 1:n(일대다) >> ex)트리, 그래프  연결리스트의 개요                  연결리스트는 다음 데이터를 포인터를 이용하여 찾아내며, 노드는 자기참조구조체(데이터 필드, 포인터 필드)이다.                                         **주소  스택 - LIFO,후입선출   - 제한된 구조로 원소의 삽입과 삭제가 한쪽(TOP)에서만 이루어지는 유한 순서리스트   - 스택의 응용: 수식계산, 복귀주소관리, 순환식, 퀵 정렬, 깊이 우선 탐색, 이진트리 운행  큐 - FIFO, 선입선출   - 한쪽 끝(REAR)에서 원소의 삽입만, 다른 쪽 끝(FRONT)에서는 우너소의 삭제만 허용   - 큐의 응용 : 작업 스케줄링, 너비우선 탐색 , 트리의 레벨 순회    데크    - 스택 + 큐  트리   - 계층형 자료구조(Hierarchical data structure)의 나무 형태로 노드들을 간선으로 연결   - 이진트리 = 자식이 2개까지 허용  ※ 트리의 용어   형제(siblings) : 한 부모의 자식들이다.   트리의 차수 : 그 트리에 있는 노드의 최대차수이다.   단말노드 : 자식 없는 노드  ★트리의 순행(운행)     전위,중위,후위   전위,중위,후위 순회 방법 경로의 종합적인 표현 예  그래프   그래프 순회 : 깊이 우선 탐색 = 스택, 너비 우선 탐색 = 큐

알고리즘  알고리즘의 정의   컴퓨터로 문제를 풀기위한 단계적인 절차, 특정 작업을 수행하기 위한 명령어들의 집합  알고리즘의 조건   1. 입력 : 외부에서 제공되는 데이터가 0개 이상 있다.   2. 출력 : 적어도 하나의 결과를 생성한다.   복잡도 => 얼마나 많이 쓰는지  프로그램 공간의 복잡도(space complexity)   - 프로그램을 실행시켜 완료하는 데 필요한 총 저장 공간을 말한다.  프로그램 시간의 복잡도   - 프로그램을 실행시켜 완료하는 데 걸리는 시간을 의미한다. 연산 시간의 크기 순서 정렬 알고리즘의 복잡도  정렬종류         평균         최악   버블정렬        O(n²)        O(n²)   선택정렬        O(n²)        O(n²)   삽입정렬        O(n²)        O(n²)   퀵정렬          O(n log²n)  O(n²)