본문 바로가기

Dot Algo∙ DS/알고리즘 개념

[알고리즘] 최적화 문제 결정 문제로 바꿔풀기 - 파라메트릭 서치(Parametric Search)
Dot Algo∙ DS/알고리즘 개념 2021. 10. 22. [알고리즘] 최적화 문제 결정 문제로 바꿔풀기 - 파라메트릭 서치(Parametric Search) 최적화 문제 결정 문제로 바꿔풀기 딱히 이름이 붙어 있지 않지만 굉장히 유용한 디자인 원칙 중 하나로, 최적화 문제를 결정 문제(decision problem)으로 바꾼 뒤, 이것을 이분법(이진 탐색과 비슷하게 수치 해석 문제를 해결하는 기법)을 이용해 해결하는 방법이다. 결정 문제란 예 혹은 아니오 형태의 답만이 나오는 문제들을 가리킨다. 최적화 문제의 반환 값은 대개 실수나 정수이므로 답의 경우의 수가 무한한 데 반해, 결정 문제는 두 가지 답만이 있을 수 있다. 다음은 여행하는 외판원 문제(TSP)를 최적화 문제와 결정 문제로 표현한 것이다. optimize(G) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환한다. (최적화 문제) decision(G, x..
[알고리즘] 탐욕스러운 그리디(Greedy) 알고리즘 정리 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 10. 19. [알고리즘] 탐욕스러운 그리디(Greedy) 알고리즘 정리 (Java) 그리디 알고리즘 그리디 알고리즘은 가장 직관적인 알고리즘 설계 패러다임 중 하나이다. 이는 우리가 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없다. 그러나 모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는 두 방법과는 달리, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않는다는 것이다. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적..
[알고리즘] 최장 공통 부분 수열 LCS - DP & 이진탐색 LIS (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 8. 10. [알고리즘] 최장 공통 부분 수열 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)이다. 이는 주어진 여러 개의 수열 ..
[알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 8. 9. [알고리즘] 가장 긴 증가하는 부분 수열 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, ..
[알고리즘] 최소 공통 조상 LCA 트리 - DP & 세그먼트 트리 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 8. 4. [알고리즘] 최소 공통 조상 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를 찾는 과정을 보면 탐색을 할 때 편향트리를 만나게되면 엄청나게 많은 반복을 돌려..
[자료구조] 세그먼트 트리 + Lazy Propagation (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 7. 8. [자료구조] 세그먼트 트리 + Lazy Propagation (Java) 세그먼트 트리 기존에 세그먼트 트리를 이용한 문제는 구간 합을 구하는 쿼리와, 숫자 하나를 바꾸는 업데이트 쿼리로 이루어져 연속된 구간의 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 트리이다. 하지만 하나의 숫자만 업데이트하는 것이 아니라 어떤 구간 [a,b]를 전부 업데이트하고 구간합을 구하라고 하면 어떻게 될까? 세그먼트 트리 + Lazy Propagation 백준 10999번: 구간 합 구하기 2 해당 문제를 풀이하면서 lazy propagation에 대해 알아보자. 일반적인 구간 합 문제는 세그먼트 트리를 사용하여 그냥 풀면 되지만 갱신하는 부분이 업그레이드되었다. 구간을 업데이트해준 다음 구간 합을 구해야한다. 단순 세그먼트 트리만으로 풀이를 하게 되면 업데이트 처리를 할 때, 최악의 경우..
[알고리즘] 투 포인터와 슬라이딩 윈도우 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 7. 7. [알고리즘] 투 포인터와 슬라이딩 윈도우 (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의 값을 이동해서 앞에 있는 원소들을 하나씩 빼준..
[알고리즘] 순열, 조합 알고리즘 정리 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 6. 22. [알고리즘] 순열, 조합 알고리즘 정리 (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개 선택 : ..

티스토리툴바

티스토리툴바