문제 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) 펜윅 트리 모른다면 대해서는 깔끔하게 설..

문제 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) 비트로 나타낸다. 단순히 생각하면 켜져있는 발전소들로 꺼져있는 발전소를 재시작할 때의 최소 비용들을 ..

문제 https://www.acmicpc.net/problem/1322 1322번: X와 K 첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 X + Y = X | Y 를 만족시키는 K번째로 작은 자연수 Y를 찾는 문제. 조금만 생각해보면 X+Y의 값이 X | Y 과 같기 위해서는 X와 Y의 비트들 중에서 1이 서로 겹치게 등장하면 안 된다는 것을 알 수 있다. 단순히 브루트포스로 해결하려 하면 X + Y = X | Y인 Y값을 1부터 K번째 수가 등장할 때까지 반복해야 하는데 K는 최대 2,000,000,000이므로 시간 안에 해결하는 것은 불가능하다. 따라서 비트마스크를 이용하여 K..

문제 https://www.acmicpc.net/problem/2064 2064번: IP 주소 네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 비트 마스크로 메모리나 계산 시간을 최적화하는 다른 문제들과 다르게 비트 마스크만을 이용하는 문제. 해당 문제에 등장하는 기법은 실제로 IPv4의 서브넷에 사용된다. 서브넷, 서브넷 마스크를 알아두면 문제를 훨씬 잘 이해할 수 있으므로 새로비님의 게시글을 통해 알아보고 오자. 서브넷, 서브넷 마스크 확실하게 짚고 넘어가자 - 새로비 즉, 컴퓨터들..