본문 바로가기

ALGORITHM

 (45)
[C++/14502] 연구소 - using BFS 문제: 연구소 아이디어: BFS 전형적인 BFS 문제다. [특정 map에서 무언가가 퍼져나가는 경우의 수 or 시간 or 집합의 수] 등등의 대부분은 BFS/DFS로 해결 가능하다. 이 문제의 핵심은 어떻게 3개의 벽을 세울 수 있는 경우의 수를 계산하느냐에 달려있다. 나의 경우에는 3개의 벽을 세울 수 있는 모든 가능한 경우의 수를 계산했다. 벽은 빈칸에만 세울 수 있고 어떻게 벽을 세울 때 best 결과가 나올지 모르기 때문에 full search를 하도록 했다. 왜냐하면 애초에 제한 사항에 다음과 같이 map의 크기가 8x8이 최대이기 때문에 가능한 모든 경우의 수를 세어도 무방했다. 다음 로직에 따라 알고리즘을 구성했다. 1. map에서 모든 칸을 확인하며 빈칸일 때 3개의 벽을 세울 수 있는 경..
DP + LCS Algorithm에 대한 이해: 최장 공통 부분 수열 (Longest common subsequence problem) LCS : 최장 공통 부분수열 문제 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제이다. 다시 말해서 두개의 수열 사이에서 가장 긴 공통 부분 수열을 구하는 문제이다. 이때 주의할 점은 substring이 아니라 subsequence 이기 때문에 연속하지 않아도 된다는 것이다. LCS 풀이 접근 방법 그럼 LCS는 어떻게 구할 수 있을까? 기본 아이디어는 DP를 사용한다. 예를 들어 ACAYKP, CAPCAK 두 문자열의 LCS를 구한다고 해보자. 이때 두 문자열을 하나씩 늘려가면서 비교해가는 방법이 가장 쉬운 접근이다. 이때 DP를 사용하여 dp 테이블에 값을 저장한다. 문자열 ACAYKP와 두번째 문자열의 첫번째 char인 C와 최장 공통 수열의 길이는 1이다. 이..
[C++/LeetCode] Minimum Operations to Reduce X to Zero - using Sliding Window Daily LeetCoding Challenge for June, Day 11. 문제 아이디어: Sliding Window Sliding Window 특정 조건의 연속 합을 구할 때 고정된 사이즈의 윈도우를 이동시키며 O(N)으로 푸는 알고리즘 Two-Pointer 알고리즘과 달리 고정된 길이의 윈도우를 이동시킬 때 사용한다. 또한 정렬되어 있지 않아도 사용할 수 있다는 점에서 유용하다. 윈도우의 크기가 고정적이기 때문에 포인터가 2개일 필요도 없이 왼쪽 또는 오른쪽 포인터에 사이즈를 더하고 빼는 것으로 쉽게 윈도우의 범위를 구할 수 있다. 주로 Map을 이용해서 구현한다. Sliding Window 알고리즘의 특성과 시간 복잡도가 O(N)인 이유 sliding window의 특징은 윈도우의 크기가 고정..
음수 간선을 가지는 그래프의 최단 경로: 벨만-포드 알고리즘 최단 경로 알고리즘은 대표적으로 플로이드 워셜, 다익스트라 등등 있지만 이 중에서도 한 노드에서 다른 노드까지의 최단 경로에는 다익스트라 알고리즘이 사용된다. 하지만 다익스트라 알고리즘은 양수에서만 동작한다. 왜 다익스트라 알고리즘은 양수 간선에서만 해를 찾을 수 있을까? 벨만 포드 알고리즘의 대표적인 문제들 11657 타임머신 문제를 해석하면 위와 같다. 한 노드에서 다른 노드까지의 최단 경로인데, 이때 음수 간선이 있을 수 있다. 따라서 벨만 포드 알고리즘을 사용하면 쉽게 해결할 수 있는 문제이다. 구현 // 11657 타임머신 #include #include using namespace std; vector graph[501]; long dist[501];// long type이어야 함 int N,..
[C++/1697, 11779] 탐색 중 이전 값를 저장해야 하는 유형의 문제들 경로나 값을 저장해서 다음에 그 값을 참조해야 하는 경우의 문제들을 정리해보자. 대부분 그래프 탐색이나 BFS, DFS 문제에서 경로 찾기, 걸린 시간 등 출발지에서의 값을 가지고 있어야 하는 경우가 많다. 1697 문제 아이디어: BFS 현재 값인 N에서 가능한 동작은 3가지이다. +1, -1, 2배 이다. 이 경우로 탐색 가능한 값에 대해서 (현재 값까지 걸린 시간 + 1)을 더해서 저장해두고 이에 대해서 다시 탐색을 도는 방식으로 문제를 해결할 수 있다. 이때 저장해두는 값은 시작 노드인 N에서부터 걸린 시간이 된다. 구현 // 1697 숨바꼭질 #include #include using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(f..
[C++/LeetCode] Network Delay Time Daily LeetCoding Challenge May, Day 14 문제: 최장 거리 판별하기 아이디어: Dijkstra 신호가 전달되는 시간은 가장 긴 시간에 의해 영향 받는다. 따라서 시작 노드부터 다른 노드까지의 최단 거리를 구하고, 그 중 가중치가 가장 큰 값이 바로 Delay Time이 된다. 완성 submission: 120ms / 39.8MB class Solution { public: void dikjstra(vector graph[], vector &dist, int start) { // 우선 순위 큐 사용 priority_queue q; // 시작 노드를 넣고 이때의 가중치는 0이다. 시작 노드의 거리는 0으로 초기화 q.push({0, start}); dist[start] = 0; ..
[C++/3665] 최종 순위 - using 위상 정렬 (topology sort) 문제 아이디어: 위상 정렬 문제에서는 "순위"를 나열해야 하기 때문에 방향 그래프라는 것을 쉽게 알 수 있다. 이를 순위에 맞게 나열하는 것은 방향 그래프를 정렬하는 것과 같으므로 위상 정렬을 사용할 수 있다. 이때 사이클이 없는 위상 정렬은 항상 노드가 N개 일때 queue를 N번 돌기 때문에, 사이클이 생긴다면 N보다 작은 횟수로 종료하게 된다. 왜냐하면 진입 차수가 0이 되는 노드가 없어서 더 이상 탐색을 진행할 수 없기 때문이다. 따라서 이 경우 쉽게 "IMPOSSIBLE" 인 경우를 알 수 있다. 데이터의 일관성이 없는 경우 "?"를 출력하라고 하였는데 이는 같은 등수인 노드가 여러개인 경우이다. 이 오류는 queue에 들어간 node의 갯수가 몇개인지에 따라 알 수 있다. 즉 2개 이상의 no..
[C++/7576] 토마토 - using BFS 문제 아이디어: BFS 진짜 전형적인 BFS 응용 문제이다. 토마토가 익는 시간을 함께 queue에 넣어서 저장한 다음, 익는 시간이 특정 시간을 지나고 나면 하루가 지난 것으로 판별해야 한다. 또한 맨 처음에 queue에 넣는 좌표는 토마토가 있는 좌표를 모두 넣는다. 이때 시간대는 모두 0으로 초기화 한다. 토마토가 이동할 수 있는 동서남북 4 방향에 대해서 토마토가 없는 경우에 값을 바꾸고 queue에 넣어준다. 이때는 (이전시간 + 1)로 설정하여서 넣어준다. 구현 #include #include #include #include using namespace std; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int m, n; int graph[..

티스토리툴바