Gi-Log

문제 링크: https://www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 누적합, 다이나믹 프로그래밍 처음에는 만들 수 있는 모든 부분 행렬을 구하고, 각 부분 행렬 내 원소의 총 합 중 최대값을 구하는 방법에 대해서 생각해봤다. 부분 행렬을 결정하는 것은, 부분 행렬의 "좌측 상단"과 "우측 하단" 2가지 이다. 좌측 상단을 알고 있다면, 부분 행렬의 가로 길이와 세로 길이를 통해 우측 하단의 좌표를 구할 수 있다. 따라서 좌측 상..

문제 링크: https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 풀이에 이용된 알고리즘: 구간합, 누적합 고정된 길이 x의 구간 내 원소의 합이 가장 큰 구간을 찾고 그 합을 출력하는 문제이다. 또한 서로 다른 구간일지라도 동일한 합을 보이는 경우, 그 합이 등장한 횟수를 증가시켜가며 최종적으로 횟수 또한 출력한다. for문 사용하여 어떤 원소들의 합을 구하면 되고, 해당 구간을 한칸씩 이동시켜나가면서 그 합의 maximum 값을 찾으면 되..

문제 링크: https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 풀이에 이용된 알고리즘: 다이나믹 프로그래밍, 세그먼트 트리 구간 내 누적합을 구하는 문제인데, 단순히 for문을 이용하여 계산할 경우 시간 초과가 발생했던 것으로 기억한다. DP를 이용하여 효율적으로 문제 풀이를 진행할 수 있는데, 최근 세그먼트 트리를 공부하기 위해서 이 문제를 다시 풀어보았다. 세그먼트 트리에 대한 설명은 나동빈님의 블로그(https:..