728x90 Computer Science/Algorithm9 [Algorithm] A* 알고리즘 ■ 들어가기 전 BFS의 두 가지 문제 중 가장 먼저 발견한 노드들을 방문한다는 한계점을 보완하기 위해 (1) 가중치 그래프(Weighted Graph)와 (2) 우선순위큐 (Priority Queue)를 사용한 다익스트라(Dijikstra) 알고리즘이 탄생했다. https://yjhdevelopdiary.tistory.com/196 [Algorithm] 다익스트라(Dijikstra) 알고리즘 ■ 배경 그래프의 탐색 알고리즘 중 BFS가 가볍고 구현하기 쉽다는 것을 알 수 있었다. 하지만 BFS의 단점은 아래 두 가지의 단점이 있다. (1) 목적지를 모른다. 그러므로 접근 가능한 모든 정점을 yjhdevelopdiary.tistory.com 하지만 다익스트라도 또 다른 BFS의 한계점은 보완하지 못했는데.. 2024. 3. 29. [Algorithm] 다익스트라(Dijikstra) 알고리즘 ■ 배경 그래프의 탐색 알고리즘 중 BFS가 가볍고 구현하기 쉽다는 것을 알 수 있었다. 하지만 BFS의 단점은 아래 두 가지의 단점이 있다. (1) 목적지를 모른다. 그러므로 접근 가능한 모든 정점을 탐색한다. (2) 가장 먼저 발견한(Discovered) 정점들을 방문 예약한다. 다익스트라 알고리즘은 위에서 (2) 문제를 해결하기 위해 고안된 알고리즘이다. ■ 특징 먼저 가중치 그래프를 활용하고 일반적인 큐(Queue)를 사용하는 BFS와 달리 우선순위 큐(Priority Queue)를 사용한다. (+)===== 우선 순위 큐는 아래 포스팅에 서술 및 구현해봤었다. https://yjhdevelopdiary.tistory.com/193 [자료구조] 우선 순위 큐 (Priority Queue) ■ 이론.. 2024. 3. 25. [Algorithm] BFS, DFS ■ 탐색 알고리즘 BFS, DFS는 그래프를 탐색할 때 사용하는 대표적인 탐색 알고리즘이다. 그래프는 이전 포스팅에서 정리해봤다. https://yjhdevelopdiary.tistory.com/194 [자료구조] 그래프 (Graph) ■ 의의 현실 세계의 사물이나 추상적인 개념 간의 '연결 관계'를 표현 트리와 굉장히 유사한데 트리보다 약간 넓은 개념으로 보면 됨. 트리가 약간 그래프의 일종이라고 보는게 좀 더 정확할듯. yjhdevelopdiary.tistory.com ■ DFS (깊이 우선 탐색; Depth First Search) 시작점 기준 뎁스 가장 끝 부분까지 깊이 파고들어서 정보를 추출해주는 알고리즘이다. 막다른 길을 만날 때 까지 뎁스를 늘려 계속 파고드는 원리이다. [구현 방법] (1).. 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. 이전 1 다음 728x90
