문제 https://algospot.com/judge/problem/read/ITES algospot.com :: ITES 외계 신호 분석 문제 정보 문제 수환이는 외계에서 날아오는 전파를 연구하는 범세계 대규모 프로젝트, ITES@home에 참가하고 있습니다. 외계에서 날아오는 전파는 전처리를 거쳐 각 숫자가 [1,10000 algospot.com 풀이 종만북 난이도: 중 큐를 사용하여 해결하는 문제. 신호의 기록은 입력값으로 주어지는 것이 아니라 직접 생성하는 문제이다. 특이 신호의 개수 N은 최대 50,000,000이므로 생성하여 저장하기보단 각 테스트 케이스마다 다시 생성하여 사용하는 것이 메모리를 절약할 수 있다. 우리는 신호의 수열에서 부분 연속 수열의 원소합이 K인 부분 수열의 개수를 찾아야..

문제 https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 solved.ac 난이도: Paltium 4 백준- 수열과 쿼리 21(16975)와 동일한 문제. 수열과 쿼리 문제는 펜윅 트리로 풀었지만 위의 문제와 같이 느리게 갱신되는 세그먼트 트리(lazy propagation)로 해결 가능하다. 프로그래밍 분야에서 lazy라는 의미는 계산이 필요할 때까지 최대한 처리를 늦추는 방..

문제 https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 느리게 갱신되는 세그먼트 트리로 해결할 수 있는 문제이지만 A를 아래와 같이 B에 대하여 나타낸다면 일반적인 세그먼트 트리나 펜윅 트리로도 해결이 가능하다. 동일한 구성의 문제를 느리게 갱신되는 세그먼트 트리로 해결하는 풀이는 아래를 참조하자. 백준 - 구간 합 구하기2(10999) 펜윅 트리 모른다면 대해서는 깔끔하게 설..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 기본 누적합 문제 백준 - 개똥벌래(3020) - Gold 5 세그먼트 트리 문제 백준 - 구간 합 구하기(11658) + 세그먼트 트리 - Gold 1 백준 - 최솟값과 최댓값(2357) + 세그먼트 트리 - Gold 1 백준 - 구간 곱 구하기(11505) + 세그먼트 트리 - Gold 1 백준 - 공장(7578)★ + 세그먼트 트리, Inversion Counting - Platium 5 알고스팟 - 족보 탐험(FAMILYTREE)★+ LCA + 세그먼트 트리 - 상 느리게 갱신되는 세그먼트..

문제 https://www.acmicpc.net/problem/11658 11658번: 구간 합 구하기 3 첫째 줄에 표의 크기 N과 수행해야 하는 연산의 수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 구간 합 문제 중에서도 중간에 값의 변경이 자주 일어나는 문제들은 세그먼트 트리 혹은 펜윅 트리를 통해 빠르게 해결할 수 있다. 해당 문제에는 두 가지 모두 적용 가능한데 2차원 세그먼트 트리로 코드를 작성하는 중에 repl.it에 오류가 계속 발생해서 2차원 펜윅 트리로 해결해 보았다. 펜윅 트리를 잘..

문제 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 세그먼트 트리를 응용하여 해결하는 문제. 기존의 세그먼트 트리는 구간의 합을 트리의 부모 노드에 저장했다면 본 문제에 적용하는 세그먼트 트리는 구간의 최솟값과 최댓값을 저장한다. 세그먼트 트리에 대해서 잘 모르겠다면 백준님의 게시글을 참조하자. 세그먼트 트리 (Segment Tree) - Baekjoon Onl..

문제 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 부분합을 구하는 문제이지만 단순한 부분합 구현으로는 중간에 배열의 값이 바뀌면 다시 연속합을 구해줘야 하는 문제가 생긴다. 배열의 길이가 n이라면 중간에 바뀐 값으로 다시 연속합을 구하면 O(n)의 시간 복잡도가 소요된다. 해당 문제에서는 중간에 배열의 값 변경이 빈번히 일어나, 단순한 부..

문제 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 solved.ac 난이도: Gold 5 이진 탐색으로 더 간단히 푸는 방법이 있지만 부분합 알고리즘만으로 해당 문제를 풀어보았다. 아래에서부터 올라오는 석순은 석순의 끝이 도달하는 구간에 위에서부터 내려오는 종유석은 그 끝이 도달하는 구간에 각각 해당 개수를 기록한다. 석순은 section_down, 종유석은 section_up에 각각 저장. 1 2 3 4 5 6 7 for(int idx=..

문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 단순히 다이나믹 프로그래밍을 적용하기에는 방문한 도시의 조합이 구현하기 힘들다. 총 도시의 개수가 16 이하이므로 비트마스크를 이용하여 방문한 도시는 bit 1, 아직 방문하지 않은 도시는 bit 0으로 표시하여 구해주자. now_city은 지금 위치한 도시 visited 는 방문한 도시의 비트 표현과 cach..

문제 https://www.acmicpc.net/problem/1102 1102번: 발전소 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 비트마스크와 다이나믹 프로그래밍을 이용하는 문제. 두 가지를 기법을 조합하는 문제다 보니 두 기법을 잘 안다면 난이도에 비해 어렵진 않지만 개인적으로는 한 가지 예외를 발견하기가 힘들었다. 해당 문제에서는 발전소가 켜져 있는 상태는(1), 꺼져있는 상태는(0) 비트로 나타낸다. 단순히 생각하면 켜져있는 발전소들로 꺼져있는 발전소를 재시작할 때의 최소 비용들을 ..