C++7 누적합 누적합이란 누적된 합을 담고있는 배열을 이용해 요소들의 합을 빠르게 구하는 방법 왜 씀? 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. 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. 백트래킹(Backtracking) 알고리즘 1.백트래킹이란? 해를 찾을 때 모든 경우의 수를 전부 고려하는 알고리즘이다. 다만 이름처럼 되추적 과정을 거쳐, 사실 모든 경우의 수를 다 돌진 않고 유망성을 판단해 버릴건 버리고 가는 방법이다. 쉽게 말하면 모든 경로를 돌긴하는데, 개중에 특정 조건만 만족하는 경우만 탐색하는 방법이다. 경우의 수 탐색에 트리가 사용되므로, 일종의 트리 검색 알고리즘이라고 봐도 무방하다. Backtracking(되추적) 해를 찾아가는 도중 그 경로가 해가 되지 않을 것 같다고 판단되면, 이전 단계로 돌아가 다시 찾아가는 기법 2. DFS 깊이우선검색(Depth First Search), 트리에서 깊이를 우선 기준으로 두고 탐색하는 방법으로, 백트래킹에서는 DFS를 이용해 트리를 탐색한다. (너비우선 BFS도 사용해 구.. 2024. 3. 24. 이전 1 2 다음
