요즘 재밌게 풀고 있는 주제가 세그먼트 트리이다. 아마 다들 이 문제로 처음 세그먼트 트리를 접했을 것이다. 이 문제는 세그먼트 트리를 사용해서 구간의 최솟값을 O(log N)만에 구하는 문제이다. 이처럼 세그먼트 트리는 구간에 대한 질의(Query)를 최적화하는 방법들 중 하나이다. 공부중인 Mo's Algorithm이나 Sqrt Decomposition과 함께 응용되어 사용되기도 하고 여러가지 형태로 변형되어 무궁무진하게 쓰이는 자료구조이다. 이런 이유로 내가 굉장히 재밌어하는 부분이 있다. 세그먼트 트리의 개념은 완전 이진 트리 형태로 구간질의를 최적화 하는 방법으로, 각각의 리프 노드를 길이 1짜리 구간, 그리고 내부 노드는 자식 둘의 구간을 합친 구간에 대한 답으로 구현한다. 예를 들어 수열과 ..
noj.am/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net 재밌는 문제다. 당연히 최대한 많은 칸을 지나야 제일 좋은데, 체스판을 생각해보면 모든 칸을 지나며 맨 위 왼쪽 끝에서 맨 아래 오른쪽끝으로 모든 칸을 지나며 갈 수가 없다. 그래서 딱 한칸을 빼고 모두 지나야 하는데, 그 칸은 당연히 점수가 제일 낮은 칸일거고, 조금 고민해보면 어느 칸을 안지날 수 있는지 알 것이다. 칸이 다 똑같은게 아니라 이 칸을 안지나게 된다면 한칸만 안지나고 경로를 그릴수가 없는 칸이 있다. 그래서 그거랑 최소..
이번엔 사탕 문제 두개를 풀었다. 사수아탕이랑 사수빈탕인데 비슷해 보이는데 난이도 차이가 심각하다. noj.am/14585 14585번: 사수빈탕 수빈이는 좌표평면 위에 앉아있다. "나는 좌표평면이 너무 좋아!!" 라고 수빈이가 말했다. 좌표평면에는 N개의 사탕바구니가 있고, 각 사탕 바구니에는 M개의 사탕이 있다. 각 사탕 바구니는 (x1, y www.acmicpc.net 사수빈탕은 쉽다. 단순 2차원dp로 풀면 되는데 함정은 M 최대가 100만이라 사탕이 (0, 0) 근처에 몰려있으면 int로는 부족할 수 있다는 점. 이거 못알아채서 두번이나 틀렸다. noj.am/2419 2419번: 사수아탕 첫째 줄에 n과 m이 주어진다. 둘째 줄부터 n개의 줄에 사탕 바구니의 위치 xi가 주어진다. (0 ≤ n ..
noj.am/1294 1294번: 문자열 장식 첫째 줄에 단어의 개수 N이 주어진다. N은 최대 20이다. 둘째 줄부터 N개의 줄에 단어가 주어진다. 단어는 최대 1,000글자이고, 공백은 없이 알파벳 대문자로만 구성되어 있다. www.acmicpc.net 첨엔 포인터를 써야하나 생각했지만 그냥 벡터에 문자열 담아놓고 쓴 글자를 지우는 방식을 사용하기로 했다. v[j].erase(v[j].begin()); erase라니,, 이게 C++? 또 substr 메소드로 첫 글자가 같을때 추가 비교를 해주었고, 느릴것 같았으나 128ms로 가뿐히 통과했다. 맞힌 사람 들어가보니 0ms도 있던데 이건 어떻게 한거지.. 질문 들어가서 좀 읽어보니까 pq써서 하면 편하고 빠르게 할 수 있을지도? 매번 substr 따는..
DP 말고 평소에 심화 공부 해보고 싶었던 그리디도 일지를 쓸거다. 그리디 특성상 아이디어가 굉장히 중요하고 구현에는 큰 문제가 없기 때문에 비슷한 문제라도 일지에 되도록이면 일지에 남기는 방향으로 진행할거다. 또 증명도 되도록이면 해서 올릴거다. 증명을 함으로써 아이디어가 기억에 더 잘 남고 비슷한 성질을 이용하는 아이디어도 잘 떠올릴 수 있을 것이라 믿기 때문에 신박한 아이디어는 증명을 꼭 해볼 것이다. 그리디 알고리즘은 매 순간순간 최적의 길을 택하는 알고리즘이다. 예를 들어 A→C 경로와 A→B→C의 경로가 있고 A에서 C까지 최소비용으로 가는 문제가 있을 때 A→B→C 경로가 더 싼 경우는 A→B + B→C < A→C인 경우고, 이는 달리 말하면 A→B < A→C이다. 즉 A에서 봤을 때 가장 ..
요즘 새로운 DP 방법들 찾아보면서 뭔가 알아야 되는거도 많아지고 해서 정리도 할겸 DP문제 푸는걸 정리해서 올려보고 싶었다. 겨울에 열심히 DP 파면서 어려운 문제도 4~5시간씩 써가며 풀었는데 3월되서는 3개는 풀었나? 싶어서 DP 푸는걸 기록해볼거다. 난이도 있는 백준(또는 정올)문제랑 내가 생각했던 간단한 풀이를 같이 남겨 나중에 보기도 편하게 하고, 아이디어랑 이런건 따로 더 쓸거다. 난이도는 한 골드 상위에서 플래, 다이아까지 공부할거다. DP말고도 그리디나 자료구조 일지도 쓰고싶은데 그건 시간될때.. 일단 겨울에 푼 어려웠던 문제 하나 noj.am/2647 2647번: 검은점과 하얀점 연결 2n개의 점이 x축의 좌표 1,2,...2n에 놓여 있다. 그 중 n개는 검은 점이고, n개는 하얀 점..