✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/개념

✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/개념

    [알고리즘] 최단경로 - Dijkstra 알고리즘
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/개념

    [알고리즘] 최단경로 - Dijkstra 알고리즘

    Dijkstra 최단경로 최단 경로 알고리즘 (Shortest Path) : 시작 정점에서 끝 정점까지 가장 짧은 경로를 찾는 알고리즘 '길 찾기' 문제라고도 불립니다. 최단 경로 알고리즘은 보통 그래프로 표현되고, 해결 알고리즘은 3가지가 있습니다. 1. 다익스트라 알고리즘 2. 플로이드-워셜 알고리즘 3. 벨만-포드 알고리즘 오늘 포스팅에서는 다익스트라 알고리즘에 대해서 알아보도록 하겠습니다. Dijkstra 특징 1. 시작 노드 설정하고 이를 우선순위 큐에 넣는다. 2. 우선순위 큐에서 시작 노드에서부터 가장 거리 비용이 짧은 노드를 꺼낸다. 3. 꺼낸 노드로부터 갈 수 있는 방문하지 않은 모든 노드의 거리비용을 계산한다. 4. 만약 해당 거리 비용이 테이블의 거리비용보다 짧다면 갱신한다. Dijk..

    [알고리즘] MST - Prim 알고리즘
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/개념

    [알고리즘] MST - Prim 알고리즘

    Prim Minimum Spanning Tree 최소 신장 트리를 알기 전에 신장 트리 개념에 대해서 알 필요가 있습니다. 신장 트리 (Spanning Tree) : 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 여기서 사이클이 존재하지 않는 다는 것은 바퀴를 돌아 제자리로 올 수 있다는 것입니다. 신장 트리에는 사이클이 없어야 합니다. 최소 신장 트리는 이러한 신장 트리들 중에서 가중치의 합이 가장 작은 신장 트리를 이릅니다. MST 라고 하며 이러한 MST 를 구성할 수 있는 알고리즘은 2가지가 있습니다. 바로 Kruskal 알고리즘과 이번 포스팅에서 소개할 Prim 알고리즘 입니다. 2022.10.11 - [✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/개념] - [알고리즘] MST - Kruscal 알고리즘..

    [알고리즘] MST - Kruscal 알고리즘
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/개념

    [알고리즘] MST - Kruscal 알고리즘

    Kruscal Minimum Spanning Tree (최소 신장 트리) 최소 신장 트리를 알기 전에 신장 트리 개념에 대해서 알 필요가 있습니다. 신장 트리 (Spanning Tree) : 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 여기서 사이클이 존재하지 않는 다는 것은 바퀴를 돌아 제자리로 올 수 있다는 것입니다. 신장 트리에는 사이클이 없어야 합니다. 최소 신장 트리는 이러한 신장 트리들 중에서 가중치의 합이 가장 작은 신장 트리를 이릅니다. MST 라고 하며 이러한 MST 를 구성할 수 있는 알고리즘은 2가지가 있습니다. 바로 이번 포스팅에서 소개할 Kruskal 알고리즘과 다음 포스팅에서 소개할 Prim 알고리즘 입니다. Kruskal 특징 그리디 알고리즘을 이용하여 MST 를..

    [알고리즘] Next Permutation
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/개념

    [알고리즘] Next Permutation

    Next Permutation 개요 Next Permutation 은 순열과 조합을 구하는 또 하나의 방법입니다. 1 2 3 의 숫자를 가지고 순열을 만들기 [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] 1, 2, 3 의 숫자를 가지고 만들 수 있는 순열은 위와 같습니다. 보통 자연스럽게 순열을 구하고자 할 때 저렇게 구하는 편이 많습니다. 앞에 놔두고 뒤에 숫자들을 바꾸고.. 앞에 자릿수의 순열이 끝나면 다음 자릿수의 숫자를 젤 앞으로 가지고 와서 나머지 자릿수를 또 순열로 만들고.. 이러한 방법을 나타난 것이 바로 next permutation 입니다. 순열 package lecture; import java.util.Arrays; publ..

    [알고리즘] Bit Masking
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/개념

    [알고리즘] Bit Masking

    Bit Masking 개요 보통 알고리즘 문제를 풀 때 방문했다는 표시로 boolean visit 배열을 많이 사용합니다. BitMask 은 해당 visit 배열처럼 bit 표현을 통해서 true/false 를 표시하는 기법이라고 보시면 됩니다. 방문을 했다 → true, 1 방문을 하지 않았다 → false, 0 bit 자체가 0, 1 을 통해 표시가 되니 visit 배열과 방식의 차이가 없어 쉬이 이해가 되실겁니다. 저도 처음에 이게 무슨 소린가 싶었는데 bit 표현만 생각해보면 이해가 되는 것이었습니다. 이해가 안되신다면 아래 설명을 확인해주시길 바랍니다. bit 표현 public class Test { public static void main(String[] args) throws Excepti..

    [알고리즘] 슬라이딩 윈도우 개념 및 문제
    ✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/개념

    [알고리즘] 슬라이딩 윈도우 개념 및 문제

    슬라이딩 윈도우 사용하는 이유 예를 들어, { 1, 2, 3, 4, 5 } 라는 수열이 주어졌다고 봅시다. 여기서 부분 문자열 3씩 끊어 해당 부분 문자열 들 중에서 어느 부분이 제일 합이 큰지 알고 싶습니다. 그러면 두 개의 반복문을 이용하여 구할 수 있을 것입니다. package day220805.practice; public class Test { // 최댓값을 찾으려는 주어진 수열 static int[] arr = { 1, 2, 3, 4, 5 }; // 부분 문자열의 길이 static int P = 3; public static void main(String[] args) { // 최댓값 초기화 int max = Integer.MIN_VALUE; // 전체 인덱스를 돈다. for (int i = ..

티스토리툴바