puravida

1. 정렬의 개념과 정렬의 종류 ① 정렬 - 순서 없이 배열된 자료를 작은 것부터 큰 것 순서인 오름차순이나, 큰 것부터 작은 것 순서인 내림차순으로 재배열하는 것 - 키 : 자료를 정렬하는데 사용하는 기준이 되는 특정 값. ②정렬 방식 분류 - 내부 정렬 □ 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식 □ 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨. - 외부 정렬 □ 정렬할 자료를 보조 기억장치에서 정렬하는 방식 □ 대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어져도 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬이 가능. 2. 선택 정렬과 버블 정렬 ① 선택정렬 - 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 ..

1. 그래프의 순회 ① 그래프 순회, 탐색 - 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산 ② 깊이 우선 탐색 - 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 반복하여 모든 정점을 방문하는 순회 방법 - 후입선출 구조의 스택 사용 ③ 너비 우선 탐색 - 시작 정점에서 인접한 정점을 모두 차례로 방문하고나서 방문했던 정점에서부터 다시 인접한 정점을 차례로 방문하는 방식 - 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회방법 -> 큐 사용 2. 신장트리 ① 신장트리 - n개의 정점으로 이루어진 무방향 ..

1. 그래프의 개념과 종류 ① 그래프 - 연결되어 있는 원소 사이의 다:다 관계 표현하는 자료구조 - G = (V,E) ② 그래프의 종류 - 무방향 그래프 : 두 정점을 연결하는 간선에 방향이 없는 그래프 - 방향 그래프 : 간선에 방향이 있는 그래프 - 완전 그래프 : 각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프 ▶정점이 n개인 무방향 그래프에서 최대의 간선 수 : n(n-1)/2개 ▶정점이 n개인 방향 그래프의 최대 간선수 : n(n-1)개 - 부분 그래프 : 원래의 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프 - 가중 그래프 : 정점을 연결하는 간선에 가중치를 할당한 그래프 ③ 그래프 관련 용어 - 차수 : 정점에 부속되어 있는 간선의 수 ▶방향 그래프의 정..

1. 점화식 ① 점화식 - 수열의 일반항을 한 개 이상의 앞선 항들을 이용하여 나타낸 식 - 원소들 사이에 일정한 규칙이 있을 수 있고 원소들의 나열 대신 이 규칙으로 표현할 수도 있으며 이를 점화식이라 함. - 수열의 항 사이에서 성립하는 관계식 2. 피보나치 수열 점화식 ① 피보나치 수열 점화식 - 앞의 두 수의 합이 바로 뒤의 수가 되는 수의 배 ② 하노이의 탑을 이용한 점화식의 예 3. 점화식의 해 ① 점화식의 해 - 점화식은 다양한 형태로 나타낼 수 있으며, 문제에 따라 독특한 방법으로 표현하여 해결하기도 함. - 점화식의 해를 구하는 방법 : 반복법, 상수계수의 선형동차점화식 등 ② 반복법 - 점화식에서 가장 많이 이용되는 방법 - 해를 구하기 위해 앞의 항을 반복적으로 나타내는 방법 ③ 상수..

1. 조합 - 임의의 집합 X가 전체 n개 원소로 구성되고 이 중 r개의 원소를 순서 없이 추출하는 것을 r 조합이라고 함. 2. 이항정리 ① 이항식 - (x+y)ⁿ과 같은 식 -> 미지수가 2개인 식 ② 이항정리 - 이항식의 각 항의 이항계수를 구하는 방법 - 예시 (x+1)⁵ 전개하기 3. 이산확률 ① 확률 - 어떤 사건이 일어날 것인지 혹은 일어났는지에 대한 가능성을 표현하는 방법 - 표본공간 S에서 특정 사건 A가 일어날 가능성 ② 표본공간과 사건 - 어떠한 시행을 했을 때 일어날 수 있는 모든 경우 (전체 사건) - 어떤 실험을 하였을 때 가능한 모든 결과 중에서 반드시 하나의 결과만 나타난다고 하면 실험의 모든 결과의 집합을 표본 공간이라고 하고, 표본 공간의 부분 집합을 사건이라고 함.

1. 플로이드 와샬 알고리즘 ① 플로이드 와샬 알고리즘 : 최단 경로를 구하는 알고리즘인 플로이드 와샬 알고리즘은 가능한 모든 노드 쌍들에 대한 최단 거리를 구하는 알고리즘 - 그래프에서 모든 정점 사이의 최단거리(4)를 구하기 위한 알고리즘 ② 다익스트라 알고리즘과 플로이드 와샬 알고리즘 비교 ③ 그래프의 탐색 방법 2. 플로이드 와샬 알고리즘의 적용방법 ① 플로이드 와샬 알고리즘 ③ 플로이드 와샬 알고리즘 수행시간 -> 모든 정점 간 경로의 최소 비용을 구하는 것은 O(|V^3|)의 시간 복잡도 가짐 ④ 이행폐쇄 : 거쳐서 갈 수 있는 모든 곳을 직접 가는 간선으로 연결한 그래프 - 간선의 추가를 통해 대부분의 노드들이 인접 노드로 바뀌게 되며 인접 행렬로 표현하는 것이 편리 3. 플로이드 와샬 알고..

1. 다익스트라 알고리즘 ① 최단 경로 문제 - 최단 경로 문제의 구분 : 시작점과 도착점의 수에 따라 구분 ◆ 단일 쌍 최단 경로 : 한 출발점에서 한 목적지로 가는 최단경로 ◆ 단일 출발 최단 경로 : 출발점 1개 목적지 여러개일 때 각각의 여러 종점까지의 최단경로 ◆ 단일 도착 최단 경로 : 출발지 여러개 목적지 1개일때 각각의 출발지에서 종점까지의 최단경로 ◆ 전체 쌍 최단 경로 : 전체 쌍 각각의 출발-목적지 쌍들 사이의 최단 경로 구하기 - 다익스트라 알고리즘 : 모든 간선 가중치가 음이 아닌 일반적인 경우 (양수) - 음의 가중치가 존재하는 경우 : 벨만 - 포드 알고리즘 -> 음의 가중치는 허용하지만 가중치 합이 음인 사이클은 절대 허용 X ② 다익스트라 알고리즘 - 어떠한 간선도 음수값을..

1. 히프의 개념과 추상 자료형 ① 히프의 개념 - 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 - 일반적으로 히프는 최대 히프를 의미 - 같은 키 값의 노드가 중복되어 있을 수도 있음 2. 히프의 삽입, 삭제 연산 ① 히프의 삽입 연산 - 1단계 : 완전 이진 트리의 조건이 만족하도록 다음 자리 확장. (노드 n개인 완전 이진 트리에서 n+1자리 만들고 그자리에 삽입할 원소 임시 저장) - 2단계 : 부모노드 크기 조건이 만족하도록 삽입 원소의 위치 찾기 ② 히프의 삭제 연산 : 히프에서는 루트 노드의 원소만 삭제 가능 - 1단계 : 루트 노드의 원소를 삭제하여 반환 - 2단계 : 원소의 개수가 n-1개로 줄었으므로 노드의 수가 n-..

1. 이진 탐색 트리의 탐색, 삽입, 삭제 연산 ① 이진 탐색 트리 - 이진 트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정의한 것 ② 이진 탐색 트리의 탐색 연산 ③ 이진 탐색 트리의 삽입 연산 - 탐색 연산 수행 : >>삽입할 원소와 같은 원소가 트리에 있으면 삽입 불가하므로 같은 원소가 트리에 있는지 탐색하여 확인 >>탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 됨. - 탐색 실패한 위치에 원소 삽입 ④ 이진 탐색 트리의 삭제 연산 - 탐색 연산 수행: >> 삭제할 노드의 위치를 알아야 하므로 트리 탐색 - 탐색 성공한 위치에 원소 삭제: >> 노드의 삭제 후에도 이진 탐색 트리 유지해야 하므로 삭제 노드의 경우에 대한 후속 처리(이진 탐색 트리의 재구성 작업)가 필요..

1. 경로의 존재 ① 경로의 존재 - 임의의 정점에서 다른 정점으로의 경로가 존재한다 : 직, 간접적인 경로 모두 의미 ② 도달행렬 - 방향 그래프에서 정점 간 경로의 존재 여부를 행렬로 표현한 것 - A*를 도달행렬이라고 하고 행렬 A에 대한 거듭제곱 - 부울 곱 연산, 합 - 부울 합 연산 - 각각의 정점에서 다른 정점으로가는 경로가 존재하는 지 여부를 알려줌. 2. 최단 경로 ① 최단 경로 - 빠른 길을 어떻게 찾을 것인가? -> 짧다는 것은 단지 물리적인 거리 뿐 아니라 시간 거리, 비용 거리 등 다양한 기준이 적용될 수도 있음. ② 최단 경로의 조건 - 간선 가중치가 있는 유향 그래프 - 무향 그래프는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있음 -> 즉 무향 간선(..