돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/14870 문제 태그 DP, Two pointer, Segment Tree 문제 풀이 일단 기존 상태의 상황을 구하는 것은 매우 쉬울 것이다. 당연히 DP로 구할 수 있고, 이때의 식은 다음과 같다. $DP[i][j]=max(DP[i-1][j],DP[i][j-1])+arr[i][j]$ 여기서 특정위치의 arr값을 1을 올리거나 내리는 값을 했을 때 DP 테이블이 어떤식으로 바뀌는지 구해야 하는 문제이다. 만약 $DP[i-1][j]$와 $DP[i][j-1]$이 둘 다 바뀌었으면 $DP[i][j]$도 바뀌었을 것이다. 혹은 둘 중에 더 큰 값, 즉 영향을 받는 값이 바뀌면 바뀔 것이다. 여기서 한가지 관찰을 해야한다. 한 가로줄에 대해서..

문제 링크 : https://www.acmicpc.net/problem/14869 문제 태그 DP, deque, Segment Tree 문제 풀이 (의식의 흐름) 기본적으로 난이도가 있는문제이다. 일단 이 문제를 보자마자 이 문제가 DP라는 사실을 깨닫지 못했다면, 앞으로의 관찰은 거의 불가능한 난이도라고 생각해도 좋다. 그럼 DP 테이블을 정의해보려고 해보자. 일단 몇번째 강좌인지가 중요할 것이고, 어느 학원에서 듣는지가 중요할 것이다. 그렇게 $DP[i][j]$를 i번째 강좌를 j번 학원에서 수강할 때, 이때까지의 비용의 최솟값이라고 설정하자. 이러면 문제는 문제의 조건인, 한 학원에서 s~e 개를 연속해서 듣기를 만족할 수 없다. 그렇다고 $DP[i][j][k]$를 설정해서 k를 j번째 학원에서 현..

BOJ 14867 고등부 1번 물통 문제 링크 : https://www.acmicpc.net/problem/14867 문제 태그 bfs 문제 풀이 우리는 문제를 풀 때 항상 '상태'라는 것에 집중을 해야한다. 이번 문제에서는 문제의 디스크립션에서부터 이에 대한 언급을 해준다. 어떤 상태에서는 문제에서 주어진 행동을 할 수 있으며, 따라서 갈 수 있는 다음상태가 정해져 있다. 여기서 좀 생각을 해보면, 이를 그래프로써 표현하여 bfs로 문제를 해결할 수 있다. 각 상태가 그래프의 정점이 되며, 갈 수 있는 다음 상태(노드)들을 방향 간선으로 연결함으로써 그래프 문제로 옮길 수 있다. 이 과정에서 만약 (i,j) 를 1번 물통에 찬 물의 양이 i, 2번 물통에 찬 물의 양이 j로 생각해서 푼다면 한 가지 걸..

BOJ 8983 고등부 1번 사냥꾼 문제 링크 : https://www.acmicpc.net/problem/8983 문제 태그 스위핑 문제 풀이 N개의 x축에 붙은 지점중 임의의 어떤 지점에 대해서 택시거리가 L이하만큼 떨어져 있는지 판별하는 문제. 당연히 하나를 관찰하면 지점은 다 x축에 있으므로 모든 지점에 대해서 떨어진 y거리는 고정이다. 가장 중요한 관찰을 하자면 어떤 점에 대해서 가장 x값이 비슷한 지점과 거리가 가장 짧을 것이고 그 지점과 거리가 L보다 크면 당연히 나머지 지점에 대해서도 거리가 L보다 클 것이다. 따라서 그냥 가장 비슷한 x값을 찾는 문제. 배열에서 가장 비슷한 값을 찾는 것은 그냥 정렬을 해놓고 lower_bound를 돌려도 되고, 혹은 정렬을 해놓고 sweeping을 해서..

생각보다 시간이 많이 빠듯했다. 할 것도 많았고, 오랜만에 하다보니까 하나하나 생각하는데 시간도 꽤나 오래 걸렸다. 사실 애초에 이 셋에 일주일동안 쓴 시간이 다 합쳐봤자 얼마 안되었다는게 가장 문제였다. 18솔을 했다. 하지만 여왕벌은 거르더라도 실골 문제들을 풀자고 만들어 놓은 연습셋이 아니기 때문에 아쉬운 부분이 많다. 그래도 일단 쭉 정리를 해보려 한다 A - 사냥꾼 KOI 2013 고등부 1번 그냥 딱히 생각하는 것도 오래 안걸리고 구현도 딱히 안빡셌다. 무난한 문제 풀이 https://stonejjun.tistory.com/98 B - 막대기 KOI 2013 고등부 2번 문제를 잘 못봤다. 관찰 위주의 문제였고, 솔직히 오래 걸릴 문제도 아니었지만, 문제 조건을 잘못 봐서 오래 고생한것이 컸다..

사실 Technique라고 하기도 뭐하지만... 최근에 여러문제들을 풀면서 느낀 점이 있어서 간단하게 적어 놓으려고 한다. Prefix Sum 이란? Prefix = 접미사 sum = 합. 그니까 앞에서 부터의 합을 의미한다. 어떠한 값이 들어있는 기존의 배열 arr이 존재한다고 하면 $pre[x]=\sum_{i=1}^{x} arr[i]$ 로 표현되는 값들이 prefix sum들이라는 것이다. How? prefix sum 배열을 채우는 것은 $O(N)$만에 정말 간단하게 할 수 있다. $pre[i]=pre[i-1]+arr[i]$ 로 할 수 있다. 어떤 식으로 활용해야 할지에 대해서 고민을 해봐야 한다. prefix sum은 구간 합을 구할 때 주로 사용되어진다. i부터 j까지의 구간합은 $pre[j]-p..

시험이 끝나고 재활하는김에 원래 풀려고 했던 KOI를 모아놓고 쭉 돌아보기로 하였다. KOI 2013 ~ 2019년도의 문제를 모두 모아놓았다. 문제 리스트는 아래와 같다. 더보기 A - 사냥꾼 B - 막대기 C - 전봇대 D - 수족관 3 E - 버스 노선 F - 관중석 G - 동전 게임 H - 구간 성분 I - 매트 J - 여왕벌 K - 리조트 L - 주유소 M - 트리 N - 먼 별 O - 물통 P - 문명 Q - 요리 강좌 R - 조개 줍기 S - 화살표 그리기 T - XCorr U - 조화로운 행렬 V - 족보 W - 괄호 X - 검은 돌 Y - 고압선 2일차 결과 요즘 계속 바쁘기는 했지만 그래도 E,F,M 을 새로 풀었다. 버스노선 문제는 아침에 일어나자마자 생각해서 그런지 좀 생각을 했다...

시험이 끝나고 재활하는김에 원래 풀려고 했던 KOI를 모아놓고 쭉 돌아보기로 하였다. KOI 2013 ~ 2019년도의 문제를 모두 모아놓았다. 문제 리스트는 아래와 같다. 더보기 A - 사냥꾼 B - 막대기 C - 전봇대 D - 수족관 3 E - 버스 노선 F - 관중석 G - 동전 게임 H - 구간 성분 I - 매트 J - 여왕벌 K - 리조트 L - 주유소 M - 트리 N - 먼 별 O - 물통 P - 문명 Q - 요리 강좌 R - 조개 줍기 S - 화살표 그리기 T - XCorr U - 조화로운 행렬 V - 족보 W - 괄호 X - 검은 돌 Y - 고압선 1일차 결과 전체적으로 다 옛날에 푼 문제들이다. 옛날에 푼 문제중 아직 제출을 안한 문제는 매트와 족보다. 둘은 처음부터 다시 해볼 예정이다...

복기를 안할 수가 없다. 물론 Div2이기는 해도 Only Div2이고, 2등은 정말 말도 안되는 결과라고 생각한다. 1년 가량 주변에서는 쭉쭉 오르는데 코포 레이팅 변화가 크게 없어서 굉장히 불안했었다. 이는 Me in PS에서도 몇 번 언급을 했었다. 그런데 뭔가 불안했던 마음이 싹 사라지는 엄청난 코포였다. A . Matrix Game 어떤 가로줄이나 세로줄에 하나라도 놓여져 있으면 그 줄은 아예 못쓰고, 하나도 안 놓여져 있으면 전체 중 아무데나 놓을 수 있다. 여기서 좀 더 생각해보면, 게임의 어떤 상황에서도 놓을 수 있는 위치들을 모으면 직사각형 모양과 동치라는 것이다. 남은 각 줄에도 딱 한번씩만 놓을 수 있기 때문에 직사각형 모양에서 더 짧은 변의 길이의 홀짝성에 따라 달라진다. 결론적으로..

이번에 포스팅할 Segment Tree의 활용법은 구간 내에서 최대 부분합을 찾는 방법이다. 흔히 "금광 세그"라고 불리는 방식이며, 금광이라는 문제에 이 기법이 사용되어졌다. 어떠한 문제에서 두가지 쿼리가 주어졌다고 하자. 1번 쿼리로 수열에서 a번째 숫자를 b로 바꾸는 쿼리가 들어온다. 2번 쿼리로 l,r이 주어졌을때 수열의 [l,r]내에서 연속된 부분합의 최댓값을 구하는 것이다. 이러한 문제를 Segment Tree를 활용해서 해결할 것이다. 어떤 노드에 그냥 최대 부분합만 담고 있다고 생각해보자. 아래 두 개의 노드를 합칠때 그냥 둘 중 최댓값을 고르게 되면 왼쪽 절반 안에 속해있는 부분합과 오른쪽 절반안에 속해있는 부분합 밖에 알 수 없다. 두 구간을 걸친 부분들의 합은 고려해 줄 수 없는 것이..