본문 바로가기

3. 알고리즘 공부

(59)
[453] 백준 2631번 - 줄세우기(LIS) 1. 문제https://www.acmicpc.net/problem/2631 2. 문제 이해임의의 순서로 수열이 주어질 때, 오름차순으로 정렬하기 위해 움직이는 최소 횟수를 구하는 문제입니다.움직일 때는 데이터를 정렬할 때처럼 자리를 서로 바꾸는 것이 아니라, 움직이는 수가 두 수 사이로 비집고 들어갑니다.[3, 7, 5, 2, 6, 1, 4] 가 주어질 때, 아래와 같이 최소 4번으로 정렬을 완성할 수 있습니다.3. 해결 방법해를 구하기 위해 두 가지를 살펴봅시다.가. 한 원소를 여러 번 움직일 필요가 없다.생각해보면 한 원소를 자리를 두 번 움직일 경우, 그냥 한 번에 최종 위치로 움직이는 것과 다름이 없습니다.굳이 두 번을 움직일 필요가 없고, 다시 말해 n개의 원소 중에 일부 원소만 선택해 자리를 ..
[452] 백준 11057번 - 오르막수(점화식과 DP테이블) 1. 문제https://www.acmicpc.net/problem/110572. 문제 이해길이가 N이고 원소가 한 자리 수인 단조 증가 수열의 개수를 구하는 문제입니다.단조 증가 수열은 나중에 나오는 원소가 이전의 원소보다 같거나 큰 수열을 말합니다.예를 들어 [2, 2, 3, 4]와 [3, 6, 7, 8], [1, 1, 1, 1, 9]는 단조 증가 수열이지만,[2, 2, 3, 2], [3, 6, 7, 6], [9, 1, 1, 1, 1]은 단조 증가 수열이 아닙니다.참고로 단조롭다는 표현은 영어로 monotonic으로 사용합니다. 3. 해결 방법우선 N이 1부터 차례대로 살펴봅시다. 길이가 1인 단조 증가 수열은 [0], [1], [2], [3], [4], [5], [6], [7], [8], [9]로 총..
[451] 백준 2240번 - 자두나무(DP 문제의 재미) 1. 문제https://www.acmicpc.net/problem/22402. 문제 이해물체의 상태는 1 또는 2이고 처음 상태는 1입니다.물체에게 정보가 1 또는 2가 임의로 최대 1000번 까지 순차적으로 주어지며, 물체의 상태와 같다면 값이 1 증가합니다.물체는 정보가 주어질 때 자신의 상태를 바꿀 수 있으며 바꾸는 횟수는 최대 30번입니다.이 때 얻을 수 있는 최대값을 구하는 문제입니다.3. 해결 방법가. 상태 변화 횟수와 현재 상태의 관계상태는 두 개(1 또는 2)이고, 처음 상태는 1로 고정이 되어 있습니다.상태를 홀수 번(1번, 3번, 5번, ...) 바꾼다면 상태는 2가 됩니다.상태를 짝수 번(0번, 2번, 4번, ...) 바꾼다면 상태는 1이 됩니다.다시 말해 상태 변화 횟수로 현재의 상..
[450] 백준 15486번 - 퇴사 2(DP 역순) 1. 문제https://www.acmicpc.net/problem/154862. 문제 이해상담원에게 상담을 할 수 있는 기간, 그리고 그 기간동안 매일 하나씩 상담이 주어집니다.각 상담은 완료까지 며칠이 걸리는지가 주어지고, 완료했을 때 가치가 주어집니다.상담원은 상담을 선택할 수도 있고 안 할 수도 있습니다.대신 상담이 진행 중이라면 새로운 상담을 선택할 수 없습니다.이 때 상담원이 얻을 수 있는 최대 가치를 구하는 문제입니다.각각 n개의 칸에서 시작하는 적당한 길이(T)의 막대가 있고, 막대에 값(P)이 정해져 있는 상황으로 바꾸어 생각할 수 있습니다.겹치지 않게, 그리고 n을 넘지 않게 막대를 적당히 골라, 값의 합을 가장 크게 하는 문제로 바꾸어 이해할 수 있습니다.3. 해결 방법막대를 순서대로..
[446] 느리게 갱신되는 세그먼트 트리(lazy propagation) 1. 세그먼트 트리 동작 과정세그먼트 트리는 루트 노드에서 리프 노드까지 범위를 나누어 가며 통일된 연산값을 유지해야 합니다.따라서 자식 노드에서 부모 노드로 올라가더라도 더 넓어진 범위에 대해 연산 결과를 유지할 수 있어야합니다.이게 가능한 연산은 최대, 최소, 덧셈, 곱셈 등 일부의 결과로 전체 범위에 적용이 가능한 연산을 세그먼트 트리에 적용할 수 있습니다. 8 크기의 배열에서 3, 2, 5, 3, 5, 2, 3, 4의 값을 가지고 있고, 구간합을 관리하는 세그먼트 트리는 다음과 같습니다. 이 세그먼트 트리에서 2 ~ 8 범위의 구간합을 구하고 싶다면 다음과 같이 구합니다. 찾고자 하는 범위 안에 포함될 때까지 자식으로 내려가며 합을 구하면, 2+8+14로 24라는 것을 알 수 있습니다.다음으로 세..
[445] 다익스트라 알고리즘으로 최단경로의 모든 정점 찾기 1. 다익스트라 알고리즘다익스트라 알고리즘을 순서대로 나타내면 다음과 같습니다.단순한 최단경로 찾기는 위와 같이 풀 수 있습니다.하지만 최단경로 상의 모든 정점을 찾고 싶을 때는 위의 과정 중에 추가적인 알고리즘이 필요합니다.2. 다익스트라 알고리즘으로 최단경로의 정점 찾기우선순위 큐에 다음 정점에 대한 정보를 추가할 때, 가중치를 더 작은 값으로 하는 간선 정보를 저장합니다.최단경로 탐색이 종료되면, 간선 정보를 담은 표를 가지고 역으로 거슬러 올라가며 최단경로 상의 모든 정점을 순서대로 확인할 수 있습니다.
[443] 순열, 조합, 중복순열, 중복조합 구현하기(파이썬 코드) - itertools 없이 1. 순열arr = [1, 2, 3]used = [False] * len(arr)def perm(arr, r): for i in range(len(arr)): if not used[i]: used[i] = True if r == 1: yield [arr[i]] else: for nxt in perm(arr, r-1): yield [arr[i]] + nxt used[i] = False print(*perm(arr, 3), sep="\n")# [1, 2, 3]# [1, 3, 2]# [2, 1, 3]# [2,..
[442] 백준 1979번 - 극적인 곱셈 1.  문제https://www.acmicpc.net/problem/19792. 문제 이해n, k 가 주어졌을 때, 위 그림과 같이 k로 끝나는 어떤 수에 n을 곱한 결과가 그 어떤 수를 오른쪽으로 한 칸씩만 옮겨진 수와 같은 결과가 되도록 하는 어떤 수를 구하는 문제입니다.3. 해결 방법찾고자 하는 수의 일의 자리 숫자는 무조건 k입니다.따라서 n을 곱한 값의 일의 자리 숫자는 (k*n)%10이고, 구하고자 하는 어떤 수의 십의 자리도 (k*n)%10이 됩니다.이제 구한 수를 a라고 하면 n을 곱한 값의 십의 자리 숫자는 (a*n)%10 에 (k*n)//10을 더한 값이 됩니다.그리고 그 수는 구하고자 하는 수의 백의 자리 값이 됩니다.이제는 이 과정을, 곱한 값에 다시 k가 나올 때까지 반복합니다.4..