개발/알고리즘8 누적합 누적합이란 누적된 합을 담고있는 배열을 이용해 요소들의 합을 빠르게 구하는 방법 왜 씀? 11659번: 구간 합 구하기 4 (acmicpc.net) 이 문제를 예시로 보자. N개의 숫자가 주어지고,이 N개의 숫자 배열의 특정구간 i부터 j번째 수까지 합을 M번 구해야한다. N과 M 모두 1부터 100000 사이 수이므로, ]단순히 for문을 써서 배열의 숫자를 하나씩 sum변수에 더해가는 구현은 O(N^2)의 시간복잡도가 발생한다. 그런데 이를 누적합 배열을 이용한다면 O(N)으로 구현이 가능하다. 누적합 배열의 각 요소는 i번째 수까지의 합을 의미하기 때문에,누적합 배열의 요소를 미리 설정해놓고i번째수 까지의 합을 찾을땐 그냥 누적합 배열에 바로 접근하면 된다. #include#include#de.. 2024. 6. 16. 최장 증가 부분 수열, LIS 알고리즘 1. 가장 긴 증가하는 부분 수열, Logest Increasing Subsequence 증가부분수열이란, 주어진 수열의 일부 원소를 골라내서 만든 부분수열 중 모든 원소가 오름차순 부분 수열이다. 예를 들어 3 5 7 1 2 5 4 8 7 에서 3 5 7 8을 골라내면 이는 증가하는 부분 수열이다.1 2 7, 2 5 역시 마찬가지 이 중 그 길이가 가장 긴 증가 부분 수열을 최장 증가 부분 수열, LIS라고 한다. 위의 예시에서는 3 5 7 8 또는 1 2 4 8 이 LIS가 될 수 있다. 2. DP와 LIS LIS알고리즘 문제는 보통 주어진 수열에 대한 LIS의 길이를 구하는 것이다. 동적계획법, Dynamic Programming 알고리즘 문제의 예시로 쉽게 접할 수 있는 문제이므로 DP를 .. 2024. 5. 14. 동적계획법, Dynamic programming 1. 동적계획법이란 큰 문제를 더 작은 문제로 분해해 각각의 결과를 저장하여 본래 문제를 해결하는 알고리즘 설계법이다. 문제의 입력 instance를 더 작은 부분 instance로 나눈다. 작은 instance를 먼저 해결하고 그 결과 저장한다 저장된 결과들로 큰 instance를 해결한다. 이를 주로 Bottom-up, 상향식 방식으로 진행하게 된다. 코딩테스트에서 주로 숫자 제한범위가 크고, 경우의 수가 방대한 문제가 주로 DP로 설계하면 해결된다(고 함) 2. Memoization n번째 피보나치 수열의 수를 구하는 문제를 재귀식으로 풀 때를 생각해보자. func fibonacci(n) if n < 2 n else fibonacci(n - 1) + fibonacci(n - 2) 보다시피 f(n) .. 2024. 4. 5. c++) 백준 14888 백트래킹, 연산자 끼워넣기 14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 1. 접근 수열과 수열의 각 수 사이에 들어갈 연산자가 주어진다. 수열은 순서에 맞게 계산해야하므로 사실 고려할게 없다. 우리가 고려해야할 것은 주어진 연산자들의 모든 순서와, 그로 인해 계산된 결과들을 출력하는 것 뿐. 사실상 연산자들을 선택하는 순열로 생각하면 된다. 2. 풀이 operands 배열엔 수열을 이루는 수들을 입력받는다. operato.. 2024. 3. 25. 이전 1 2 다음
