전체 글 (90) 썸네일형 리스트형 플로이드 와샬(Floyd Warshall) 플로이드-와샬(Floyd-Warshall) 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 특히 음의 가중치가 포함된 그래프에서도 동작하지만, 음의 사이클(negative cycle)이 있으면 고장난다.플로이드 와샬의 기본 개념플로이드 와샬은 기본적으로 Dp(Dynamic Programming)알고리즘을 사용하는 알고리즘이다. 플로이드 와샬의 핵심은 "거쳐가는 경로"이다. 플로이드 알고리즘은 "dp[i][j][k] = "i에서 j사이 거쳐가는 모든 정점의 번호가 k 이하인 최단거리"를 기반으로 둔 것이다. 그래프 표현:그래프는 일반적으로 n x n 크기의 인접 행렬로 표현된다. 여기서 n은 그래프의 정점의 수이다. 이 행렬의 각 요소 Floyd[i][j]는 정점 .. 백트래킹(Back Tracking) 백트래킹(Backtracking)은 모든 가능한 해를 탐색하는 과정에서, 현재 상태에서 더 이상 해를 찾을 가능성이 없는 경우 되돌아가서 이전 상태로 돌아가는 기법이다. 이 방법은 최적화 문제와 조합적 탐색 문제에서 사용되는 경우가 많다.백트래킹의 기본 개념문제 해결을 위한 상태 공간 트리:백트래킹은 상태 공간 트리를 탐색하면서 해결책을 찾는다. 상태 공간 트리는 가능한 모든 상태(해결책 후보)를 나타내는 트리를 말한다. 백트래킹은 이 트리의 모든 노드를 탐색하여 해를 찾는 방법이다.가능성 없는 해의 가지치기(Pruning):백트래킹의 핵심은 겹치거나 가능성이 없어보이는 경로를 탐색하지 않고 이를 더이상 탐색하지 않는 것다. 이를 가지치기(Pruning)이라고 부른다. 더이상 탐색하지 않아도 되는 경로는.. 누적합(Prefix Sum) 알고리즘 누적합 알고리즘(Prefix Sum Algorithm)은 배열이나 리스트같은 데이터에서 연속된 부분의 합을 빠르게 계산하기 위한 알고리즘이다. 이 알고리즘은 주어진 배열의 각 요소에 대해 이전 요소까지의 누적합을 미리 계산해 두고, 이를 활용하여 특정 구간의 합을 효율적으로 구하는 데 사용된다. 누적합과 관련된 여러 문제가 있지만 먼저 가장 기본적인 누적합의 형태에대해 알아보자.누적합 알고리즘의 기본 개념누적합 배열(Sum Array):주어진 배열 A의 누적합 배열 Sum을 만든다. S[i]는 A 배열의 0번째부터 i번째 요소까지의 합을 뜻한다. 즉, S[i] = A[0] + A[1] + ... + A[i]구간 합 계산:배열 A의 구간 [i, j] (i 시간 복잡도 전처리: 누적합 배열을 생성하는 데 O.. 백준 14677: 병약한 윤호 문제 조건1. 약을 맨 앞 또는 맨 뒤에서만 꺼내 먹을 수 있다.2. 전체 3N개의 약을 모두 먹을 수 있는지 확인해야한다.3. 만약 3N개의 약을 모두 먹을 수 없다면, 최대 몇 개까지 연속적으로 먹을 수 있는지를 구해야 한다. 문제의 N범위가 적당함으로 BFS완전 탐색을 이용해 해결할 수 있다. ch[x][y] = 배열의 구간 [x, y]가 방문되었는지 여부를 체크하는 변수로 두고 약의 앞뒤에 두개의 포인터를 queue에 집어넣어 탐색해가며 구하면 된다. 큐에서 상태를 꺼내고, 현재까지 먹은 약의 개수를 최대값으로 갱신.현재 상태에서 시작 인덱스 st의 약과 끝 인덱스 ed의 약을 검사.arr[st]가 ct % 3와 같으면(현재 먹어야하는 약과 맨 앞의 약이 같다면), 시작 인덱스를 오른쪽으로 이동하.. 백준 17299 : 오등큰수 문제 설명주어진 수열에서 각 원소의 등장 빈도를 계산한 후, 각 원소의 오른쪽에서 그보다 더 높은 빈도를 가진 첫 번째 수를 찾아 오등큰수로 설정. 만약 그런 수가 없다면, 해당 원소의 오등큰수는 -1로 설정. 이를 통해 모든 원소에 대해 오등큰수를 구하는 문제. 문제 자체는 오큰수와 비슷하다. 오큰수에서 빈도수 계산이 추가된 문제이다. 1. 수열의 각 원소의 등장 빈도를 계산. 2. 수열을 처음부터 끝까지 순회하면서 스택을 사용해 각 원소의 오등큰수를 계산. -스택이 비어 있으면 현재 원소와 인덱스를 스택에 넣는다. -스택이 비어 있지 않으면, 스택의 맨 위 원소와 현재 원소의 등장 빈도를 비교. -현재 원소의 등장 빈도가 더 크면, 스택의 맨 위 원소의 오등큰수 현재 원소. 스택에서 해당 원소.. 백준 28357 : 사탕 나눠주기 문제 설명N명의 학생들의 점수와 사탕의 최대 개수 K가 주어졌을 때, 사탕의 총 개수가 K를 넘지 않도록 하면서 기준 점수 X를 가능한 한 낮게 설정하는 문제이다. 간단한 이분탐색 응용(파라미터 서치) 문제이다. 적절한 X를 이분탐색을 통해 찾으면 된다. X의 범위를 설정한다. X의 최솟값은 0, 최댓값은 10^12 이다.이분 탐색을 통해 중간값 X를 선택한다.선택된 X에 대해 각 학생에게 나누어 줄 사탕의 총 개수를 계산한다.사탕의 총 개수가 K를 초과하지 않으면 high = mid - 1, 초과하면 low = mid + 1.최종적으로 X의 최솟값을 찾는다.소스 코드#include #include #include int n;long long k;long long arr[500010];long long .. 백준 3015 : 오아시스 재결합 문제 설명N명의 사람들이 한 줄로 서 있고, 각 사람의 키가 주어진다. 서로 볼 수 있는 쌍은 두 사람 사이에 두 사람보다 키가 큰 사람이 없어야 한다. 이때 주어진 사람들중 서로 볼 수 있는 사람쌍의 총 수를 구한다.(1 ≤ N ≤ 500,000) 해당 문제는 스택을 통해 해결할 수 있다. 만약 키가 같은 사람이 주어지지않는다면, 모노톤 스택을 응용해 쉽게 해결이 가능하지만, 키가 같은 사람이 주어진다면 이를 따로 처리해야한다. 따라서 stack >를 잡은뒤, first = "키", second = "현재 키를 갖는 사람의 수" 로 정의하고 문제를 해결하면 된다. - 스택의 최상단 요소와 비교하여 현재 키 x보다 작은 키를 가진 사람들의 수를 ans(정답)에 더한다. - 현재 키가 스택의 최상단 키와.. 백준 17298 : 오큰수 문제 설명수열의 각 원소에 대해 오른쪽에 있는 더 큰 수 중 가장 왼쪽에 있는 수를 오큰수라고 한다. 이때 주어진 모든 배열의 수의 오큰수를 출력한다. 해당하는 값이 없으면 -1을 출력한다. 이 문제는 스택을 이용해서 풀면 된다. 주어진 배열을 순차적으로 스택에 넣어가며, 스택에 있는 값보다 현재 탐색한 값이 더 크다면, 스택에서 해당 수를 빼내고 그값의 오큰수는 현재 탐색중인 값으로 한다. 해당 방법을 이용하여 주어진 배열을 순차 탐색해나가면 된다. 반복문을 통해 각 원소 x(현재 탐색중인 배열의 값)를 입력받는다.스택이 비어있다면 스택에 (현재 인덱스, 배열의 값) 쌍을 추가.스택이 비어있지 않은 경우, 스택의 최상단 원소를 검사하여 x가 더 크면 스택에서 꺼내고, 그 인덱스의 오큰수를 x로 설정한.. 이전 1 2 3 4 5 6 7 ··· 12 다음
