알고리즘/백준
-
[백준] 구간 합 구하기(2042번)알고리즘/백준 2021. 9. 19. 12:09
문제 링크 풀이 쉬운 문제는 아닙니다. 세그먼트 트리를 이용해야 합니다. 먼저 배열을 통해 살펴보겠습니다. 1. 구간 합 구하기 2. 특정 위치 값 변경 1번의 경우 점화식을 이용해서 푼다면 다음과 같으므로 O(N)입니다. s[0] = a[0]; for (int i = 1; i < n; ++i) { s[1] = s[i-1] + a[i]; } 2번은 a[4] = 3;의 방법으로 이루어지기 때문에 O(1)입니다. 1번이 M번, 2번이 K번 이루어진다면 O(NM + K)입니다. 문제에서 N, M, K는 적은 숫자가 아니기 때문에 O(NM + K)는 충분히 오래 걸릴 수 있습니다. 세그먼트 트리를 이용하면 O((M+K)*log₂N)에 가능합니다. O(NM + K)와 크게 다르지 않은 것처럼 보일 수 있는데, 문..
-
[백준] 유기농 배추(1012번)알고리즘/백준 2021. 9. 17. 09:41
문제 링크 풀이 전형적인 그래프 탐색 문제입니다. 문제에서 X좌표는 (행, 열) 중에 '열', Y좌표는 '행'에 해당합니다. 밭을 이차원 벡터로 표현하고 배추를 탐색한 곳은 확인하는 bool형 이차원 벡터도 필요합니다. 코드 #include #include #include using namespace std; int main() { int T, M, N, K; // c r 배추 scanf("%d", &T); int r_dir[] = {0, 1, 0, -1}; int c_dir[] = {1, 0, -1, 0}; while (T--) { scanf("%d", &M); scanf("%d", &N); scanf("%d", &K); vector map(N, vector(M, 0)); vector checked(N..
-
[백준] N-Queen 9663번알고리즘/백준 2021. 9. 7. 18:35
문제 링크 풀이 대표적인 백트래킹 문제라고 합니다. 백트래킹이란 깊이 우선 탐색 중에 오답을 만나면 이전 분기점으로 돌아가는 걸 말합니다. 재귀함수를 호출할 때 특정 조건일 때만 함수를 호출합니다. 트리로 봤을 때, 이전 분기점으로 돌아가 하위 노드가 구성되지 않은 모습을 가지치기라고도 합니다. 이 문제는 일차원 배열로 풀 수 있습니다. 문제를 보면 N x N 크기의 체스에 N개를 놓는 것이기 때문에 조건을 만족하는 경우의 수는 무조건 한 행에 하나의 퀸이 있어야 하기 때문에, 다음과 같이 표현할 수 있습니다. rows[0] = 1 // 0번째 행의 1열에 퀸 놓기 퀸을 위치시키는 규칙을 말하기 전에 재귀함수의 탈출조건부터 살펴보겠습니다. 재귀함수는 반드시 탈출 조건이 있어야 하는데요. 그 탈출 조건이란..
-
다익스트라(dijkstra) 최단 경로알고리즘/백준 2021. 8. 30. 17:55
풀이 다익스트라 알고리즘은 탐욕법과 동적 계획법을 같이 사용합니다. i 노드까지 최단 경로를 구하는 점화식 dist[i]가 등장하며 이를 구하기 위해 매번 최선의 선택(최소 가중치)을 수행합니다. 기본적인 흐름은 다음과 같습니다. 시작 노드를 방문하면서 시작합니다. 1. 방문한 노드에서 방문할 수 있는 다른 노드까지의 거리를 구합니다. 그 거리가 기존 값보다 짧으면 새로 갱신합니다. 2. 거리가 새로 갱신된 노드만 우선순위 큐에 넣습니다. 중복 방문을 없애기 위해서입니다. 이 외에도 중복 방문을 막기 위한 코드가 한 줄 더 있습니다. 3. 이 중에서 간선의 가중치가 최소인 노드를 방문합니다(우선순위 큐를 이용하면 최소 가중치를 쉽게 구할 수 있음). 4. 1번으로 갑니다. 코드 #include #incl..
-
[백준] 2805번 나무 자르기알고리즘/백준 2021. 8. 29. 16:49
문제 링크 풀이 내가 가져갈 수 있는 나무 길이가 나오는, 나무의 절단 높이를 구하는 문제다. 20 높이의 나무의 15로 높이로 절단하면 5를 가져간다. 이 문제의 특성은 이분 탐색을 통해 절단 높이를 구해가는 과정에서, 절단 높이가 작아질수록 잘린 나무의 길이가 커지는 데 있다. 그러므로 일반적인 이분 탐색에서 high, low를 구하는 조건을 반대로 해주면 된다. 코드 #include #include using namespace std; // 2805번 int main() { int N; // 나무 수 scanf("%d", &N); vector trees(N); long long M; // 필요한 나무의 길이 long long answer = 0; // 절단기에 설정할 최대 높이 long long h..
-
[백준] 3079번 입국 심사알고리즘/백준 2021. 8. 27. 18:44
문제 링크 프로그래머스 풀이 심사대의 범위가 1 ~ 100,000이고 친구들의 숫자가 최대 10억명이므로 이분 탐색을 사용하지 않으면 시간이 너무 오래 걸리게 될 겁니다. 이 문제에서는 어디에 이분 탐색을 사용해야 할까요. 우리가 구하고자 하는 답은 주어진 인원이 입국 심사 하는 데 걸리는 최소 값입니다. 입국 시간과 인원과의 상관 관계를 먼저 생각해볼게요. 예제에서 두 개의 심사대가 주어지고 각각 심사 시간이 7분, 10분입니다. 만약 입국자에게 5분이 주어진다면 어느 누구도 심사대를 통과할 수 없을 겁니다. 7분이면 1명만 통과할 수 있고요 10분은 돼야 2명이 받을 수 있습니다. 직관적으로 계산할 수 있지만 수식으로 해보면, 주어진 시간이 X일 때 각 심사대의 심사 시간을 나눈 값을 더한 총합입니다..
-
[백준] 1920번 수 찾기알고리즘/백준 2021. 8. 27. 12:27
문제 링크 풀이 이분 탐색 혹은 이진 탐색은 매 탐색 마다 탐색 범위를 절반으로 줄여 나가는 방식입니다. O(logN)의 시간 복잡도를 가지는데요. 약 40억 개의 데이터라도 32번 이하의 횟수에서 원하는 데이터를 찾을 수 있습니다. 찾을 수 없더라도 32번만에 알 수 있는 것이지요. 코드에서 find가 A[mid]가 되거나 혹은 mid == low == high 상황일 때(이 경우는 최대로 다 순회한 상태) 값을 찾았다고 판정하게 됩니다. 그리고 이분 탐색은 반드시 데이터가 정렬되어 있어야 합니다. 중간 값을 기준으로 요소의 크고 작음을 이용하는 것이기 때문입니다. 기본 흐름은 찾고자 하는 주어진 정수 데이터의 중간 값을 구해서 중간 값이 찾고자 하는 데이터보다 작으면 low 인덱스를 mid + 1로 ..