티스토리

그릿 속의 해빗
검색하기

블로그 홈

그릿 속의 해빗

loosie.tistory.com/m

Connecting The Dots

구독자
45
방명록 방문하기
공지 프로그래머로 사는 법 요약본 (샘 라⋯ 모두보기

주요 글 목록

  • [알고리즘] 접미사 배열(Suffix Array)와 LCP 배열(Lognest Common Prefix Array) (Java) 접미사(Suffix) 접미사(suffix)는 파생어를 만드는 접사로 단어 뒤에 붙어 새로운 단어가 되게 하는 말이다. 문자열 s의 i번째 접미사란, s 의 i번째 글자부터 마지막 글자까지 포함되는 부분문자열을 뜻한다. 문자열 "alohomora" A[i] S[A[i]···] 0 a l o h o m o r a 1 l o h o m o r a 2 o h o m o r a 3 h o m o r a 4 o m o r a 5 m o r a 6 o r a 7 r a 8 a 접미사 배열(Suffix Array) 문자열을 다룰 때 빼놓을 수 없는 자료 구조로 접미사 배열(Suffix Array)가 있다. 접미사 배열은 흔히 '문자열의 맥가이버 칼'이라고 불리며, 굉장히 다양한 문제를 푸는 데 쓸 수 있다. 접미사 배.. 공감수 2 댓글수 0 2022. 4. 7.
  • [알고리즘] 균형잡힌 이진 검색 트리 Balanced BST - 트립(Treap) (Java) 균형잡힌 이진 검색 트리 (Balanced Binary Search Tree) 표준 라이브러리의 이진 검색 트리는 대부분 X보다 작은 원소의 수를 계산하거나 k번째 원소를 찾는 연산을 지원하지 않기 때문에 이진 검색 트리를 직접 구현해야 할 경우가 종종 있다. 단순한 이진 검색 트리는 특정 형태의 입력에 대해 편향트리와 같은 연결 리스트가 되어 버리는 문제가 있기 때문에, 균형잡힌 이진 검색 트리를 구현해야 한다. AVL 트리나 레드 블랙 트리 등 교과서에 실리는 대부분의 균형잡힌 이진 검색 트리들은 구현이 매우 까다롭다. 다양한 경우의 수를 따져서 구현해야 하기 때문에 코드도 길고, 한정된 시간 안에 코드를 작성해야 하는 프로그래밍 대회에서 사용하기엔 부적합하다. 따라서 대회에서는 구현이 간단한 트립(.. 공감수 0 댓글수 0 2022. 1. 17.
  • [알고리즘] 펜윅 트리(Fenwick Tree) 빠르고 간단한 구간 합 구하기 (Java) 펜윅 트리(Fenwick Tree) : 빠르고 간단한 구간 합 세그먼트 트리의 가장 흔한 사용 예는 바로 구간 합을 빠르게 구하는 것이다. 이 경우 세그먼트 트리 대신 쓸 수 있는 세그먼트 트리의 궁극적인 진화 형태로 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(binary indexed tree)라고 불리는 것이 있다. 펜윅 트리가 사용하는 중요한 아이디어는 구간 합 대신 부분 합만을 빠르게 계산할 수 있는 자료구조로 만들어도 구간 합을 계산할 수 있다는 것이다. arr[]의 위치 pos에 대해 배열의 부분합 psum[pos] = arr[0] + arr[1] + ··· + a[pos]를 빠르게 계산할 수 있다고 하자. 그러면 [i, j] 구간의 합은 psum[j] - psum[i-1]로 .. 공감수 0 댓글수 0 2022. 1. 3.
  • [알고리즘] 이분 매칭 (Bipartite Matching) 알고리즘 (Java) 매칭 문제 (Matching Problem) N명의 유치원생이 소풍을 가는데, 단독 행동을 막기 위해 둘씩 짝을 이뤄 같이 다니게 하려고 한다. 단 서로 사이가 안 좋은 학생끼리 짝을 지어 주면 떨어져서 따로 다니기 때문에, 사이가 좋은 학생끼리만 짝을 지어 주고 싶다. 이런 규칙 하에서 모든 학생에게 짝을 지어 줄 수 있을까? 불가능하다면 최대 몇 쌍이나 만들 수 있을까? 그래프로 간단하게 표현할 수 있다. 각 학생을 표현하는 정점을 만든 뒤, 사이 좋은 학생들을 간선으로 연결한다. 이때 서로 짝을 이룬 학생들을 연결하는 간선들을 모아 보면, 이들은 끝점을 공유하지 않는 간선의 집합이 된다. 이런 간선의 집합을 이 그래프의 매칭(matching)이라고 부른다. (a) 굵은 회색으로 표시한 간선들은 끝점.. 공감수 0 댓글수 0 2022. 1. 1.
  • [알고리즘] 네트워크 유량, 포드-폴커슨(Ford-Fulkerson) 알고리즘 (Java) 네트워크 유량 그래프 문제에는 경로의 길이 외에도 그래프에 대해 정의할 수 있는 중요한 개념이 있다. 바로 그래프의 ‘용량’이다. 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 ‘흐름’ 혹은 ‘유량’을 보낼 수 있는지를 계산하는 문제를 네트워크 유량(network flow) 문제라고 부른다. 교통망에서 두 도시 사이를 이동할 수 있는 시간당 차량의 수, 송유관 네트워크에서 두 도시 사이에 보낼 수 있는 석유의 양 등 네트워크 유량은 현실에서 자주 찾을 수 있는 문제들이다. 또한 네트워크 유량은 굉장히 강력한 최적화 문제로, 그래프와 별 상관이 없어 보이는 다양한 최적화 문제들을 푸는 데도 이용할 수 있다. 유량 네트워크(flow network)란 각 간선에 용량(capacity)이라는 추.. 공감수 0 댓글수 0 2021. 12. 27.
  • [알고리즘] SCC(Strongly Connected Component) (백준 2150번 풀이) #2150 Strongly Connected Component 난이도 : 플레 5 유형 : 그래프 이론 / SCC 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net ▸ 문제 방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오. 방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는.. 공감수 1 댓글수 0 2021. 12. 5.
  • [알고리즘] 단절점 (백준 11266번 풀이) #11266 단절점 난이도 : 플레 5 유형 : 그래프 이론 / 단절점 / DFS 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net ▸ 문제 그래프가 주어졌을 때, 단절점을 모두 구해 출력하는 프로그램을 작성하시오. 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말한다. ▸ 입력 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000.. 공감수 0 댓글수 0 2021. 12. 3.
  • [알고리즘] 다중 문자열 검색 아호 코라식(Aho-Corasick) 알고리즘 정리 (Java) 아호 코라식(Aho-Corasick) 알고리즘 아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은 Alfred V. Aho와 Margaret J. Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘)이다. (위키 참고) 패턴 1개를 탐색하는 매칭 알고리즘은 선형 시간에 구현됨을 KMP 등 여러 알고리즘을 통하여 증명되었다. 하지만 패턴 집합에 대하여 이러한 알고리즘을 수행하게 되면 패턴 개수에 비례하여 그 속도가 느려지게 된다. m = 모든 패턴들의 길이 합, p = 패턴수, n = text 크기 즉 , O(m + p*n)의 시간 복잡도를 가지게 된다. 하지만 아호 코라식 알고리즘을 이용하면 O (m + p + n)의 시간복잡도로 패턴 집하에 대하여 패.. 공감수 1 댓글수 0 2021. 11. 29.
  • [알고리즘] 최적화 문제 결정 문제로 바꿔풀기 - 파라메트릭 서치(Parametric Search) 최적화 문제 결정 문제로 바꿔풀기 딱히 이름이 붙어 있지 않지만 굉장히 유용한 디자인 원칙 중 하나로, 최적화 문제를 결정 문제(decision problem)으로 바꾼 뒤, 이것을 이분법(이진 탐색과 비슷하게 수치 해석 문제를 해결하는 기법)을 이용해 해결하는 방법이다. 결정 문제란 예 혹은 아니오 형태의 답만이 나오는 문제들을 가리킨다. 최적화 문제의 반환 값은 대개 실수나 정수이므로 답의 경우의 수가 무한한 데 반해, 결정 문제는 두 가지 답만이 있을 수 있다. 다음은 여행하는 외판원 문제(TSP)를 최적화 문제와 결정 문제로 표현한 것이다. optimize(G) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환한다. (최적화 문제) decision(G, x.. 공감수 2 댓글수 0 2021. 10. 22.
  • [알고리즘] 탐욕스러운 그리디(Greedy) 알고리즘 정리 (Java) 그리디 알고리즘 그리디 알고리즘은 가장 직관적인 알고리즘 설계 패러다임 중 하나이다. 이는 우리가 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없다. 그러나 모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는 두 방법과는 달리, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않는다는 것이다. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적.. 공감수 6 댓글수 1 2021. 10. 19.
  • [알고리즘] 최장 공통 부분 수열 LCS - DP & 이진탐색 LIS (Java) 최장 공통 부분 수열 LCS (Longest Common Subsequence) LCS(Longest Common Subsequence)는 LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 나타내지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다. 최장 공통 문자열(Longest Common Substring)은 반드시 부분 문자열이 연결된 형태여야한다. banana, vbankn 최장 공통 부분수열(Longest Common Subsequence)은 떨어져있어도 상관없다. bdanvv, vbkkanm 이번에 다룰 LCS 알고리즘은 최장 공통 부분수열(Longest Common Subsequence)이다. 이는 주어진 여러 개의 수열 .. 공감수 1 댓글수 0 2021. 8. 10.
  • [알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java) 가장 긴 증가하는 부분 수열 LIS LIS(Longest Increasing Subsequence)는 불연속 상관없이 가장 긴 증가하는 부분 수열을 구하는 알고리즘이다. 예시로, 수열 A = {10, 20, 10, 30, 20, 50}이 있다고 하면 해당 수열의 LIS는 {10, 20, 30, 50} 이다. 풀이 방법으로는 DP를 활용한 LIS, 이진탐색을 활용한 LIS 두 가지가 있다. DP는 단순하지만 시간복잡도가 O(n^2)을 가진다. 이진탐색을 활용하면 시간복잡도를 O(nlogn)을 가진다. 1. DP로 풀이하는 방법 dp는 1차원 배열로 dp[i]에는 0~i 증가하는 부분 수열의 크기를 나타낸다. dp[i] = 0~i의 증가하는 부분 수열 크기 수열 A = {10, 20, 10, 30, 20, .. 공감수 6 댓글수 2 2021. 8. 9.
  • [알고리즘] 최소 공통 조상 LCA 트리 - DP & 세그먼트 트리 (Java) 최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor)는 주어진 두 노드 a,b의 최소 공통 조상을 찾는 알고리즘이다. 예를들어 아래의 트리에서 5번과 6번노드의 최소 공통 조상 LCA는 2번 노드이다. 일반적인 LCA 풀이방법 1번 루트노드를 기준으로 DFS탐색을 하면서 각 노드의 트리의 높이(h)와 부모 노드(parent)를 저장해준다. LCA를 구하기 위한 a,b번 노드가 주어지면 해당 두 노드의 h를 일정하게 맞춘다 (a의 높이 == b의 높이) 높이가 맞춰졌으면 각 부모노드가 일치할 때 까지 비교하여 구한다. (최대 LCA는 루트노드 1) LCA를 찾는 과정을 보면 탐색을 할 때 편향트리를 만나게되면 엄청나게 많은 반복을 돌려.. 공감수 1 댓글수 2 2021. 8. 4.
  • [자료구조] 세그먼트 트리 + Lazy Propagation (Java) 세그먼트 트리 기존에 세그먼트 트리를 이용한 문제는 구간 합을 구하는 쿼리와, 숫자 하나를 바꾸는 업데이트 쿼리로 이루어져 연속된 구간의 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 트리이다. 하지만 하나의 숫자만 업데이트하는 것이 아니라 어떤 구간 [a,b]를 전부 업데이트하고 구간합을 구하라고 하면 어떻게 될까? 세그먼트 트리 + Lazy Propagation 백준 10999번: 구간 합 구하기 2 해당 문제를 풀이하면서 lazy propagation에 대해 알아보자. 일반적인 구간 합 문제는 세그먼트 트리를 사용하여 그냥 풀면 되지만 갱신하는 부분이 업그레이드되었다. 구간을 업데이트해준 다음 구간 합을 구해야한다. 단순 세그먼트 트리만으로 풀이를 하게 되면 업데이트 처리를 할 때, 최악의 경우.. 공감수 0 댓글수 0 2021. 7. 8.
  • [알고리즘] 투 포인터와 슬라이딩 윈도우 (Java) 투 포인터 투 포인터는 주어진 배열에서 두 개의 포인터를 조작해가며 원하는 것을 얻는 기법이다. 투 포인터 알고리즘 문제 유형 포인터 2개가 같은 방향으로 진행 포인터 2개가 양끝에서 시작하여 반대로 진행 1. 포인터 2개가 같은 방향으로 진행 백준 2003번: 수들의 합2 해당 문제 예제 2번을 통해 시뮬레이션을 돌려보자. n = 10, m=5, 원소의 갯수가 10개인 배열에서 구간 합이 5인 구간을 찾으면 된다. 빨간색은 s이고, 파란색은 e인 두 포인터는 시작점 0에서 같이 탐색을 시작한다. e를 한 칸씩 움직여 s~e사이에 있는 원소들의 구간합을 구한다. sum :1 sum의 값이 m보다 크게 될 경우 e의 값을 조정하면 값이 더욱 커지기 때문에 s의 값을 이동해서 앞에 있는 원소들을 하나씩 빼준.. 공감수 0 댓글수 0 2021. 7. 7.
  • [알고리즘] 순열, 조합 알고리즘 정리 (Java) 순열 (Permutation) 서로 다른 n개중 r개를 골라 순서를 고려해 나열한 경우의 수이다. 보통 가수들은 음반을 내면 트랙 번호가 1번부터 순서대로 매겨져 있다. 10곡이 있는데 이 중 5곡을 앨범에 넣고 트랙의 순서까지 정하려고 한다면 몇 가지의 경우의 수가 나올까? 앨범에 [ 1, 6, 9, 8, 5, 4 ]의 순서대로 실으려고 하다가 갑자기 마음이 바뀌어서 [ 6, 1, 9, 8, 5, 4, ] 1번과 2번 트랙의 순서를 바꿨고하자. 그러면 앨범에 속해있는 1, 4, 5, 6, 8 ,9의 곡은 같지만 순서가 다르기 때문에 다른 경우의 수로 세줘야 한다. 1) 10곡 중 1개 선택 : 10가지 2) 9곡 중 1개 선택 : 9가지 3) 8곡 중 1개 선택 : 8가지 4) 7곡 중 1개 선택 : .. 공감수 0 댓글수 0 2021. 6. 22.
  • [알고리즘] 외판원 순회 문제(TSP: Travelling Salesman Problem) 정리 (Java) 외판원 순회 문제 (TSP: Travelling Salesman Problem) TSP(Travelling Salesman Problem, 일명 ‘여행하는 외판원 문제’)는 조합 최적화(Combinatorial Optimization) 문제로 전산학에서 연구된 가장 유명한 문제 중 하나다. 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다. 그래프 이론의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라"라고 표현할 수 있다. 즉 해밀턴 순환에 저비용 조건만 추가.. 공감수 2 댓글수 0 2021. 6. 15.
  • [알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java) 소수 소수(prime number)는 정수론의 가장 중요한 연구 대상 중 하나로, 양의 약수가(1보다 큰 자연수) 1과 자기 자신만을 약수로 가지는 수를 의미한다. 소수의 반대말로, 세 개 이상의 양의 약수를 갖는 자연수를 합성수라고 부른다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 소수 구하기 주어진 수가 소수인지 판별하는 문제는 소수에 관련된 가장 기초적인 문제이다. 주어진 수 n이 소수인지를 판단하는 가장 단.. 공감수 11 댓글수 0 2021. 6. 12.
  • [알고리즘] 비트(Bit)와 비트마스크(BitMask) 정리 (Java) 비트(bit) 비트(binary digit)는 데이터를 나타내는 최소 단위로 이진수의 한자라인 0 또는 1의 값을 가진다. 부호 없는 N비트 정수형 변수는 N자리의 이진수로 나타낼 수 있다. 이때 비트가 표현하는 값은 2^0 ~ 2^N-1까지이다. 여기서 2^N-1에 해당하는 비트값을 최상위 비트(Most Significant Bit)라 하고, 2^0에 해당하는 비트값을 최하위 비트(Least Significant Bit)라고 한다. 예를 들어 부호없는 4비트 정수형은 네 자리 이진수로 표시할 수 있는 모든 정수를 나타낼 수 있다. 아래 그림과 같이 4칸의 공간에 이진수 0 또는 1을 넣은 모든 경우의 수를 의미한다. 이때 비트가 표현하는 값은 2^0~2^3이다. 여기서는 2^3이 최상위 비트이고 2^0.. 공감수 4 댓글수 0 2021. 5. 31.
  • [알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java) 분할정복(divide and conquer) 알고리즘 분할정복 알고리즘 (Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬과 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다. 정렬 알고리즘 비교 선택 정렬과 삽입 정렬의 최대 실행시간은 O(n^2)이다. 입력하는 배열의 크기가 크다면 이 알고리즘으로 정렬하는데 매우 오랜 시간이 걸릴 수 있다. 반면 분할정복 알고리즘을 사용하는 합병 정렬의 실행시간은 모든 경우에 대해 O(nlgn)으로 , 퀵 정렬은 최대 O(n^2)이지만 최선이나 평균의 경우 O(nlgn)으로 비교적 빠른 시간을 갖는 것을.. 공감수 3 댓글수 0 2021. 5. 30.
  • [알고리즘] 백트래킹(Backtracking) 가지치기 기법 (Java) 백트래킹 Backtracking 백트래킹은 조건 만족 문제(CSP; Constrain Satisfication Problems)를 해결하기 위해 사용하는 알고리즘이다. 이는 어떤 조합을 탐색하는데 무작정 그리디하게 모든 곳을 탐색하는 것이 아니라 조건에 만족하지 않으면 왔던 길을 되돌아가 조건이 만족하는 부분에 한해 완전 탐색하는 것이다. ❐ 백트래킹의 대략적인 흐름은 다음과 같다. 1. 어떤 노드의 유망성(탐색 가능성) 체크 1-1. 탐색 가능하면 그대로 탐색 1-2. 탐색이 가능하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자식노드를 탐색 BACK! - ✂️가지치기 그래서 백트래킹(되추적)이라고 불리는 것이다. DFS + 백트래킹? DFS는 모든 노드를 방문하고자 하는 경우에 주로 사용한다. D.. 공감수 0 댓글수 0 2021. 5. 12.
  • [알고리즘] 문자열 매칭 알고리즘 KMP (Java) 문자열 매칭 알고리즘 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘이다. 워드파일 또는 웹 브라우저 DB에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다. 단순 문자열 알고리즘 가장 간단한 문자열 매칭 알고리즘으로, 말 그대로 하나씩 확인하는 방법을 사용한다. 검색할 문자열 ABDEGH 찾는 문자열 DE 가장 앞부분부터 찾는 문자열이 매칭될 때 까지 탐색을 시작한다. 검색할 문자열 A B D E G H 찾는 문자열 D E 매칭이 이루어지지 않았다면 한 칸씩 옆으로 이동시킨다. 검색할 문자열 A B D E G H 찾는 문자열 D E 매칭이 이루어졌으면 탐색을 종료한다. 검색할 문자열 A B D E G H 찾는 문자열 D E 코드 이 알고리즘은 이중포문으로 시간.. 공감수 6 댓글수 0 2021. 5. 11.
  • [알고리즘] DP문제에서 Top-down과 Bottom-up 어떻게 판단할까? Top-down vs Bottom-up DP문제를 풀 때 항상 고민하는 것은 'Top-down으로 풀어야하나 Bottom-up으로 풀어야하나' 이다. 그래서 다른 개발자들은 어떻게 접근하는지 참고해보자. Top-down은 언제 사용하는게 좋을까? → Generally, I recommend the top-down solution when either of the following is true: It's not easy to see in what order the sub-problems should be solved if you were going to solve them bottom-up. This is sometimes the case if the relationship between the sub-.. 공감수 4 댓글수 0 2021. 5. 2.
  • [알고리즘/그래프] 크루스칼(Kruskal) 최소 신장 트리 vs 다익스트라(Dijksta) 최단 경로 그리디 알고리즘 과정 해 선택 실행 가능성 검사 해 검사 크루스칼(Kruskal)과 그리디 알고리즘 최소 신장트리는 사이클을 형성하지 않고 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리이다. 최소 신장 트리를 구축하는데 한 가지 중요한 제약은 최소 신장 트리 내에 사이클이 형성되어서는 안된다는 것이다. 크루스칼 알고리즘 동작 방식 1) 그래프 내의 모든 간선의 가중치에 대해 오름차순으로 정렬한다. 2) 1)의 간선을 차례대로 순회하면서 최소 신장 트리에 추가한다. (사이클 생성 x) 그리디 과정으로 다시 보면 다음과 같다. 해 선택 : 가장 작은 가중치의 간선 선택 실행 가능성 검사 : 사이클 생성 여부 파악 (사이클 생성되면 x) 해 검사 : 모든 정점이 하나의 집합에 있는지 확인 다익스트라(.. 공감수 2 댓글수 0 2021. 4. 29.
  • [알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java) 최단경로 알고리즘 최단 경로 문제는 다음과 같이 분류할 수 있다. 모든 간선이 양수인 경우 음수 간선이 있는 경우 음수 간선 순환은 없는 경우 음수 간선 순환이 있는 경우 위의 분류를 3가지 알고리즘을 통해 구할 수 있다. 벨만포드 알고리즘 (Bellman-Ford Algorithm) → 2-1),2-2) 음수 간선이 있는 경우 다익스트라 알고리즘(Dijkstra Algorithm) → 1)모든 간선 양수 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) → 1)모든 간선 양수 벨만포드 알고리즘 벨만포드 최단 경로 알고리즘은 음수 간선이 포함된 상황에서의 최단 거리 문제를 풀 때 사용할 수 있다. 또한, 음수 간선의 순환을 감지할 수 있다. 동작 과정 출발 노드를 설정한다. (to, .. 공감수 1 댓글수 0 2021. 4. 25.
  • [알고리즘/ 그래프] 위상 정렬 (topology Sort) (Java) 위상 정렬 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 진입 차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출 차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 큐를 이용하는 위상 정렬 알고리즘의 동작 과정 진입차수가 0인 모든 노드를 큐에 넣는다. 큐가 빌 때 까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. ☞ 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다. 위상 정렬 특징 위상 정렬은 DAG에 대해서만 수행할 수 있다. DAG(Direct Acyclic Graph) : 순환하지 않는 방향 그래.. 공감수 1 댓글수 0 2021. 4. 23.
  • [알고리즘/ 그래프] 최소 스패닝 트리 - 크루스칼(Kruskal)과 프림(Prim) 알고리즘 (Java) 스패닝 트리 또는 신장 트리 어떤 무향 그래프의 스패닝 트리는 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 이때 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야 한다. 트리 형태여야 한다는 말은 선택된 간선들이 사이클을 이루지 않는다는 뜻이며, 정점들이 꼭 부모-자식 관계로 연결될 필요는 없다는 데 유의하자. 즉, 스패닝 트리는 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 최소 스패닝 트리 (MST) 최소 스패닝 트리란 최소한의 비용으로 구성되는 스패닝 트리를 말한다. 두 가지 유명한 알고리즘으로 크루스칼과 프림이 있다. 크루.. 공감수 1 댓글수 0 2021. 4. 22.
  • [알고리즘/ 그래프] 서로소 집합 자료구조 Union-find (Java) 서로소 집합(Disjoint Sets)이란? 서로소 집합(Disjoint Sets)은 공통원소가 없는 두 집합을 뜻한다. 서로소 집합 자료구조 (Union-find) 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조로, 합치기 찾기(Union-find) 자료구조라고도 불린다. 서로소 집합 자료구조는 두 종류의 연산을 지원한다. Union(합집합) : 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 Find(찾기) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 동작 과정 서로소 집합 자료구조에서는 연결성을 통해 손쉽게 집합의 형태를 확인할 수 있다. 합치기(Union) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다. A와 B의 루트 노드 A', B'를 .. 공감수 1 댓글수 0 2021. 4. 21.
  • [알고리즘/ 그래프] DFS와 BFS 정리 (Java) 깊이 우선 탐색 DFS 각 정점 노드를 깊게 탐색하는 방식으로 매 탐색을 stack으로 쌓으면서 갈 수 있는 최대한 깊이를 탐색하고 갈 곳이 없다면 이전 정점으로 돌아간다. 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라간다. 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 뒤돌아간다. 깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 깊이 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다. 인접 행렬 DFS DFS 하나에 for loop을 V번을 탐색하기 때문에 O(V) , 정점을 방문할 때 마다 DFS를 부르.. 공감수 4 댓글수 0 2021. 3. 22.
  • [알고리즘] 동적계획법 DP (Dynamic Programming) 정리 (Java) 동적계획법 Dynamic Programming 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로, 이름만 가지고는 무엇을 의미하는지 영 알 수 없기 때문에 가장 많은 오해를 불러 일으키는 주제이기도 하다. Dynamic? 동적? 기억하기? 자료구조의 동적할당(Dynamic Allocation)에서 '동적'은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. 그러나, 알고리즘의 동적 계획법(Dynamic Programming)에서 '동적'은 별 뜻 없다 그냥 '기억하기'라고 생각하면 편하다. '프로그래밍'은 컴퓨터 프로그래밍이 아니라 테이블을 만든다는 뜻이다. 중복되는 부분 문제 피보나치 수열을 코딩하려고 한다. 점화식이 F(n) = F(n-.. 공감수 7 댓글수 7 2021. 3. 9.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

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

    © Kakao Corp.