본문 바로가기

프로그래밍 언어/자료구조 & 알고리즘13

자료구조 - 해싱 해싱(Hashing) 해싱이란? 해시 함수와 해시 테이블을 이용하여 데이터를 빠르게 저장하고 탐색하는 방법 데이터를 해시 테이블이라는 배열에 저장하고 데이터의 키 값으로 해시 함수를 통하여 테이블의 주소를 반환하여 원하는 데이터를 찾는 방식 해시 테이블 값의 연산에 의해 직접 접근 가능한 구조 해시 함수 해시 테이블에서 기 값을 주소로 변환하는데 사용되는 함수 계산이 빠르고 간단해야 하며, 다른 키 값이 같은 주소를 산출하는 경우가 적어야 함 해시 함수 종류 나눗셈법 중간 제곱법 폴딩법 기수 변환법 자리수 분석법 나눗셈법 키 값을 정수로 보고 이를 적당한 양의 정수(주소, 해시 테이블의 크기 등)로 나누어 그 나머지를 해시 주소로 하는 방법 h(k) = k mod N h(): 해시 함수 k: 키 값 N:.. 2021. 12. 1.
자료구조 - 탐색 탐색(Search) 탐색이란? 데이터의 집단 내에서 특정 데이터를 찾아내는 구조 탐색 알고리즘의 효율성은 탐색 집단의 구조가 어떻게 구성되어 있느냐에 따라 영향을 받음 컴퓨터가 가장 많이 하는 작업 중의 하나 탐색에서 사용되는 자료 구조 배열, 연결 리스트, 트리, 그래프 등 탐색 방법 순차 탐색 이진 탐색 보간 탐색 이진트리 탐색 순차 탐색 (Sequential Search) 정렬되지 않은 데이터의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾는 방법 탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법 크기가 적은 리스트에서는 효유류적이지만 크기가 큰 리스트에서는 매우 비효율적 장점 하나씩 비교하기 때문에 탐색에 용이 탐색 알고리즘이 간단함 단점 탐색 시간이 느리며 수행 시간 오래 걸림.. 2021. 12. 1.
자료구조 - 정렬 정렬(Sort) 정렬이란? 일련의 자료들을 자료 중에 포함된 몇 가지 항목을 우선 순서대로 지정하여 그 순서에 따라 모든 자료를 배열(나열)하는 방법 컴퓨터 공학분야에서 가장 기본적이고 중요한 알고리즘 중의 하나로 자료 탐색에 있어서 필수적 정렬 알고리즘의 종류 버블 정렬 (Bubble Sort) 선택 정렬 (Selection Sort) 삽입 정렬 (Insertion Sort) 쉘 정렬 (Shell Sort) 퀵 정렬 (Quick Sort) 2원 합병 정렬 (Two-way merge Sort) 기수 정렬 (Radix Sort) 힙 정렬 (Heap Sort) 정렬 알고리즘 단순하지만 비효율적인 방법: 삽입 정렬, 선택 정렬, 버블 정렬 복잡하지만 효율적인 정렬: 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬.. 2021. 12. 1.
자료구조 - 트리 컬렉션 프레임워크(Collection Framework) 트리 자료의 항목(node)들이 가지(edge)로 연결될 수 있게 자료가 구성되어 있는 구조 계층적 구조 부모-자식 관계의 노드로 구성 트리의 용어 노드(node): 트리를 구성하는 각 자료 항목: A, B, C, D, E, F, ... 근 노드(root node) 트리 구조를 시작하는 노드 제일 상위 계층에 존재하는 하나의 노드 A 자식 노드 임의의 노드에 연결된 다음 레벨의 노드들의 집합 D의 자식 노드는 H, I, J 부모 노드 임의의 노드에 연결된 상위 계층의 노드 A는 B, C, D의 부모 차수(degree) 노드에 연결된 자식 노드의 수 A의 차수: 3, B의 차수: 2, C의 차수: 1 레벨 root node 레벨을 0으로 하고 그 아.. 2021. 11. 30.
자료구조 - 연결리스트(1) 연결 리스트 자료구조(Data Structure) 자료구조 종류 순차 리스트 배열 / 행렬 / 레코드 스택 / 큐 / 데크 연결 리스트 단일 연결 리스트 원형 연결 리스트 이중 연결 리스트 트리 일반 트리 이진트리 선형 리스트 각 데이터가 배열과 같이 연속되는 기억 장소에 순차적으로 저장되는 자료 구조 1차원 배열과 비슷한 구조이지만, 원소의 개수가 유동적 원소를 나열한 순서가 원소들의 순서가 됨 원소들의 논리적인 순서와 메모리에 저장하는 물리적인 순서가 같은 구조로 되어 있음 순차 자료구조에는 원소들이 순서대로 연속 저장되어 있기 때문에 시작 위치와 원소의 길이를 알면 특정 원소의 위치를 알 수 있음 리스트에서 처리할 수 있는 연산 길이: 리스트의 길이를 구하는 연산 접근: 리스트의 내용을 조사하거나 변경하기 위해.. 2021. 11. 29.
자료구조 - 순차리스트(2) 큐(Queue), 데크(Deque) 자료구조(Data Structure) 자료구조 종류 순차 리스트 배열 / 행렬 / 레코드 스택 / 큐 / 데크 연결 리스트 단일 연결 리스트 원형 연결 리스트 이중 연결 리스트 트리 일반 트리 이진트리 순차 리스트 각 자료가 메모리 중에서 서로 이웃해 있는 구조 선형 구조라고도 함 메모리에 연속적으로 저장 종류 배열 / 행렬 / 레코드 스택 / 큐 / 데크 큐 (Queue) 선형 리스트 구조의 특별한 형태 기억 장소의 한쪽 끝에서 데이터의 입력이 이루어지고, 다른 한쪽 끝에서 출력이 이루어지는 형태 먼저 삽입한 데이터가 먼저 삭제되는 구조를 가짐 FIFO(First-In First-Out) / 선입선출의 형태 전위 포인터(front) 데이터가 삭제되는 끝을 가리키는 포인터 후위 포인터(rear) 데이터가.. 2021. 11. 29.
자료구조 - 순차리스트(1) 스택(Stack) 자료구조(Data Structure) 자료구조 종류 순차 리스트 배열 / 행렬 / 레코드 스택 / 큐 / 데크 연결리스트 단일 연결 리스트 원형 연결 리스트 이중 연결 리스트 트리 일반 트리 이진 트리 순차 리스트 각 자료가 메모리 중에서 서로 이웃해 있는 구조 선형 구조라고도 함 메모리에 연속적으로 저장 종류 배열 / 행렬 / 레코드 스택 / 큐 / 데크 배열 크기와 데이터형이 같으며 동일한 이름을 갖는 원소들의 연속적 저장공간 배열의 원소는 메모리 내에서 연속적으로 순서대로 저장 각 배열의 원소는 첨자(인덱스 [0]부터 시작)로 구별 레코드 서로 다른 데이터 형태와 크기로 구성되어 있는 데이터 구조 이질적 구조 ex) 어떤 사람에 관한 자료들인 이름, 주민등록번호, 주소 등과 같이 서로 관계있는 여러.. 2021. 11. 29.
알고리즘 설계 기법 - 동적 프로그래밍 기법 알고리즘 설계 기법 동적 프로그래밍 기법 (Dynamic programming) 분할 정복 기법과 유사하게 부분 문제의 해답을 이용하는 방식으로 문제를 해결하는 방식 주어진 문제를 여러 개의 소문제로 분할하여 문제를 해결 상향식 설계기법 작은 문제부터 먼저 해결한 후 그 결과를 큰 문제에서 활용함으로써 효율성을 높이는 방법 동적 프로그래밍 방식 적용 방법 분할 정복식 방법과 마찬가지로 문제를 나눈 후, 주어진 부분 문제들을 한 번 계산한 후에는 특정 장소에 저장 부분 문제의 해가 필요할 때 이를 다시 계산하지 않고, 이전에 저장해둔 결과를 이용 일반적으로 동적 프로그래밍에서 부분 문제의 값을 저장하는 장소는 배열 형태를 사용 피보나치 수열 계산 과정의 트리 중복 계산 발생 다시 계산하지 않고 한번 계산한.. 2021. 11. 29.
알고리즘 설계 기법 - Greedy 알고리즘/욕심쟁이 기법 알고리즘 설계기법 욕심쟁이 기법 (Greedy method) 최적 해답을 구성할 수 있는 집합을 만들기 위해 필요한 원소를 각 단계마다 하나씩 선택해 나가는 방법 선택을 하는 매 순간마다 현재 상태에서 가장 좋아 보이는 원소를 선택하는 전략 최적의 해를 찾는 전형적인 해결 방법 즉, 각 순간에 지역적으로 가장 좋아 보이는 선택이 보여서 전체적으로 가장 좋은 최종의 답에 이르는 문제가 많기 때문에 전략이라고 할 수 있음 이 기법은 모든 최적화 문제를 해결할 수는 없으나, 많은 경우의 문제에 쉽게 적용할 수 있는 기법 중 하나 욕심쟁이 기법 적용 예 배낭 채우기 문제 거스름돈 문제 최단 경로 문제(Dijkstra의 최단 경로 Algorithm) 최소 비용 신장 트리 Prim(프림)의 알고리즘 Krusckal.. 2021. 11. 29.

티스토리툴바