hyejun CSlog

14.1 해싱이란?선형탐색이나 이진탐색은 모두 키를 저장된 키값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근-> 최대 가능한 시간 복잡도가 O(로그n)에 그친다. 어떤 응용에서는 더 빠른 탐색 알고리즘 요구해싱은 O(1)의 시간 안에 탐색 끝마칠수도 있다.키에 산술적인 연산 적용 -> 항목이 저장돼있는 테이블의 주소를 계산한여 항목에 접근. 해시테이블: 키에 대한 연산에 의해 직접 접근 가능한 구조해싱: 해시테이블 이용한 탐색14.2 추상자료형 사전사전 : (키,값)쌍의 집합. 키와 관련된 값을 동시에 저장하는 자료구조. (키,값)쌍을 저장할 수도 있고 삭제할수도 있으며 키를 가지고 값을 검색할 수 있다. map이나 table로 불리기도 한다.키 : 사전의 단어처럼 항목과 항목을 구별시켜주는 것..

*시험 : 교재문제+ 교수님이 올려주신 기출문제13.1 탐색이란? 탐색: 기본적으로 여러 개의 자료 중 원하는 자료를 찾는 작업- 탐색키와 데이터로 이루어진 여러 개의 항목 중 원하는 탐색키 갖고 있는 항목 찾는 것사용되는 자료구조 : 배열, 연결리스트, 트리, 그래프 .......가장 기초적인 방법: 배열 사용하여 자료 저장하고 찾기, but 탐색성능을 향상하고자 한다: 이진트리처럼 보다 진보된 방법으로 자료를 저장하고 찾아야 한다.탐색의 단위 : 항목(숫자 or 구조체...) - 항목과 항목을 구별시켜주는 탐색키 존재 13.2 정렬되지 않은 배열에서의 탐색순차탐색 : 탐색 방법 중 가장 간단하고 직접적인 탐색방법. 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목 찾기탐색..

12.1 정렬이란?정렬: 물건을 크기순으로 오름차순이나 내림차순으로 나열하는 것정렬시켜야 될 대상: 레코드, 레코드는 필드라는 단위로 나뉘어진다.키: 레코드와 레코드를 식별해주는 역할을 하는 필드 = 레코드들을 키값의 순서로 재배열최적 알고리즘은 존재하지 않으므로 이들 방법 중에서 현재 환경에서 가장 효율적인 정렬 알고리즘을 선택해야 한다.효율성의 기준: 정렬 위해 필요한 비교연산의 횟수와 이동연산의 횟수(빅오표기법 이용)횟수는 자료의 초기화 여부에 의존적, 이동횟수와 비교횟수가 서로 비례하지 x숫자와 숫자 비교는 시간 별로 안 걸림, 문자열과 문자열 비교하는 것은 상당히 시간 걸림, 숫자이동보다 큰 구조체 이동하려면 많은 시간 걸림 > 잘 맞춰서 적절한 정렬 알고리즘 선택해야 함.정렬 알고리즘의 효율성..

11.1 최소 비용 신장 트리신장트리: 그래프내 모든 정점을 포함하는 트리트리의 특수한 형태 : 모든 정점 연결, 사이클 포함 x그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결. 하나의 그래프에는 많은 신장트리 존재.깊이 우선이나 너비 우선탐색 때 사용한 간선들 표시하면 신장트리 만들 수 있음.그래프의 최소연결부분 그래프(간선의 수가 가장 적음)n개의 정점 갖는 그래프는 최소 (n-1)개 간선 가져야 함,(n-1)의 간선으로 연결돼있으면 필연적으로 트리형태>신장트리통신네트워크 구축에 많이 사용최소비용신장트리네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결신장트리 중 사용된 간선들의 가중치 합이 최소.각 링크의 구축 비용은 똑같지 x -> 각 링크(간선)에 비용 붙여서 링..

10.1 그래프란?그래프: 객체사이 연결관계 표현하는 자료구조 (ex. 지하철노선도), 선형리스트나 트리(트리도 그래프의 종류이긴 함)의 구조보다 복잡. 인접행렬이나 인접리스트로 메모리에 표현되고 처리될 수 있음.  10.2 그래프의 정의와 용어정점과 간선들의 유한집합수학적으로는 G=(V,E)와 같이 표시.V(G)는 그래프 G의 정점들의 집합, E(G)는 그래프 G의 간선들의 집합정점 vertex (=노드 node) : 여러가지 특성을 가질 수 있는 객체,간선 edge (링크 link): 이러한 정점들 간 관계  무방향 그래프와 방향 그래프무방향그래프 : 간선을 통해서 양방향으로 갈 수 있음을 나타냄, (A,B)=(B,A) 방향그래프: 간선에 방향성 존재. 간선을 통하여 한쪽 방향으로만 갈 수 있음을 나..

9.1 우선순위 큐 추상 데이터 타입[우선순위 큐] 데이터들이 우선순위 갖고있고 우선순위 높은 데이터가 먼저 나간다.0개 이상의 요소 모임(각 요소는 우선순위값 갖고 있음)최소 우선순위 큐: 가장 우선순위 낮은 요소가 먼저 삭제최대 우선순위 큐: 가장 우선순위 높은 요소가 먼저 삭제  9.2 우선순위 큐의 구현방법1. 배열 사용정렬 안 된 배열 사용:삽입 - 배열의 맨 끝에 새로운 요소 추가> 시간복잡도 O(1)삭제 - 가장 우선순위가 높은 요소를 찾아야 한다. > 정렬 안 돼 있으므로 처음부터 끝까지 모든요소 스캔 > 시간복잡도 O(n)+요소 삭제된 다음 뒤에 있는 요소를 앞으로 이동시켜야 한다.정렬된 배열 사용: 삽입- 위치 찾기 위해 순차탐색, 이진탐색 이용> 삽입위치 뒤의 요소 이동시켜서 빈자리 ..

8.1 트리의 개념 트리: 계층적인 구조를 나타내는 자료구조(계층적인 구조)선형자료구조(리스트, 스택, 큐), 한 개 이상의 노드로 이루어진 유한 집합 노드(node): 트리의 구성요소에 해당하는 A, B, C, D, E , F, G, H, J  A: 루트/ 서브트리에서는 B,C,D가 루트연결선: 간선(edge)A는 B의 부모노드, B는 A의 자식노드, B와C와D는 형제관계조상노드: 임의의 노드 상위에 연결되어 뻗쳐나간 모든 노드 후손노드: 임의의 노드 하위로 연결되어 뻗쳐나간 모든 노드단말노드: 자식노드가 없는 노드 비단말노드노드 차수: 어떤 노드가 갖고 있는 자식노드의 개수트리 차수: 트리가 갖고있는 노드의 차수 중 가장 큰 값트리 레벨: 트리의 각층에 번호 매기기(루트의 레벨이 1, 한 층씩 내려갈..

7.1 원형 연결 리스트원형 연결 리스트 : 마지막 노드가 첫 번째 노드 가리키는 리스트(마지막 노드의 링크필드가 null이 아닌 첫번째 노드 주소가 되는 리스트) 장점: 하나의 노드에서 다른 모든 노드로의 접근 가능 - 링크 계속 따라가면 결국 모든 노드 거쳐서 자기 자신으로 되돌아온다. ->노드 삽입,삭제가 단순 연결리스트보다 용이.(삭제나 삽입시 항상 선행노드 가리키는 포인터 필요) 특히 유용한 경우 : 리스트의 끝에 노드 삽입하는 연산이 단순 연결리스트보다 효율적. (단순 연결리스트에서 리스트 끝에 노드 추가하려면 첫 번째 노드에서부터 링크를 따라서 노드의 개수만큼 진행하여 마지막 노드까지 가야함.) 원형연결리스트는 원칙적으로 헤드 포인터만 있으면 된다.   원형리스트의 처음에 삽입 : 새로운 노..

6.1 리스트 추상 데이터 타입 리스트: 순서 또는 위치를 가지는 항목들이 차례대로 저장 (스택과 큐도 리스트의 일종)                                              ㄴ집합과는 다름(집합은 항목간 순서가 없기 때문에)                                                                                                       ㄴ삽입, 삭제, 탐색연산리스트 ADT 구현:  배열(더 간단)과 연결리스트 통해 가능 BUT 크기 고정. 포인터 이용하여  만들수도 있음 배열을 사용한 리스트 구현의 장단점장점: 구현 간단, 속도 빠름단점: 리스트 크기 고정, 동적으로 크기 늘리고 줄이기 힘듦, 남은 공간 없으..

5.1 큐 추상 데이터 타입-먼저 들어온 데이터가 먼저 나가는 구조(선입선출, FIFO) : 뒤에서 새로운 데이터 추가, 앞에서 데이터 하나씩 삭제. *스택은 삽입삭제가 같은 곳에서 일어나지만 큐는 다른 쪽에서 일어남 삽입삭제에 쓰이는 변수: 스택에서는 top이라는 변수 1개 존재, 큐에서는 삽입-rear, 삭제-front 사용 (배열과 연결리스트로 구현) 5.2 선형큐ex. 1차원 배열 쓰는 방법 : (정수저장큐 만든다 가정) 먼저 정수 1차원 배열 정의 - > 삽입, 삭제 위한 변수 front와 rear 만듦ㄴ front 와 rear의 초기값 : -1 (같음) . [실행] 데이터 증가> rear 하나 증가>그 위치에 데이터 저장 삭제할 때도 front 하나 증가> front가 가리키는 위치에 있는 데..