코딩일지

다트(DART, Data Analysis, Retrieval and Transfer system)는 금융감독원 전자공시시스템이다. 학교 경제 과목에서 수행평가 할때 자료조사하기 좋은 서비스라고 선생님께서 알려주셨다. 다트를 처음 들었을 때 이걸 떠올리는 사람은 많지 않을 것이다. 다트는 보통 이런걸 나타내는 명사로 많이 쓰이기 때문이다. 다트(Darts)는 500여년 전 영국에서 시작된 스포츠로, 30년 전쟁에 참전한 영국 병사들이 나무에 빈 술통 뚜껑을 걸어 놓고 부러진 화살촉을 던지고 놀며 소일거리를 하던 것에서 비롯되어 영국 전역의 노동자 계층에 퍼져나갔다. - 출처 나무위키 사실 이런 게임보다는 NASA의 프로젝트인 Double Asteroid Redirection Test을 나타내는 단어로 더 ..

요즘 기하를 많이 풀고 있어서 기하에 관한 글도 좀 적어보려고 한다. 기하도 생각보다 복잡한 트릭이나 기술이 많이 쓰였고 특히 최근에 ICPC 서울 리저널 문제 셋을 돌아봤는데 어려운 기하 문제도 종종 나왔었다. 그래서 기하도 좀 열심히 풀어보려 한다. noj.am/13433 13433번: 기하 문제 첫째 줄에 가장 왼쪽 원과 직선이 닿는 점과 가장 오른쪽 원과 직선이 닿는 점 사이의 거리의 최솟값을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다. www.acmicpc.net 원을 직선에 접하도록 겹치지 않게 나열하라는 문제이다. 이런 간단한 기하적 아이디어가 금방 떠올랐고, 실수 오차도 float로 감당할 만한 수준인것 같아서 구현을 해봤지만 예제에서 바로 저 아이디어만으로는 풀 수 없다는..

noj.am/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 어떤 분이 열심히 백금광에서 백금을 캐고 계시길래 구경해볼겸 백금광에 놀러갔다. 근데 백금광 안에 웬 다이아몬드 광산이 있어서 좀 놀랐다. 아무튼 풀어봤다. 아쉽게도 2트를 했고 40분 정도가 걸렸다. 아이디어는 처음부터 맞은 것 같다. 처음에는 크기 제한을 보고 누적합을 써서 풀어야겠다는 생각이 들었고, 길이를 변수로 누적합을 만들었다. 이를 DP를 활용해서 모든 점에 대한 길이들을 다 담았고, 모든 점에서 길이들이 맞는지 확인하는 방식으로 답을 구했다. 처음 틀린 이유는 예외 처리를 ..

새 학기가 시작하고 한달 남짓 지났다. 역시 학기가 시작하면 뭔가 교과 외 일에 엄청 집중하는 것 같다. 파이썬으로 GUI도 좀 만져보고 CSS도 좀 하고 백준도 열심히 하고... 하지만 스트릭이 깨졌다. 4월부터 이어져 오고 있는 스트릭이었는데 얼마전에 새싹 7단계도 찍었지만 152일로 마무리했다. 최근 좀 어려운 문제를 2~3일 정도 잡고 푸는 일이 좀 있었는데 그래서인지 하루종일 파고 있다가 기진맥진해서 그날 코딩을 끝내버려서 프리즈가 많이 쓰였고 프리즈를 까먹었더니 스트릭이 날라가버렸다. 길게 쌓아오던게 없어져서 아쉽긴 하지만 밤에 급하게 코딩할 일이 없어서 어쩌면 좋긴 하다. 요즘은 그래프를 convex하게 만드려고 하고있다. 연초에 그리디를 갑자기 시작한거도 그리디 부분을 펴려는 노력의 일환이..

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에서 봤을 때 가장 ..