noj.am/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net 재밌는 문제다. 당연히 최대한 많은 칸을 지나야 제일 좋은데, 체스판을 생각해보면 모든 칸을 지나며 맨 위 왼쪽 끝에서 맨 아래 오른쪽끝으로 모든 칸을 지나며 갈 수가 없다. 그래서 딱 한칸을 빼고 모두 지나야 하는데, 그 칸은 당연히 점수가 제일 낮은 칸일거고, 조금 고민해보면 어느 칸을 안지날 수 있는지 알 것이다. 칸이 다 똑같은게 아니라 이 칸을 안지나게 된다면 한칸만 안지나고 경로를 그릴수가 없는 칸이 있다. 그래서 그거랑 최소..
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에서 봤을 때 가장 ..