티스토리

동윤의 블로그

검색하기

블로그 홈

동윤의 블로그

dongyoonq.tistory.com/m

동윤큐 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

최단 거리 알고리즘 (다익스트라, A*) 다익스트라 알고리즘 그래프에서 한 정점으로부터 모든 정점으로의 최단거리의 경로를 구하는 알고리즘 1. 지금 연결되어 있는 노드 중에서 탐색을 안한 노드중 가장 가까운 노드를 선정한다. 2. 직접 연결된 거리보다 거쳐서 더 짧아지면 갱신한다. 3. 이 과정을 반복하다보면 최단 경로가 나온다. 예시 더보기 1번 정점에서 시작해서 모든 정점들까지의 최단 경로를 구한다고 가정해 보겠습니다. 정점들 간의 간선의 가중치는 그림과 같고, distance 배열은 1번 정점에서 특정 정점까지의 최단 경로 길이를 표시해 놓습니다. 단, 초기에는 최단 경로를 구하지 않은 상태이므로 무한대(아주 큰 값)로 표시합니다. 1번 정점에서 인접한 정점들을 살펴봅니다. 처음에는 모두 무한대 값들이었으므로, 1번 — 특정 정점 까지의 .. 공감수 0 댓글수 1 2023. 10. 16.
탐색 알고리즘 탐색알고리즘은 배열에 대해 탐색하는 선형 탐색 알고리즘과 트리나 그래프에 대해 탐색 알고리즘이 있다. 선형 탐색알고리즘에 선형 탐색과 이진 탐색 방법이 있다 선형 탐색 선형 탐색 방식은 배열의 시작부터 마지막 요소까지 순차적으로 탐색하여 요소를 찾는 방식이고 이진 탐색 이진 탐색 방법은 정렬이 보장되어있는 배열에서 배열의 중간 위치에서 시작해 탐색 하려는 요소가 중간 위치의 요소보다 작으면 왼쪽, 크면 오른쪽을 탐색하는 방법으로 이 과정을 반복하며 찾는 방법이다. 이진 탐색의 시간 복잡도는 O(logN)만큼을 가진다. 트리/그래프 탐색 알고리즘에는 DFS, BFS 방식이 있는데 DFS DFS는 깊이 우선 탐색으로 그래프에서 분기점이 있을 경우 모두 탐색 후 다음 분기 탐색하는 방식 가장 깊은 위치부터 탐.. 공감수 0 댓글수 0 2023. 10. 16.
정렬 알고리즘 정렬알고리즘에는 버블, 선택, 삽입 정렬과 분할과 정복 정렬인 퀵, 병합, 힙 정렬이 있는데 각각의 특징들을 살펴보자면 버블 정렬 (Bubble Sort) 버블 정렬은 인접한 인덱스의 요소들을 서로 비교하며 정렬하는 방식으로 구현 방법이 엄청 간단한 장점이 있지만, 인접한 모든 요소들을 비교하며 해당 요소보다 더 크거나 더 작은 요소면 스왑 작업을 해주어야 하므로 많은 요소들이 스왑 해야하는 단점이 있어 효율적이지 못하고 모든 요소들에 대해 비교해 주어야하므로 O(n^2) 시간 복잡도를 가지고 있다. 선택 정렬 (Selection Sort) 선택 정렬은 인덱스에 처음 위치부터 해당 위치의 뒤에 있는 모든 요소들을 비교하며 최대 또는 최소값과 교환 해주어 정렬해주는 방식으로 버블 정렬과 비교하면 적은 스왑.. 공감수 0 댓글수 0 2023. 10. 11.
해시테이블 해시테이블이란? 해시테이블은 테이블과 해시 개념이 합친 것으로 테이블은 Key, Value가 쌍을 이룰 때, 데이터를 구분하기 위한 Key를 가지게 되고, Key는 데이터를 구분하기 위한 기준이 되어야 하기 때문에 유일 해야한다. 즉, Key는 중복되면 안된다. 해시 개념은 해시 함수와 해싱이 있는데, 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 변환하는 함수이며, 해싱은 데이터를 이러한 해시 함수로 해시값(해시코드)로 변환하는 과정이다. 해시함수는 입력에 대한 결과가 항상 동일한 값이어야하고. 처리가 빨라야하며, 결과가 밀집도가 낮아야한다. 해시테이블은 Key, Value가 쌍을 이룰 때, 이 Key를 가지고 해시함수로 해시 코드로 변환하고, 이 코드는 고유한 인덱스로 작용하여 Key의 .. 공감수 0 댓글수 0 2023. 10. 10.
이진탐색트리 이진탐색트리란? 이진 탐색트리 자료구조는 트리 기반 구조로 비선형 자료구조이다. 우선 이진 탐색 트리는 이진 트리와, 이진 탐색 기법을 합친 개념으로 이진 트리 구조로 이루어져있고, 모든 노드가 최대 두개 이하의 자식을 가지고 있는 구조다. 이진 탐색 기법이란 정렬된 배열에서 가운데 위치한 요소를 기준으로 왼쪽은 작은 요소들, 오른쪽은 큰 요소들로 구분하여 탐색할 요소가 있으면 가운데 위치한 요소와 비교하여 더 작거나, 더 큰 위치의 배열로 이동해 이 과정을 반복하는 탐색 기법으로 빠르게 해당 요소를 찾을 수 있는 방식이다. 이진 탐색 트리는 이 둘 개념을 합쳐 완전 이진 트리 구조를 이루며, 해당 노드의 왼쪽 서브 트리는 모두 해당 노드 보다 작은 요소들, 그리고 오른쪽 서브 트리는 큰 요소들로 이루어.. 공감수 0 댓글수 0 2023. 10. 9.
우선순위 큐 - Heap 일반적인 큐(Queue)는 First in-First Out 구조로 먼저 들어온 데이터가 먼저 나가는 구조였다. 하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것 것을 말한다. 우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수있기 때문에 이 둘을 묶어서 같이 쓴 것이다. # 우선순위큐가 힙을 사용하는 이유 (알아두면 나쁠거 없음) 더보기 [주의] 왜 우선순위 큐는 배열이나 연결리스트로 구현하지 않을까? (출처 : 자료구조 - 우선순위 큐(Priority Queue)와 힙(heap) | ChanBLOG (chanhuiseok.github.io)) (1) 만일 배열로 구현한다고 가정합니다. 우선순위가 높은 순서대로 배열의 가장 앞부.. 공감수 0 댓글수 0 2023. 10. 8.
스택 vs 큐 스택 스택은 후입선출(LIFO : Last In First Out)구조를 가지고 있어 나중에 들어온 요소가 먼저 나간다는 특성을 가지고 있다. 스택 자료구조는 특정한 곳에서 사용되는데 문서의 History 기록과 웹사이트의 방문 기록 같은 이전에 작업하던 요소로 되돌아가고 싶을 때 사용하며, 프로그램에서 함수의 호출 스택 같은 개념도 나중에 들어온 함수가 먼저 작업되고 빠져 나가는 방식, 또는 게임에서의 PopupUI, Object Pool 에 이용될 수 있다. 스택의 구현 원리 스택의 구현 원리는 배열 방식 즉 리스트 방식으로 구현되는데, C#에서는 리스트를 그대로 사용하여 어댑터 방식을 사용할 수 있다. 스택에 요소를 추가하는 Push 함수는 리스트의 Add 함수를 사용할 수 있으며, 스택의 맨 위 .. 공감수 0 댓글수 0 2023. 10. 7.
선형리스트, (정적배열) 배열 vs (동적배열) List vs LinkedList 정적배열과 동적배열의 개념 및 차이 정적 배열은 배열의 크기가 컴파일 타임에 정해져 프로그램 실행 도중에 크기를 늘리거나 줄이거나 할 수 없지만 메모리에 연속적으로 저장되어 인덱스라는 개념을 이용해 접근과 탐색에는 용이하며 캐시 적중률(Hit Rate) 효율성이 좋다. # 캐시 적중률이란? (CS) - 알아두면 나쁠꺼 없음 더보기 캐시 적중률이란? (CS 내용) 캐싱(caching)은 컴퓨터의 처리 성능을 높이기 위한 기법 CPU는 데이터를 처리하기 위해 메모리와 끊임없이 데이터를 주고받는다. 이 때 CPU에 비해 메모리는 속도가 느리기 때문에 메모리에 접근할 때 CPU는 효율적으로 사용되지 못한다. 캐시 메모리(cache memory)는 CPU와 메모리의 속도 차이로 인한 병목 현상을 완화하기 위해 사.. 공감수 0 댓글수 0 2023. 10. 6.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.