[알고리즘] 다익스트라

다익스트라 알고리즘이란??그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 각각 구하는 알고리즘 그래프 방향의 유무와 구현 방법에 구애받지 않고 적은 비용으로 가장 빠르게 해답에 도달하는 최단경로 알고리즘이다.하지만 음수 가중치가 존재한다면 사용할 수 없다. 정상 동작하는 경우도 있는데 음수 사이클이 있으면 잘못 나올 수도 있다.그래서 웬만하면 음수 가중치가 없을 때만 사용하는 것이 좋을 것 같다. 음수 사이클이 있는지 판별도 안된다음수가중치가 있다면 벨만포드를 사용하는 것을 추천한다. 다익스트라 알고리즘을 확장시킨 알고리즘인 A* 알고리즘도 존재한다. 구현 방식 1. 출발점으로부터 최단거리를 저장할 배열 - dist - 을 만들고, 출발 노드에는 0, 다른 노드들에게는 INF값을 채워 넣는다. 코드..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 1. 24.
• textsms

[알고리즘] 정렬

정렬이란?? 일련의 데이터들을 정해진 규칙을 따라 순서대로 나열하는 것정해진 규칙이란건 오름차순, 내림차순, 알파벳순서, 문자열의 길이 등 다양한 것이 될 수 있다. 정렬의 종류 1. 선택 정렬 (Selection Sort)제자리 정렬 알고리즘의 하나입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법시간 복잡도 O(n^2) 공간 복잡도 O(1) 정렬 과정첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째로 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다. 예제배열에 9, 6, 7, 3, 5가 저장되어 있다고 하고 오름차순으로 정렬할 때 예..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 1. 22.
• textsms

[자료구조] Heap (힙)

Heap 이란? Heap 자료구조는 이진트리 중에서도 완전이진트리의 속성을 가지고 있다. 힙은 최대 힙 Max Heap과 최소 힙 Min Heap으로 구분할 수 있다. 최대 힙은 부모노드가 항상 자식노드보다 큰 값을 가지고 있기 때문에 루트 노드는 항상 트리의 최댓값을 가지고 있게 된다. 반대로 최소 힙은 부모노드의 값은 항상 자식 노드보다 작기 때문에 루트 노드는 트리의 최솟값이 들어있게 된다. 항상 그렇기 때문에 이 힙의 새로운 값이 추가되거나 삭제되어도 특성은 유지되어야 한다.! 힙은 이진탐색트리와는 다르게 값의 중복이 허용되고, 좌우 노드 간의 관계가 아닌 상하 관계에서만 값의 제약을 받게 된다. 힙의 시간 복잡도 최대 혹은 최소값을 빠르게 가져오는 게 중요한 상황에서 사용할 수 있다.힙에서 최대..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 21.
• textsms

[자료구조] 그래프, dfs, bfs

그래프란? 정점(vertice)과 정점간의 관계를 표현한 조직도직접적인 관계가 있다면 두 정점 사이에 간선(edge)이 있고 간접적인 관계가 있다면 몇 개의 점과 선에 걸쳐서 이어진다.' 용어 정점(Vertice): 데이터가 저장되는 그래프의 기본 원소, 노드라고도 한다.간선(Edge): 정점 간의 관계를 나타내는 선사이클(Cycle): 한 정점에서 출발해 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 할 수 있음.자기 루프(Self loop): 한 정점에서 출발한 간선이 다른 정점을 거치지않고 다시 자기 자신에게 돌아오면 자기루프를 가진다고 표현함.차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 그래프 구현 그래프를 구현하는 방식에는 인접행렬과 인접리스트 방식이 있다. 인..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 21.
• textsms

[자료구조] 트라이 (trie)

트라이(trie)란? 트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조.흔히 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조이다. 장단점트라이는 문자열 검색이 빠르다.문자열을 탐색할때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 효율적이다.각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있음. 삽입 예제apple, app, asia를 입력했을 때의 모습 처음 apple을 넣을 때 head의 자식노드에 아무것도 없으므로 a를 추가한다.a노드의 자식도 없으므로 p를 넣어준다.p의 자식도 없으므로 다음 글자인 p를 넣어준다. 이런식으로 e까지 자식노드로..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 20.
• textsms

[자료구조] 트리순회 (전위, 중위, 후위)

트리를 순회하는 방법은 전위, 중위, 후위로 나뉜다.전위순회(preorder traversal)전위순회는 루트 노드를 먼저 탐색하고, 자식 노드를 탐색하는 방식이다.중위순회(inorder traversal)중위순회는 왼쪽 자식 노드를 탐색하고, 루트 노드를 탐색하고, 오른쪽 자식 노드를 탐색하는 방식이다.  후위순회(postorder traversal)후위순회는 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식이다.    재귀를 이용한 트리 순회 1. 전위순회 preorder // 전위 순회 (결과를 StringBuilder에 저장) private void preOrder(Binary node, StringBuilder result) { if (..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 20.
• textsms