[연결리스트]-리스트기본적인 연산: 삽입, 삭제, 검색 등리스트를 구현하는 대표적인 두 가지 방법: 배열, 연결 리스트[스택(LIFO)]리스트의 일종. 데이터의 삽입과 삭제가 한 쪽 끝(top)에서만 이루어짐.[큐(FIFO)]리스트의 일종. 데이터의 삽입은 한 쪽 끝(rear)에서, 삭제는 반대쪽 끝(front)에서만 일어남. 따라서 연결리스트의 앞쪽을 front, 뒤쪽을 rear로 하는 것이 유리함.삽입을 위해서는 마지막 노드의 주소를 항상 기억해야 함.[정렬]데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일.레코드: 정렬의 대상필드: 레코드를 구성하는 작은 단위의 데이터키: 레코드를 식별하는 역할을 하는 필드1. 단순하나 비효율적- 삽입 정렬, 선택 정렬, 버블 정렬2. 복잡하나 효율적- 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬-선택 정렬-정렬 대상 데이터에서 가장 작은 수 또는 가장 큰 수를 찾아 정렬정렬 대상 데이터 수만큼의 저장 공간(정렬 공간)을 마련한 후 정렬 대상 데이터 집합에서 기준으로 수를 선택한 후 결과 공간으로 옮기는 정렬-삽입 정렬-정렬 대상 데이터를 정렬하기 위해 정렬된 목록과 정렬되지 않은 목록으로 구분정렬되지 않은 목록의 데이터 하나를 정렬된 목록의 올바른 위치에 삽입하여 정렬을 유지비교해서 크면 비교한 데이터 뒷 자리에 추가, 작으면 비교한 데이터를 뒷 자리로 이동-버블 정렬-정렬 대상 데이터를 정렬하기 위해 인접한 두 개의 데이터를 비교크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 수행-합병 정렬-하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬-퀵 정렬-분할 정복 방법에 근거: 합병 정렬과 유사하게 전체 리스트를 2개의 부분 리스트로 분할(비 균등 분할), 각각의 부분 리스트를 다시 퀵 정렬-기수 정렬-입력데이터에 비해 비교 연산을 실행하지 않고 데이터를 정렬-셀 정렬-삽입 정렬의 문제점 해결 및 장점을 활용전체 데이터를 특정 규칙(간격)을 갖는 부 데이터로 만든 후 각 부 데이터를 정렬부 데이터의 정렬을 통해 전체 데이터가 정렬될 때까지 계속 반복오름차순으로 정렬[Big-O표기법]- 알고리즘의 성능을 수학적으로 표현해주는 표기법- 알고리즘의 시간과 공간복잡도를 표현 할 수 있다.- 실제 러닝타임 표시인 것보다는 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표. 상수와 같은 숫자는 모두 1이 된다.1. O(1)알고리즘- 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘. (일정한 속도)- 데이터가 증가함에 따라 성능에 변함이 없다.2. O(n)- 입력 데이터의 크기에 비례해 처리시간이 걸리는 알고리즘을 표현할 때 사용- 데이터와 시간이 늘 같은 비율로 증가함.? 알고리즘의 효율성1) 시간 : 이 알고리즘이 얼마나 빠른가. -> 시간 복잡도2) 공간 : 이 알고리즘이 메모리를 얼마나 사용하는가. -> 공간 복잡도따로 이야기하지 않는 이상 대부분의 복잡도는 시간 복잡도를 말한다.알고리즘의 속도 : 입력이 n일 때 연산 횟수? 점근적표기법1) 빅오표기2) 오메가표기3) 세타표기? 트리- 자료들 간의 1:n의 관계를 가지는 비선형 자료구조도- 노드들과 노드들을 연결하는 링크들로 구성? 이진 트리: 노드의 차수를 2 이하로 정하여 전체 차수가 2이하가 되도록 한 트리? 포화 이진 트리- 단말 노드를 제외한 모든 노드가 포화상태(차수 : 2)로 차 있는 이진 트리? 완전 이진 트리- 단말 노드가 트리의 왼쪽부터 채워진 모습의 트리? 편향 이진 트리- 최소 개수의 노드를 가지면서 한 쪽 방향의 자식 노드만을 가진 이진 트리? 이진 트리 순회- 계층적 구조로 저장된 트리의 모든 노드의 데이터를 목적에 맞게 처리하기 위해 모든 노드를 방문하는 것. (중위 순위 / 전위 순위 / 후위 순위 / 레벨 오더 순회)[탐색]- 특별한 키 값을 가지고 있는 기억 장소에 저장되어 있는 레코드를 찾는 과정- 탐색에 사용되는 자료구조 : 배열, 연결 리스트, 트리, 그래프 등- 탐색의 대상 키를 비교하여 검색하는 방법 : 순차탐색, 이진 탐색, 트리 탐색- 계수적인 성질을 이용한 계산으로 탐색하는 방법 : 해싱? 탐색- 테이블에서 특정 레코드를 찾는 것.- 레코드는 하나 이상의 플드로 구성된다.- 키 : 테이블에서 레코드를 구별하는 필드 (예 : 주민, 학번)? 순차 탐색- 쉽고 단순한 탐색 알고리즘- 데이터 리스트에서 목표 값을 첫 요서에서 마지막 요소까지 순차적으로 찾는 방법- 탐색할 데이터가 많은 경우 비효율적이다.- 정렬된 데이터의 처음부터 탐색하려는 데이터 값과 비교하여 정렬된 데이터 값이 작으면 다음 데이터를 비교- 비교하는 데이터 값이 탐색하려는 데이터 값과 같거나 크면 비교를 종료한다.? 이진 탐색- 정렬된 배열의 탐색에 적합하다.: 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 조사한 위치에서 왼쪽 또는 오른쪽 부분 배열에 있는지 판단하고 탐색의 범위를 반으로 줄여가며 탐색을 진행한다.[이진 탐색 트리]1. Binary Search Tree? 이진 트리 기반의 탐색을 위한 자료 구조? 정의- 모든 노드의 key는 유일- 왼쪽 서브트리의 key들은 root의 key보다 작음- 오른쪽 서브트리의 key들은 root의 key보다 큼- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리[힙]-이진트리의 일종-우선순위를 큐를 위한 자료구조-값들 중에서 가장 큰 값 또는 가장 작은 값을 빠르게 찾기 위하여 만들어진 자료구조-중복된 값을 허용-완전 이진트리[힙의 종류]최대 히프- 부모노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리최소 히프- 부모노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리[삽입 알고리즘]- 새로운 데이터를 힙의 맨 마지막에 저장-새로 추가한 데이터 값이 조상 노드의 데이터 값보다 작거나 root노드가 아닐 때 까지 다음을 반복. (단, 부모노드의 데이터 값이 새로 추가된 데이터 값보다 작으면 데이터 값 교환)[삭제 알고리즘]- root 노드의 데이터 값을 힙에서 삭제하고 반환- root 노드의 데이터 값을 힙의 마지막 노드의 데이터 값으로 이동하고 힙크기를 줄임- root 노드의 데이터 값이 자손노드의 데이터 값보다 클 때까지 다음을 반복[AVL 트리]- 어느 노드에서든 두 자식 서브 트리의 높이의 차이가 1 이하인 트리- 두 서브 트리의 높이의 차이가 1보다 커지면 AVL 트리가 되도록 트리를 재구성- 탐색 연산이진 탐색 트리와 동일- 삽입 연산삽입 후 두 서브 트리의 높이의 차이가 1보다 커지면 LL,LR,RR,RL 회전을 이용해 두 자식 서브 트리의 높이의 차이가 1 이하인 트리로 만듬.- 삭제 연산삭제하려는 노드의 차수가 0인 경우- 노드만 삭제- 부모 노드와 삭제할 노드와의 링크 필드를 NULL로 지정삭제하려는 노드의 차수가 1인 경우-노드를 삭제하고 삭제할 노드의 자손노드 처리-삭제할 노드의 자손 서브트리를 부모노드에 연결삭제하려는 노드의 차수가 2인 경우-왼쪽 서브트리에서 최대 값의 노드를 찾아 삭제하고 최대 값을 삭제할 노드의 값으로 대치-오른쪽 서브트리에서 최대 값의 노드를 찾아 삭제하고 최대 값을 삭제핳 노드의 값으로 대치-삭제 후 AVL제한이 맞지 않으면 회전으로 맞춤.[그래프]-두개의 컴포넌트(정점과 간선)로 구성된 비선형 자료구조-정점과 두 정점을 연결하는 간선들의 집합-연결되어 있는 객체 간의 관계를 표현하는 자료구조-가장 일반적인 자료구조 형태[정점]- 여러 가지 특성을 가질 수 있는 객체 의미- 현상이나 사물을 정점으로 표현- 노드라고도 불림[간선]-정점들과의 관계의미-링크라고도 불림-두 정점 사이에 간선이 있으면 두 정점은 인접하다고 함[무방향 그래프]-무방향 간선만 사용-간선을 통해서 양방향으로 갈 수 있음.[방향 그래프]-방향 간선만 사용-간선을 통해서 한쪽 방향으로만 갈 수 있음.
