C++에는 참 다양한 자료구조가 STL로 구현되어있다. 대표적으로 vector, queue, stack 등이 있으며 단순 선형 자료구조 이외에도 map이나 Linked List 등도 있다. 그중에서도 최근에 굉장히 유용함을 알게 된 자료구조가 있어서 이렇게 글을 남겨본다. 본래 프로그래밍 언어로 C++을 처음 접했으나 모종의 이유로 파이썬으로 대부분의 규모가 큰 코드들을 많이 작성했었는데, 그래서 어떤 기능을 가지는 프로그램을 만들고 싶을 때 파이썬으로 구현하는 일이 많았고 파이썬의 라이브러리를 빠삭하게 알게 되었다. 파이썬의 set, list, deque, dictionary 등을 매우 자주 쓰고 익숙해지다보니 정작 문제를 풀 때 사용하기에는 적합하지 않았다. 딕셔너리도 풀라고 만든 문제는 대부분 실버..
10월 말에 오프라인 컨테스트를 하고, 11월 첫 주에 오픈컨을 했던 DGUPC를 끝마쳤다. 시험이 끝나자 밀려오는 과제와 수행평가 때문에 이제서야 에디토리얼을 완성하고 후기글을 쓴다. 한 5월? 6월?쯤 부터 대회를 한번 열어봐야겠다고 생각했다. 예전엔 우리학교에 Code Jam을 정기적으로 했다는데 작년엔 자율동아리에서 진행한 암호맞추기가 끝이었고, 정보쌤이 퀴즈 형식으로 캐주얼한 컨테스트 정도가 끝이었다. 작년에 학교를 들어오고 정보에 관심을 가지게 돼서 아쉬웠고, 이제 2학년이 됐으니 본격적으로 프로젝트를 추진해보려고 했다. 작년에 platter님이 학교에 있어서 코드포스로 비공식 대회를 한번 열었었다. 그래서인지 올해 교내대회가 없다는 소식에 더 열고싶었던것 같다. 그래서 열심히 문제 프롬프트를..
요즘 기하를 많이 풀고 있어서 기하에 관한 글도 좀 적어보려고 한다. 기하도 생각보다 복잡한 트릭이나 기술이 많이 쓰였고 특히 최근에 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하게 만드려고 하고있다. 연초에 그리디를 갑자기 시작한거도 그리디 부분을 펴려는 노력의 일환이..
재밌는 기능을 찾았다 위에 보이는 것 처럼 깔끔한 아이콘을 폴더같은 바탕화면에 둘 만한 것들에 적용시키는 방법이다. 방법은 간단하다. 일단 적용시키고 싶은 거를 우클릭하고, 속성에 들어간다. 폴더의 경우 위 처럼 사용자 지정 탭에 들어있고, 바로가기의 경우 아래처럼 보이는 화면에 아이콘 변경 버튼이 있다. 그리고 아래 경로를 붙여넣어주면 된다. 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..
이번엔 DP를 최적화하는 심화 기법에 대해서 알아보겠다. CHT, Convex Hull Optimization이라고도 불린다. 번역하면 볼록 껍질을 이용한 최적화 정도가 되겠다. 이름에서 볼록 껍질이 나오다시피 볼록 껍질을 응용해서 하나의 쿼리의 시간복잡도를 줄이는 것이다. 대표적으로 \(O(N)\)의 쿼리를 \(O(\log N)\)으로 줄이는 최솟값/최댓값 쿼리가 있다. 하지만 항상 사용할 수 있는 최적화 기법은 아니고, 최솟값/최댓값을 구하고자 하는 배열의 일부가 단조감소 혹은 단조증가할 때만 사용할 수 있다. 이렇게 말하면 너무 어려우니 예시를 보자. 아 그리고 이제 글에 \(\LaTeX\)이 적용이 돼서 기분이 너무 좋다. 이제 N^2나 a_1같은 표기 안봐도된다. 화살표도 \(\Rightarro..