Computer Science28 [자료구조] 그래프 (Graph) ■ 의의 현실 세계의 사물이나 추상적인 개념 간의 '연결 관계'를 표현 트리와 굉장히 유사한데 트리보다 약간 넓은 개념으로 보면 됨. 트리가 약간 그래프의 일종이라고 보는게 좀 더 정확할듯. ■ 구성 (1) 정점 (Vertex) : 데이터를 표현 (사물, 개념 등) (2) 간선 (Edge) : 정점들을 연결하는데 사용 [사용 예시] 1. 소셜 네트워크 관계도 2. 지하철 노선도 3. 최적 길 판단 4. 다수 간의 호감도 등 ■ 종류 (1) 가중치 그래프 (Weighted Graph) 정점과 정점 사이를 잇는 간선에 가중치(비용)가 주어진 그래프를 뜻한다. (2) 방향 그래프 (Directed Graph) 정점과 정점 사이를 잇는 간선에 방향이 주어진 그래프를 뜻한다. ■ 표현 방법 (1) 인접 리스트 :.. 2024. 3. 25. [자료구조] 우선 순위 큐 (Priority Queue) ■ 이론 우선 순위 큐는 힙 트리(Heap Tree)의 구조를 갖는다. 최적 조건에 해당하는 값을 한 번에 구하고 싶을 때 유용한 자료구조이다. 연결리스트나 벡터 같은 경우 최대값 최소값을 찾으려면 O(n)만큼 선회하며 모든 값을 비교해줘야 도출할 수 있다. 하지만 우선순위큐는 힙트리의 구조로인하여 완전이진트리의 형태를 띄고 있다. 데이터를 삭제 및 추가하는 과정에서 대소관계를 비교하며 노드를 이동시키는 연산이 트리의 높이(logN)만큼 발생하므로 O(logN) 정도의 시간복잡도로 수행된다. [힙트리 설명 및 힙 정렬 알고리즘은 아래 포스팅에서 이전에 C#으로 구현해봤었다.] https://yjhdevelopdiary.tistory.com/172 [Alogrithm] 히프, 기수, 계수 정렬, 알고리즘 .. 2024. 3. 25. [Alogrithm] 히프, 기수, 계수 정렬, 알고리즘 비교표 ■ 히프 정렬 (Heap Sort) 1. 히프(heap) 자료구조를 사용하는 정렬 알고리즘임. 2. 히프는 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조이며 완전 이진 트리이다. 3. 최대힙 혹은 최소 힙에서 삽입, 삭제 연산에 내포되어있는 정렬 알고리즘들이 히프 정렬이다. * 완전이진트리 : 루트로부터 자식노드가 두 개씩 있는데 마지막 레벨의 노드들이 왼쪽부터 오른쪽으로 채워져있는 트리 (※ 마지막 바로 위 레벨 노드들은 다 꽉채워져있고 마지막 레벨의 노드들도 빈틈 없이 왼쪽부터 오른쪽 순서대로 채워져있어야함) [히프 정렬 과정] 1. 정렬할 데이터들을 먼저 히프로 삽입해야 함 2. 그런 다음 루트 노드들 하나씩 삭제하여 꺼내면 히프에 있는 데이터들이 순서대로 나오게 되는데 이 순서대로 나열한 것이 .. 2024. 2. 7. [Algorithm] 셸, 병합, 퀵 정렬 ■ 셸 정렬 (Shell Sort) 삽입 정렬을 보완한 알고리즘. Donald L. Shell이란 사람이 제안한 방법이라 셸 정렬임. [삽입 정렬의 문제점] 1. 데이터들이 삽입될 때 이웃한 위치로만 이동하는 것 2. 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있음 [특징] 1. 삽입 정렬의 확장된 개념. 전체 데이터를 한꺼번에 정렬하는 것이 아니라 매개변수를 설정한 후 이 매개변수만큼 떨어져 있는 데이터들을 모아 부분 리스트를 만든 다음 그 매개변수를 줄여가면서 정렬하는 방식 2. 일정한 간격(gap)만큼 떨어져있는 데이터들끼리 부분 리스트를 구성하고 각 부분 리스트에 있는 데이터들을 삽입 정렬하는 작업을 반복 3. 큰 간격에서부터 시작하여 각 .. 2024. 2. 7. [Algorithm] 선택 정렬, 버블 정렬, 삽입 정렬 ■ 선택 정렬 (Selection Sort) 정렬되지 않은 여러 데이터들 중에 '가장 작은 값'을 찾아 가장 앞의 데이터와 교환하는 작업을 반복하여 정렬 정렬되지 않은 전체 데이터 중에서 해당 위치에 맞는 데이터를 선택하여 위치를 교환 [구현] [시간 복잡도] 1. 선택 정렬의 시간 복잡도는 O(n^2) 2. 입력이 거의 정렬되어 있든지, 역순으로 정렬되어 있든지, 랜덤하게 되어 있든지를 구분하지 않고 항상 일정한 시간 복잡도를 가짐 (입력에 민감하지 않은 알고리즘) 3. 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적음 ■ 버블 정렬 (Bubble Sort) 첫번째 값부터 시작해서 바로 앞뒤 데이터를 비교하여 큰 것은 뒤로 보내는 방법을 사용하는 정렬 수가 정렬되는 모습이 물속의 거품(Bubbl.. 2024. 2. 7. [Algorithm] 정렬 알고리즘,내부정렬, 외부정렬 ■ 정렬 알고리즘 여러 알고리즘 중 가장 기본이 되는 알고리즘 [특징] 1. 대부분의 정렬 알고리즘은 키값을 비교하는 비교 연산과 자료의 위치를 바꾸는 이동 연산으로 이루어짐 2. 비교 연산의 횟수와 이동 연산의 횟수로 정렬의 효율성을 판단 3. 정렬을 수행해야 하는 데이터의 크기가 크면 이동 연산이 적을수록 좋음 (데이터의 크기가 크면 그만큼 이동해야 하는 데이터의 크기가 증가하여 이동 연산을 수행하는데 더 많은 시간이 필요) 4. 연산의 횟수가 같더라도 비교 연산이 많은 알고리즘이 이동 연산이 많은 알고리즘보다 성능이 더 우수 5. 컴퓨터 메모리 내부에서 정렬하는 '내부 정렬 알고리즘'과 보조기억 장치에서 정렬하는 '외부 정렬 알고리즘'이 있음 [시간복잡도] 1. 대부분 O(n^2)과 O(nlogn).. 2024. 2. 7. [Algorithm] 완전 탐색 (Exaustive Search) ■ 완전 탐색 (Exaustive Search) 고지식한 방법 (Brute-Force)의 의미를 갖고 있음. - 모든 경우의 수를 나열한 후 그 중에서 최선의 해결책을 찾는 방법으로 가장 좋은 결과를 확실히 추출할 수 있음 - brute-force는 문제를 해결하기 위한 간단하고 쉬운 접근법 [개념] 1. 완전탐색은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 2. brute-force 혹은 generate-and-test 기법이라고도 부름 [특징] 1. 모든 경우의 수를 테스트한 후 최종 해법을 도출 2. 문제에 포함된 자료 (요소, 인스턴스)의 크기가 작다면 유용 3. 학술적 또는 교육적 목적을 위해 알고리즘의 효율성을 판단하기 위한 척도로 사용됨 4. brute-for.. 2024. 2. 7. [Algorithm] 분석 종류, 설계 기법, 표기법 ■ 알고리즘의 조건 조건 설명 입력 0개 이상의 데이터 입력이 있어야한다. 출력 적어도 하나 이상의 결과를 출력해야한다. 명확성 각 단계와 명령은 모호하지 않고 명확해야한다. 유한성 유한한 단계를 거친 후, 반드시 종료해야한다. 유효성 각 명령어들은 실행 가능해야 한다. ■ 알고리즘의 표현 방법 1. 자연어 2. 순서도 (Flow Chart) 3. 의사코드 (Pseudo Code) 4. 프로그래밍 언어 (C, C#, C++ ...etc) ■ 알고리즘 분석 종류 종류 설명 최악의 경우를 분석 (★★) 어떤 입력이 주어지더라도 알고리즘의 수행 시간이 이 이상은 넘지 않는다는 '상한(Upper-Bound)'의 의미. * 수행시간이 가장 늦은 경우를 뜻함 평균의 경우를 분석 입력의 확률 분포를 가정하여 분석. .. 2024. 2. 7. [자료구조] 순환적, 반복적 피보나치 수열 구현 및 성능 비교, 순환문과 반복문 비교, 하노이탑 ■ 구현 ■ Main ■ 성능 비교 이로 인하여 피보나치 수열은 Iterative 기법이 더욱 효과적인 것을 알 수 있었다. ■ 순환 (Recursive) vs 반복 (Iterative) 순환 (Recursive) 반복 (Iterative) [장점] 가독성 증대 및 코딩도 간단해짐 [단점] 함수 호출의 오버헤드 발생으로 수행속도가 느림 (스택 저장 공간에 함수 파라미터 스택을 저장할 기억 공간이 더필요하고 이와 관련된 작업을 함에 있어서 오버헤드가 발생함) [특징] 1. 어떤 경우는 순환이 아니면 프로그램 구현이 어려운 경우가 있음 2. 시간 복잡도 (Time Complexity)는 순환 호출 1번에 1번의 곱셈을 수행하므로 n번 발생시 O(n)이다. [장점] 수행속도가 빠름 [단점] 가독성을 악화시킬 .. 2024. 2. 3. 이전 1 2 3 4 다음
