[자료구조]

자료구조란 : 자료를 구조화 시키는것 ex) 스택, 큐, 링크드리스트, 트리, 그래프 등등알고리즘이란 : 입력에 맞추어서 어떤 문제를 처리에 맞게 해결하려는 과정(문제를 풀기 위한 단계적인 과정)알고리즘의 성능 분석clock 함수로 호출 프로세서에 의하여 사용된 CPU

순환이란어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법장점 : 알고리즘을 훨씬 명확하고 간결하게 나타냄팩토리얼메모리 생성 순서와 죽는 순서는 반대시스템 스택의 변화f(3) -> f(2)호출 -> f(1)호출 -> 1반환 -> 2x1반환 -

스택 : First in Last out 처음에 들어가서 마지막에 나온다. 스택을 구현하기 전에 추상 자료형으로 정의해 보자. 추상자료형 객체 : 0개 이상의 데이터를 가지는 유한 선형 리스트 연산 : 스택의 구현 먼저 스택에서 가장 최근에 입력되었던 자료

괄호검사 알고리즘 프로그램에서 괄호들은 항상 쌍이 되게끔 사용되어야한다. [], (), {} .. 조건1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다. 조건2. 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다. 조건3. 서로 다른 종류

큐 : First-In Fisrt-Out : 처음 들어온 데이타가 처음으로 나간다. 큐에서 삽입이 일어나는 곳 : 후단(rear) 큐에서 삭제가 일어나는 곳 : 전단(front) > 큐 추상 자료형 객체: 0개 이상의 요소들로 구성된 선형 리스트 연산:

은행 서비스 시뮬레이션 프로그램 큐 데이터 원소를 고객 정보 구조체로 생성하고 큐 함수들을 가져다가 main함수만 바꿔주면 된다. 1.주어진 시간동안 고객은 랜덤한 간격으로 큐에 들어온다. 2.고객들의 서비스 시간도 한계값 안에서 랜덤하게 결정된다. 3.한 고객의

리스트 : 자료를 정리하는 방법 중의 하나 ex) 오늘 해야 할 일: (청소, 쇼핑, 영화관람) 버킷 리스트 : (세계여행, 영어 마스터, 마라톤..) 요일들 : (일, 월, 화, 수 ..) 배열로 구현된 리스트 장점: 구현이 간단하고 속도가 빠르다. 단점 :

원형 연결 리스트 : 마지막 노드가 첫 번째 노드를 가리키는 리스트 단순 연결 리스트에서는* 마지막 노드가 NULL이었지만 원형에서는 _마지막 노드의 링크가 첫 번째 노드 주소를 가르키*_면 된다. > 장점 : 하나의 노드에서 다른 모든 노드로의 접근이 가능하다.

정렬 : 물건을 크기순으로 오름차순, 내림차순으로 나열하는 것을 의미 ex) 책 제목순, 저자순, 발간연도수 사람 나이, 키, 이름 인터넷 제품 가격, 인기순 등등 보통 정렬시켜아 될 대상은 레코드(필드들을 합친것) 하나의 레코드 = 이름 + 학번 + 주

쉘 정렬 : 삽입 정렬 보안 정렬 장점 : 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 삽입 정렬은 한 번에 한 칸씩만 이동가능한 반면에 쉘 정렬은 더 큰 거리를 이동할 수 있다. 따라서 교환될 때 최종 위치에 더 가까이 있을 가능성이 높아진다. 이론

트리 자료들이 계층적으로 나열 되어 있는 구조 트리 용어 --> 트리 용어 이진 트리 : 모든 노드가 2개의 서브 트리를 가지고 있는 트리 이진 트리의 모든 노드는 차수가 2개 이하이다. 즉 자식 노드의 개수가 2 이하이다(공집합도 포함). 반면 일반 트리는

이진 탐색 트리 : 이진 트리 기반의 탐색을 위한 자료 구조 정의 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트 키보다 작다. 오른쪽 서브 트리의 키들은 루트의 키보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트

우선순위 큐 : 우선 순위의 개념을 큐에 도입한 자료구조 우선순위 큐의 응용 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석적인 계산 우선순위 큐의 구현 방법 배열을 사용하는 방법 정렬이 안된 배열 : 삽입 배열의 맨

그래프란.. 객체 사이의 연결 관계를 표현할 수 있는 자료구조다. 도로 미로 선수과목 그래프 정의와 용어 정의 : 정점과 간선들의 유한 집합이다. 정점 : 여러 가지 특성을 가질 수 잇는 객체 -> 노드 간선 : 이러한 정점들 간의 관계 -> 링크

신장 트리 : 그래프내의 모든 정점을 포함하는 트리다.모든 정점들이 연결되어 있어야 하고 , 사이클을 포함해서는 안 된다.따라서 하나의 그래프에는 많은 신장 트리가 존재 가능하다.정점의 개수가 n개라면 간선의 개수는 n-1개최소 비용 신장 트리(MST : minimum

탐색이란 ... 탐색키 : 항목과 항목을 구별시켜주는 키 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는것!!! 정렬되지 않은 배열에서의 탐색 순차탐색 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는

선형탐색, 이진 탐색은 모두 키값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근한다. 이런 방법들은 최대 가능한 시간 복잡도가 O(logn)에 그친다. 그렇다면 O(1)만큼 더 빠른 검색,탐색 방법은 없을까? 해싱 : 키에 산술적인 연산을 적용하여 항목이 저장