Computer Science/Data Structure10 [자료구조] 13장 Search 1. 탐색 : 여러 개의 자료 중에서 원하는 자료를 찾는 작업 2. Map dictionary : 키-값 쌍을 테이블에 저장 3. 순차 탐색 : 정렬 안된 배열을 처음부터 마지막까지 하나씩 검사 - 시간 복잡도: O(n) - 평균 비교 횟수: (n+1)/2 4. 이진 탐색 : 정렬된 배열 탐색에 적합. 탐색의 범위를 반으로 줄여가면서 탐색 진행. - 시간 복잡도: O(logn) 5. 색인 순차 탐색 : 인덱스 테이블을 사용. 모두 정렬되어 있어야함. - 시간 복잡도: O(m+n/m), m은 인덱스 테이블 크기, n은 주자료 크기 6. 보간 탐색 : 사전이나 전화번호부를 탐색하는 방법, 탐색키가 존재할 위치를 예측하여 탐색하는 방법 이진 탐색과 유사하지만, 보간 탐색은 불균등 분할해 탐색 - 시간 복잡도:.. 2023. 12. 17. [자료구조] 12장 Sort 1. 정렬 : 데이터를크기순으로 오름, 내림 차순으로 나열하는 것 - 정렬의 대상: 레코드 - 종류 단순하지만 비효율적인 방법: 삽입,선택, 버블 정렬 복잡하지만 효율적인 방법: 퀵, 힙, 합병, 기수 정렬 2. 선택 정렬 : 가장 작은 값과 정렬 안 된 값들 중 가장 앞에 있는 값을 교환 - 시간 복잡도: O(n^2) - 특징: 매우 간단. 비효율적. 안정성 만족 안함. 3. 삽입 정렬 정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정 - 시간 복잡도: O(n^2) - 특징: 많은 이동 필요. 안정됨. 대부분 정렬되어 있으면 효율적. 4. 버블 정렬 : 인접한 2개 레코드를 비교해 바꿈 - 시간 복잡도: O(n^2) - 특징: 많은 이동 필요. 5. 셸 정렬 : 삽입 정렬은 어느정도 정.. 2023. 12. 17. [자료구조] 11장 그래프 1. 그래프 - 오일러 정리: 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로가존재함. - 동일한 그래프? 배열로 정점의 집합과 간선의 집합을 나타냈을 떄 두 배열이 다른 그래프의 배열과 동일할 때. - 방향그래프, 무방향 그래프, 가중치 그래프, 부분 그래프 2. 그래프 용어 인접 정점 - 자신과 간선으로 직접 연결된 정점 차수 - 자신과 연결된 정점의 수 그래프의 경로 경로의 길이 - 경로를 구성하는데 사용된 간선의 수 단순 경로 - 경로 중에 반복 간선이 없는 경로 사이클 - 시작 정점과 종료 정점이 동일한 경로 연결 그래프 - 모든 정점쌍에 대한 경로 존재 트리 - 그래프의특수한 형태. 사이클이 없음 완전 그래 - 모든 정점이 연결되어 있는 그래프 3. 그래프 표현 방법1: 인접행렬 4. 그.. 2023. 12. 16. [자료구조] 9장 Priority Queue 1. Priority Queue : 우선순위가 높은 데이터가 먼저 나감. 배열/연결리스트/힙으로 구현 가능. 2. Heap 완전 이진 트리 최대 힙: 부모 노드의 키 값이 자식노드의 키값보다 크거나 같음 최소 힙: 부모 노드의 키 값이 자식노드의 키 값보다 작거나 같음 힙은 배열을 이용해 만들면 효율적. 완전 이진 트리 -> 각 노드에 번호를 붙임 -> 배열의 인덱스 3. Upheap(삽입) 새로운 요소가 들어오면 일단 마지막 노드에 이어서 삽입 삽입된 위치에서 루트까지의 경로에 잇는 노드들을 비교, 교환 키가 부모 노드보다 작거나 같으면 종료. O(logn) 4. Downheap(삭제) 루트 삭제. 루트에서부터 단말 노드까지의 노드들을 교환해 힙 성질 만족. O(logn) 5. 힙정렬 n개의 요소를 최.. 2023. 12. 16. [자료구조] 8장 BST 1. BST : 이진 트리 기반 효율적인 탐색 가능 2. 이진 탐색 트리 정의 : key(왼쪽 서브트리) = 루트 -> 오른쪽으로 순회하는 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있음. 3. 이진 탐색 트리의 탐색 연산 4. 이진 탐색 트리의 삽입 연산 : 탐색을 하다가 실패한 위치가 새로운 노드 삽입의 위치. 5. 이진 탐색 트리의 삭제 연산 case1) 단말 노드 삭제: 부모 노드 찾아서 연결 끊음. case2) 자식이 하나인 노드 삭제: 노드 삭제하고 서브트리를 부모 노드에 붙임. case3) 두 개의 자식을 가진 노드 삭제: 가장 비슷한 값을 가진 노드를 삭제 노드 위치로 가져옴. 6. 이진 탐색 트리의 성능 : 이진 탐색 트.. 2023. 12. 16. [자료구조] 4장 스택 4-1 스택 1. 스택이란 : 쌓아놓은 더미. → 후입 선출!(LIFO: Last In First Out): 가장 최근에 들어온 데이터가 가장 먼저 나감 2. 스택의 구조 : 스택의 상단(top), 스택의 하단: 불필요, 요소, 항목, 공백 상태, 포화 상태, 삽입, 삭제 3. 스택 추상 자료형(ADT) 데이터: 후입선출의 접근 방법을 유지하는 요소들의 모음 연산(7): ⊙ init(): 스택을 초기화. ⊙ is_empty(): 스택이 비어있으면 TRUE, 아니면 FALSE를 반환. ⊙ is_full(): 스택이 가득 차 있으면 TRUE, 아니면 FALSE를 반환. ⊙ size(): 스택 내의 모든요소들의 개수를 반환. ⊙ push(x): 주어진 요소 x를 스택의 맨 위에 추가. ⊙ pop(): 스택 맨.. 2023. 10. 16. [자료구조] 3장 Linked List 3-1 리스트 1. 리스트란 : 순서를 가진 항목들의 모임. 2. 리스트의 구조 : 선형의 자료구조(스택, 큐와 공통점). 임의의 위치에서도 삽입과 삭제가 가능함(스택, 큐와 차이점) 3. 리스트 ADT(추상 자료형) 데이터: 임의의 접근 방법을 제공하는 같은 타입 요소들의 순서 있는 모임 연산(9): ⊙ init(): 리스트 초기화. ⊙ insert(pos, item): pos 위치에 새로운 요소 item을 삽입. ⊙ delete(pos): pos 위치의 요소를 삭제. ⊙ get_entry(pos): pos 위치에 있는 요소 반환 ⊙ is_empty(): 리스트가 비어 있는지 검사 ⊙ is_full(): 리스트가 가득 차 있는지 검사. ⊙ find(item): 리스트 요소 item이 있는지 살핌. ⊙ .. 2023. 10. 15. [자료구조] 2장 자료구조 소개 2-1 자료구조 1. 자료구조 : 컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조 2. 추상화? : 어떤 시스템의 간략화 된 기술 또는 명세. 시스템의 핵심적인 구조나 동작에만 집중. 3. 자료형? : 데이터의 집합과 연산의 집합. 4. 추상 자료형(ADT: abstract data type) : 데이터 타입을 추상적으로 정의한 것. - 데이터나 연산이 무엇(what)인가를 정의. - 데이터나 연산을 어떻게(how) 구현할 것인지는 정의하지 않음 ▶ 추상 자료형을 프로그래밍 언어로 구현한 것이 자료구조!! - 추상 자료형의 데이터: 구조체 사용 - 추상 자료형의 연산: 함수 사용 2-2 알고리즘 1. 알고리즘 : 컴퓨터로 문제를 풀기위한 단계적인 절차. ▶ 알고리즘 + 자료구조 = 프로그램 2. 알고리.. 2023. 10. 15. [자료구조] 1장 C언어 리뷰 (2) 1. 세 개의 숫자 중에 가장 큰 수 찾기 – 세 개의 숫자를 키보드로 입력 받음 – 가장 큰 숫자를 찾아 화면으로 출력 : if문 사용 or 삼항 연산자 사 #include int main() { int a, b, c; int max; scanf("%d %d %d", &a, &b, &c); max = ((a>b) & (a>c)) ? a : ((b>a) & (b>c)) ? b : c; printf("%d", max); return 0; } 2. 입력받은 수를 역순으로 만들기 – 12345 → 54321 – while() 문장 사용 #include int main() { int N; int r = 0; scanf("%d", &N); while(N != 0){ r *= 10; r += N % 10; N /=.. 2023. 9. 10. [자료구조] 1장 C언어 리뷰 (1) 이번 학기도 자료구조를 듣게 되었다. 한동안 파이썬으로 코테를 공부하고, 스프링으로 자바를 공부해서 C언어를 까먹었다. 그래서 자료구조 수업을 본격적으로 들어가기 앞서 C언어를 간단히 공부하겠다. 이번 포스팅에서는 이론 공부를 하고, 다음 포스팅에서는 문제를 풀어보도록 하겠다. 알고 있는 내용은 생략하고 작성하겠다. 1-1 배열 1. 배열의 선언 : int A[6] 2. 메모리 접근 방식 : 직접 접근 방식(direct access).→ 항목 접근의 시간 복잡도가 O(1) cf. 연결리스트: 순차 접근 방식(direct access) → 항목 접근의 시간 복잡도 O(n) 3. 문자열 특징(3) : 문자열은 특별한 1차원 배열이다. : 포함 필수 : =, ==, < 등의 연산자를 사용할 수 없다. 4. 문.. 2023. 9. 10. 이전 1 다음
