공부공간

www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 수열에서 연속된 부분배열의 최댓값을 구하는 문제.. 양수면 계속더하면 최댓값이 되지만 중간에 음수가있는경우, 음수의 덧셈으로 0보다 크면 계속 더해준다. N^2 / NlogN의 풀이도 있지만, O(N)에 해결가능하다 package algorithm; import java.io.BufferedReader; import java.io.InputStreamRea..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으� www.acmicpc.net 3가지를 체크해주자. 1. 첫번째가는 길이여서 N,M까지 갈수있는 길인지? 2. 두번이상 째에 가는 길인데 N,M까지 갈수있는 경로인지 ( visit[0][y][x] 값이 양수) 3. 두번째 이상가는길인데 N,M까지 갈수 없어서 갈 필요가 없는 길인지? 3번째고려요소를 놓쳐 예전에 못풀었던 문제였다. 즉 첫번째 탐색했을때 N,M까지 못가면, 이후 탐색에서 그쪽길로 가면안된다는 체크를 해주어야한다. i..