본문 바로가기

Algorithm17

[DP] 백준 2156번 포도주 시식 (Java 풀이) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net [문제] 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해.. 2021. 4. 14.
[DP] 프로그래머스 도둑질 (Java 풀이) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [ 문제 설명 ] 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. [제한 사항] 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하.. 2021. 4. 14.
LCA (Lowest Common Ancestor) LCA는 이름에서 알 수 있듯이 두 정점 A와 B에서 가장 가까운 공통된 조상을 찾는 알고리즘입니다. 여기에는 2 가지 방법이 있는데요, 하나씩 조상 노드를 살펴보는 방법과 DP를 사용하는 방법이 있습니다. 트리의 depth를 H라고 할 때, 조상 노드를 하나씩 살펴보는 방법으로는 보통 시간복잡도가 O(H)가 나오지만, 최악의 경우 O(N)이 걸릴 수 있습니다. 하지만 DP를 사용하게 된다면? 보통 O(log H)가 걸리지만, 최악의 경우 O(log N)이 걸립니다. DP를 사용하는게 훨씬 빠르죠? 그래서 노드의 개수가 매우 많고, 검사해야할 노드가 매우 많은 경우에 DP를 사용한 방법을 활용하면 빠르게 답을 찾을 수 있습니다! 먼저, 조상 노드를 하나씩 살펴보는 방법은 사실 간단해요. 두 정점 A와 B.. 2021. 4. 1.
확장 유클리드 호제법 이전에 유클리드 호제법에 대해 알아본 적이 있었습니다. 유클리드 호제법과 확장 유클리드 호제법 모두 정수론을 이용한 알고리즘인데요, 유클리드 호제법이 a와 b의 최대 공약수 gcd(a, b)를 구하는 알고리즘이었다면, 확장 유클리드 호제법은 더 나아가 a와 b의 최대 공약수 gcd(a, b)와 ax+by = gcd(a, b)를 만족하는 x, y까지 구하는 알고리즘 입니다. 그럼 확장 유클리드 호제법을 어떻게 사용하는지 알아보겠습니다. 확장 유클리드 호제법을 사용하기 위해 간단한 규칙을 먼저 살펴봐야 합니다. 아래 규칙을 통해서 Ri가 0이 될 때까지 반복했을 때 마지막으로 나온 Xi, Yi가 gcd(a, b)를 만족하는 x, y가 됩니다. 초기 설정해줘야 하는 값은 X0 = 1, X1 = 0, Y0 = .. 2021. 3. 25.
인덱스 트리 (Indexed Tree) 구간합을 구하는 트리 종류에는 인덱스 트리, 세그먼트 트리, 펜윅 트리가 있습니다. 그 중에서도 오늘은 인덱스 트리(Indexed Tree) 에 대해 알아보려 합니다. 참고로, 인덱스 트리에 포함되어 있는 종류 중 하나가 세그먼트 트리이기 때문에 세그먼트 트리로 풀 수 있는 문제는 인덱스 트리로 모두 풀 수 있습니다. 인덱스 트리는 A라는 수열에서 구간 S ~ E 가 주어졌을 때, A의 구간 S ~ E 사이의 합을 구하기 위해 사용합니다. 중간 중간 A의 값이 하나씩 바뀔 때마다 그 구간의 합을 구할 때 인덱스 트리를 사용할 수 있습니다. 구현 과정을 보면 다소 복잡해 보일 수 있지만, 그래도 천천히 단계를 밟으면 쉽게 이해할 수 있습니다. 저는 Swift로 구현을 해볼건데요, 마지막에 Java 로 구현.. 2021. 3. 24.
플로이드 와샬 (Floyd Warshall) 플로이드 와샬 역시 벨만 포드나 다익스트라와 같은 최단 경로 찾기 알고리즘입니다. 다만, 1:N 최단 경로를 찾는 벨만 포드와 다익스트라와 달리, 플로이드 와샬은 N:N 사이의 최단 경로를 찾습니다. 그렇기 때문에 비용을 저장하는 배열로 이중 배열을 사용하게 됩니다. 순환만 발생하지 않는다면 음수 가중치도 가능하며, 기본적으로 동적계획법으로 접근하게 됩니다. 플로이드 와샬은 가능한 모든 경유지에 대해 모든 정점에서 모든 정점으로 가는 최단거리를 확인하기 때문에, 시간복잡도는 O(N^3)이 나옵니다. 역시 n:n 경로라 그런가 다른 알고리즘들보다 시간이 많이 걸리네요ㅎ.. 먼저 플로이드 와샬을 구현하기 위해서 좀 복잡하지만 아래와 같은 그래프를 사용하겠습니다. 그래도 보는사람 쉽게 보시라고 제가 색도 다르.. 2021. 3. 23.
벨만-포드 (Bellman-Ford) 오늘은 최단 경로를 찾는 대표적인 기법 중 하나인 벨만-포드 알고리즘을 알아보려 합니다. 벨만-포드는 V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점 S 에서부터 다른 정점까지의 최단경로 (1:N) 를 구하는 알고리즘입니다. 다익스트라와 달리 음의 가중치를 가진 간선을 가질 수 있고, 때문에 음의 사이클의 존재 여부를 확인해주어야 합니다. 최단거리를 구하기 위해 최대 (V-1)번 E개의 모든 간선을 확인하고, 음의 사이클을 확인하기 위해 한 번 더 E개의 간선을 확인합니다. 따라서 벨만-포드 알고리즘은 O(VE)의 시간복잡도를 가지게 됩니다. 구체적인 벨만-포드 Swift 코드를 보기 전에, 벨만-포드 알고리즘의 구현을 슈도 코드(Pseudo Code)로 먼저 보겠습니다. 슈도 코드.. 2021. 3. 8.
크루스칼 (Kruskal) 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 입니다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이죠. 보통 여러 개의 도시가 있을 때, 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하는 문제에서 적용됩니다. 크루스칼 알고리즘에서는 간선 리스트를 많이 이용합니다. 아래와 같이 방향이 있는 그래프에서는 출발, 도착 지점을 기록하고 비용이 있는 경우 추가적으로 기록해줍니다. 만약 방향이 없는 그래프라면 출발과 도착의 순서는 상관이 없습니다. 그럼 크루스칼을 한 번 구현해볼까요? 크루스칼을 구현하기 위한 단계를 간단하게 정리해보았습니다. Step 1. 비용이 적은 순서대로 간선 리스트를 정렬해줍니다. Step 2. 가장 위의 간선(비용이 가장 적.. 2021. 3. 4.
Disjoint-Set / Union-Find (디스조인트 셋, 유니온 파인드) 저는 예전에 디스조인트 셋이 유니온 파인드인지 몰라서 엥? 디스조인트 셋? 이건 뭐랭 했었는데 알고보니 같은 말이었네요ㅋㅋㅋ 그래서 말이죠, 오늘은 크루스칼에서도 사용되는 Disjoint Set을 알아볼게요. Disjoint Set의 원리는 서로소 집합과 연관되어 생각하면 됩니다. 새로운 집합을 추가하거나, 기존의 집합과 합치거나, 집합에 어떤 원소가 들어있는지 찾는 연산을 거의 선형시간에 가깝게 수행하는 자료구조라고 할 수 있죠. Disjoint Set이 Union-Find라고도 불리는 이유는, Disjoint Set을 구성하는데에 union과 find라는 함수? 개념? 을 사용하기 때문입니다. find를 통해서 a라는 요소가 b라는 요소와 같은 집합인지(연결되어 있는지) 를 확인 할 수 있고, uni.. 2021. 3. 3.
Lower / Upper Bound Binary Search (이분 탐색) 가 '원하는 값 x를 찾는 과정' 이라면, Lower Bound는 '원하는 값 x 이상이 처음 나오는 위치를 찾는 과정' 입니다. 마찬가지로 Upper Bound는 '원하는 값 x를 초과한 값이 처음 나오는 위치를 찾는 과정' 입니다. 따라서 Lower Bound와 Upper Bound를 이해하기 전에 Binary Search (이분 탐색) 에 대해 먼저 이해하고 오셔야 합니다❗️❗️ Lower Bound 의 계산 과정은 이분 탐색과 다를 바가 없습니다. 1. 탐색할 리스트는 정렬되어 있어야 한다. 2. start와 end, mid 변수로 이분탐색을 시작한다. 3. mid의 값이 number보다 작을 때 start를 mid+1로 설정한다. 4. mid의 값이 num.. 2021. 2. 26.
투 포인터 (+ 백준 2003) 오늘은 투 포인터라는 개념을 알아보겠습니다! 투 포인터는 알고리즘.. 이라기보다는 개념이라고 하는게 더 맞는 표현인 것 같아요. 1차원 배열을 두고 start, end 라는 두 개의 인덱스를 사용해서 답을 구하기 때문에 Two Pointer (투 포인터) 라는 이름이 붙었습니다. 사실상 두 개의 인덱스 (포인터) 를 사용한다는 것 외에 특별히 설명할 수 있는게 없어서 오늘은 백준 2003번: 수들의 합 2 를 예시로 투 포인터를 설명해보려 합니다. 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤.. 2021. 2. 25.
Linked List (링크드리스트) 링크드 리스트는 이름과 같이 하나하나의 요소가 연결되어 리스트를 이루는 구조입니다. 그리고 보통 싱글 링크드 리스트 (Single Linked List)와 더블 링크드 리스트 (Double Linked List)로 나뉩니다. 링크드 리스트를 사용하게 되면, 새로운 요소를 넣을 때 그 요소와 원래의 요소들을 연결하기 때문에 미리 데이터 공간을 할당할 필요가 없어집니다. 하지만 연결을 위한 별도 데이터 공간이 필요하기 때문에 저장공간 효율이 높지는 않습니다. 중간 데이터를 삭제할 때도 앞 뒤 데이터의 연결을 재구성해야하는 부가적인 작업이 필요하죠. 하지만 만약 데이터를 얼마나 집어넣을지 모르는 상태라면 링크드리스트를 사용해보는 게 좋습니다. 애초에 많은 데이터 공간을 할당하고 시작하는 것보다 리스트에 추가해.. 2021. 2. 24.

티스토리툴바