Windows 아이콘
재밌는 기능을 찾았다 위에 보이는 것 처럼 깔끔한 아이콘을 폴더같은 바탕화면에 둘 만한 것들에 적용시키는 방법이다. 방법은 간단하다. 일단 적용시키고 싶은 거를 우클릭하고, 속성에 들어간다. 폴더의 경우 위 처럼 사용자 지정 탭에 들어있고, 바로가기의 경우 아래처럼 보이는 화면에 아이콘 변경 버튼이 있다. 그리고 아래 경로를 붙여넣어주면 된다. C:\Windows\system32\imageres.dll C:\Windows\system32\shell32.dll C:\Windows\system32\DDORes.dll C:\Windows\System32\moricons.dll (MS-DOS) image res에 깔끔한 아이콘들이 많은 것 같다. DDORes.dll는 제어판에서 볼만한 아이콘들이 많고 shell..
Dynamic Programming - Convex Hull Trick
이번엔 DP를 최적화하는 심화 기법에 대해서 알아보겠다. CHT, Convex Hull Optimization이라고도 불린다. 번역하면 볼록 껍질을 이용한 최적화 정도가 되겠다. 이름에서 볼록 껍질이 나오다시피 볼록 껍질을 응용해서 하나의 쿼리의 시간복잡도를 줄이는 것이다. 대표적으로 \(O(N)\)의 쿼리를 \(O(\log N)\)으로 줄이는 최솟값/최댓값 쿼리가 있다. 하지만 항상 사용할 수 있는 최적화 기법은 아니고, 최솟값/최댓값을 구하고자 하는 배열의 일부가 단조감소 혹은 단조증가할 때만 사용할 수 있다. 이렇게 말하면 너무 어려우니 예시를 보자. 아 그리고 이제 글에 \(\LaTeX\)이 적용이 돼서 기분이 너무 좋다. 이제 N^2나 a_1같은 표기 안봐도된다. 화살표도 \(\Rightarro..
자료구조 - 세그먼트 트리
요즘 재밌게 풀고 있는 주제가 세그먼트 트리이다. 아마 다들 이 문제로 처음 세그먼트 트리를 접했을 것이다. 이 문제는 세그먼트 트리를 사용해서 구간의 최솟값을 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에서 봤을 때 가장 ..