Algorithm9 [알고리즘] 초급~중급 난이도 알고리즘 기법 [초급] Greedy (탐욕법) 탐색기법 - 완전 탐색, DFS, BFS 동적 계획법 초급 (DP : Dynamic Programming) 큐, 스택 [중급] 그래프 이론 분할 정복 이분 탐색 동적 계획법 중급 (DP : Dynamic Programming) 최단거리 - 다익스트라, 벨만 포드, 플로이드 최소 스패닝 트리 구간 트리(세그먼트 트릐, 인덱스 트리, 팬윅트리) LCA 비트마스크 서로소 집합 문자열 2021. 8. 23. [정렬] 다양한 정렬 방식 (삽입/쉘/선택/버블/퀵/힙/합병/기수) 삽입 정렬 (Insertion Sort) - 가장 간단한 정렬 방식 - 평균 수행 시간 복잡도 = 최악 수행 시간 복잡도 = O(n^2) [수행 방법] (1회전) 두 번째 값과 첫 번째 값을 비교해 순서대로 나열 (2회전) 세 번째 값을 첫 번째, 두 번째 값과 비교해 순서대로 나열 ... (n회전) n-1번째 값을 앞의 값들과 모두 비교하여 알맞은 순서에 삽입하여 정렬 [예제] 초기 상태 : 8 5 6 2 4 1회전 : 8 5 6 2 4 → 5 8 6 2 4 2회전 : 5 8 6 2 4 → 5 6 8 2 4 3회전 : 5 6 8 2 4 → 2 5 6 8 4 4회전 : 2 5 6 8 4 → 2 4 5 6 8 쉘 정렬 (Shell Sort) - 삽입 정렬을 확장한 개념 - 입력파일을 어떤 매개변수(h)의 .. 2021. 7. 14. [자료구조] 비선형 자료구조 - 트리 트리의 정의 - 정점(Node, 노드),과 선분(Branch, 가지)을 이용하여 나타냄 - 사이클을 이루지 않도록 구성된 그래프의 한 형태 - 노드(Node) : 하나의 기억 공간 - 링크(Link) : 노드와 노드를 연결하는 선 - 가족의 족보, 조직도 등의 표현에 적합 트리 관련 용어 - 노드(Node) : 트리의 기본 요소로서 자료 항목과 자른 항목에 대한 가지를 합친 것 - 근 노드(Root Node) : 트리의 맨 위에 있는 노드 - 디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지의 수 - 단말 노드(Terminal Node) : 자식이 하나도 없는 노드 ( = 차수가 0인 노드) - 자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들 - 부모 노드(Parent .. 2021. 7. 14. [자료구조] 비선형 자료구조 - 그래프 그래프의 정의 및 특징 - 정점 V(Vertex)와 간선 E(Edge)의 두 집합으로 이루어진 자료구조 - 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분 - 통신망, 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향선분 해법 등에 응용 - 무방향 그래프의 최대 간선 수 = n(n-1) - 방향 그래프의 최대 간선 수 = n(n-1)/2 2021. 7. 14. [자료구조] 선형 자료구조 - 큐 (Queue) 정의 및 특징 - 리스트의 한쪽에서는 삽입 작업이, 다른 한쪽에서는 삭제 작업이 이루어지는 자료구조 - 선입선출 (FIFO; First In First Out) : 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 방식 - 운영체제의 작업 스케줄링에 사용 - 시작과 끝을 표시하는 두 포인터 존재 (프런트 포인터, 리어 포인터) - 프런트 포인터 (F, Front) : 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터. 삭제 작업에 사용 - 리어 포인터 (R, Rear) : 가장 마지막에 삽입된 자료가 위치하는 기억 공간을 가리키는 포인터. 삽입 작업에 사용 2021. 7. 14. [자료구조] 선형 자료구조 - 스택 (Stack) 정의 및 특징 - 리스트의 한쪽 끝으로만 자료의 삽입/삭제가 이루어지는 자료구조 - 후입선출 (LIFO; Last In First Out) : 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 방식으로 자료를 처리 - 오버플로 (Underflow) : 스택의 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되는 경우 발생 - 언더플로 (Overflow) : 더 이상 삭제할 데이터가 없는 상태에서 데이터 삭제를 시도하는 경우 발생 - TOP : 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소 - Bottom : 스택의 가장 밑바닥 2021. 7. 14. [자료구조] 선형 자료구조 - 배열 정의 및 특징 - 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 가지는 자료구조 - 정적인 자료구조 - 기억 장소의 추가가 어려움 - 데이터 삭제 시 데이터가 저장되어 있던 기억 장소는 빈 공간으로 남아 메모리 낭비 발생 - 첨자를 이용하여 데이터에 접근 - 반복적인 데이터 처리 작업에 적합 - 데이터마다 동일한 이름의 변수를 사용하여 처리가 간편 - 사용한 첨자의 개수에 따라 n차원 배열이라고 부름 2021. 7. 14. [자료구조] 선형 자료구조 - 선형 리스트 (연속 리스트 & 연결리스트) List : 나열하다 리스트란? 리스트(List) : 나열한 목록 선형 리스트(Linear List) : 원소들이 일정한 순서에 의해 나열된 자료구조 리스트 표현 방법 리스트 이름 = (원소1, 원소2, ..., 원소n) 종류 연속 리스트 - 배열을 이용 - 기억 장소를 연속적으로 배정받음 → 기억 장소 이용 효율 = 밀도 1로 가장 좋음 - 중간에 데이터를 삽입하는 경우, 연속된 빈 공간 생성을 위해 삽입/삭제 시 자료의 물리적인 이동 필요 - 삽입/삭제 연산이 많이 필요한 문제에 적용할 경우 비효율적 - 원소들의 순서를 따로 표시할 필요 없이 간단히 구성 가능 - 인덱스를 사용하여 특정 원소를 쉽게 액세스 가능 - 시작 위치와 원소의 크기를 알고 있다면 특정 원소의 위치 알아낼 수 있음 연결 리스트 .. 2021. 7. 11. [자료구조] 자료구조의 정의 및 분류 자료구조 : 일련의 자료들을 조직하고 구조화(정리)하는 것 : 대량의 데이터를 효율적으로 관리할 수 있는 데이터 구조 및 그것과 관련된 연산 : 자료구조에 따라 데이터를 효율적으로 처리하기 위한 코드가 달라진다. 즉, 어떤 자료구조와 어떤 알고리즘을 사용하는지에 따라 프로그램의 성능이 좌우된다. 자료구조의 형태에 따른 분류 선형 구조 : 자료 간의 연결 관계가 1:1 관계를 갖는 구조 비선형 구조 : 계층 구조나 망 구조를 갖는 자료구조 파일 구조 : 서로 관련 있는 필드들로 구성된 레코드의 집합인 파일에 대한 자료구조 더보기 참고 포스팅 https://devraphy.tistory.com/31?category=928262 Data Structure - Array * 해당 포스팅은 파이썬을 이용한 알고리.. 2021. 7. 11. 이전 1 다음
