목록오늘의 코딩 (386)
one day left
Hackerrank 풀었다.. 간단한 오토마타 법칙이 주어지고 K단계의 변환결과를 출력하는 문젠데, N과 K의 범위가 무지막지하게 크다는 점이 문제.. 심지어 O(K)도 TLE가 나온다. 변환을 O(1)로 한다고 해도 풀 수 없다는 것이다-_- 결국 규칙을 찾아내기로 했다. 그렇게 어제 한 4시간쯤 들여다보면서 생각하다가 빡쳐서 잤는데 오늘 아침 생각하면서 해결법이 떠올랐고 구현 5분 만에 한번에 AC받아냈다ㅠ_ㅠ 감격의 순간..가장 기본적인 점화식은 mix(start,end,k)=mix(start,end-1,k-1)+mix(start+1,end,k-1). 여기서 이들을 cache로 한 DP를 궁리했지만 범위가 너무 넓었다-_-중요한 아이디어는 mix연산이 교환법칙과 결합법칙이 성립하고, 항등원은 A이며..
Hackerrank 를 풀었다. DP문제중 좀 더 어려운 걸 풀고 싶어서 Difficult를 골랐는데 갑자기 문제수준이 헬이 됐다-_- 아무리 생각해도 답이 안나와서 Editorial을 참고했는데, 한참 걸려 이해했다.중요한 아이디어는 fuel이 0인 상태로 출발하니까, 어떤 출발점에서 한 번 일주를 할 수 있다면 무한 번 돌고돌 수 있다는 것. 왜냐면 출발점에서 연료가 0인 상태에서 출발해서 일주가 가능했는데, 일주를 한 다음에 출발점에 도착했을 때 연료는 0 이상일 테니까, 일주가 불가능할 리 없다. 또한 어떤 출발점 s에서 시작해 j점에서 막히면, s부터 j점은 모두 불가능한 출발점이 된다. 왜냐면 반대의 논리로.. 도착했을 때 연료가 0이상일 때도 불가능했는데 연료가 0인상태로 출발해 일주가 가능..
Hackerrank 은 생각보다 간단한 문젠데 문제특성상 디버깅이 거의 불가능하기 때문에-_- 거의 2시간여동안 날 짜증나게 했다. 이런 간단한 구현도 똑바로 못하는 내자신에 화도 날 정도로.. 실수를 두 가지 했었다. ?operator에 괄호를 안씌운 것. %operator에 대한 이해 부족.. 두번째는 완전히 몰랐던 사실이라 2시간의 가치가 있었다고 생각한다. C++ standard를 인용함.the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwis..
I talked my mom about my lack of fundamental knowledge on mathematics. However, after some consideration, I became doubtful in practice. I sometimes should make the difference between necessity and sense of inferiority. This has been not only an impetus to plunge into a brand new area, but also nothing ending up to the lack of steadiness, which I need the most now. I should concentrate more on C..
Sieve가 얼마나 시간이 걸리나 체크해보려고 별 최적화를 다해서 C++소스를 짜놨더니 n=10^7에 대해서 1초정도 걸리더라. 그런데 그냥 bool을 동적으로 n/2만큼 할당해서 계산하는 C소스(심지어 bool도 없어서 enum으로 정의함-_-)는 2초 안에 10^8까지 구해냈다. 허무해지는 순간... C/C++에서 짤 때는 우선순위큐보다 그냥 bool vector로 짜는 게 나은듯..저번에 봤던 Haskell로 짠 Sieve는 얼마나 걸릴지 궁금함..
Numerical Analysis 세 문제(ROOTS, LOAN, RATIO) 후기. 이분법은 쉽게 적용하겠는데 사실 수치해석은 수학과 연관이 깊어서 학부수준만 나와도 풀기가 힘들것 같다^_ㅜ 선대만 듣고 왔어도 좋았을텐데..
가입 5달만에 랭크 100위권 달성!-_-vApplied Mathematical Programming by Bradley, Hax, and Magnanti (Addison-Wesley, 1977) link두려운 마음에 미뤄뒀던 TSP를 해결했다. N
GRIEFSEED 후기. 2차원 배열 부분합에 관한 문제/나머지가 일정한 부분합 계산하기.HOMURAARSENAL 후기. mapping만 잘하면 되는 문제.
CICADAPRINCIPLE후기. 무려 3일에 걸쳐 고민해서 정답을 만들어냈다.. 고민하는 동안 XOR의 성질을 잘 알게 돼서 좋았지만, 해답 풀이인 가우스 소거를 떠올리지 못했다는 게 마음에 들지 않는다-.- 또한 여러 예외case덕분에 머리를 많이 썩힌 문제.
(p. 149) I wanted you to see what real courage is, instead of getting the idea that courage is a man with a gun in his hand. It's when you know you're licked before you begin but you begin anyway and you see it through no matter what. You rarely win, but sometimes you do. - AtticusKAKURO후기. 이 문제는 책을 읽지 않았다면 죽었다 깨어나도 못 풀었을 문제들(많다-_-) 중 하나. 미리 적절히 초기화된 배열을 이용해 아주 효율적으로 문제를 해결할 수 있다는 사실.
Autohotkey 스크립트가 여러번 수정을 거쳐 꽤나 안정적으로 돌아간다.BOARDCOVER2후기. STL없었으면 어떻게 풀었을까 싶을 정도로 더러운-_-문제. 조합탐색은 제약조건의 구현을 까다롭게 만듦으로서 사람을 고민하게 만든다.ALLERGY후기. "조합탐색에서 순서는 두가지를 의미한다. 첫 번째로 어떤 변수부터 넣을 것인가 하는 순서. 두 번째로 변수에 값을 넣는 순서." 이 순서를 결정하는 방법에 따라 조합탐색의 효율이 천차만별로 달라진다.
(p. 114) "Uncle Jack, please promise me somethin', please sir. Promise you won't tell Atticus about this. He─he asked me one time not to let anything I heard about him make me mad, an' I'd ruther him think we were fightin' about somethin' else instead. Please promise..." - 스카웃, 스카웃..(p. 116) "Jack! When a child asks you something, answer him, for goodness' sake. But don't make a production of it..
번사이드 정리...끙.. 오늘 꼭 이해하고 말리라. 링크! 바둑판에서의 경우의 수를 세는 문제를 풀고 있었는데, 개고생해서 하나하나 따져가며 AC를 받아냈는데(오답 7번이었나-_-), 딴사람 코드 보고 멍..해졌던 기억이 있다. 아마도 번사이드 정리를 써서 해결한 방법이었던 것 같은데.. 번사이드 정리는 군론과 관련이 있군!For any problem, there is a certain challenge in trying to solve it elegantly using only lists, but there are nevertheless good reasons to avoid too much of a fixation on lists, particularly if a focus on seeking ele..
Sieve of Eratosthenes의 시간복잡도 분석에 관한 논문 하나를 읽으면서.. Haskell을 배우고싶어졌다..@.@ Lazy Evaluation이란 개념이 아직까지 확 들어오지 않는다. Prime Number Theory에 관한 내용은 생소하기만 함.. 적분을 오랜만에 들여다보니 눈이 팽팽 돈다.. 그래도 궁금했던 Wheel Factorization은 이해했다!Competitive Programming이라는 책에 관심이 간다. 링크그리디 문제 세 개 후기. 그리디 알고리즘을 구상만 하면 구현은 진짜 쉬운데.. 문제가 그리디로 해결 가능한지 알아내는 것과, 그 해법의 정당성을 보이는 게 어렵다.
이야기를 쓰고 싶다. 읽고 싶다.GENIUS후기. 정방행렬을 class로 구현하는 게 귀찮아서 일주일 가까이-_-미뤄뒀던 문제. 이번에 Professional C++에서 배운 내용을 복습할 겸, 클래스를 만들어 봤는데 나름 재밌었다! 왜 디폴트 생성자와 복제 생성자, 대입 연산자가 함께 가야하는지도 느꼈고, 클래스를 잘 구현해 두면 코드가 정말 쉽다는 것도 느꼈다. 또 참조형 변수에 대해서 잘 알게 된 계기가 되기도~ 대입 연산자에서는 참조형이 가능하지만, 사칙연산을 오버로딩할 땐 참조형이 불가능한 이유도 다시 떠올리게 된다. 다만 vector구현이었기 때문에 속도가 조금 느려졌던 것 같다. 1000ms대 구현에서는 모두 동적 배열 할당으로 memcpy를 사용해 오버헤드를 줄인 코드들이었음.