The Way

타이타닉(Titanic) / 1997 / 미국 / 제임스 카메론 명작 영화로 손꼽히는 타이타닉. 본의 아니게 EBS에서 방영해주어 보게 되었다. 오랜만에 본 감동적인 영화. 영화는 루이 16세의 다이아몬드를 위해 타이타닉 호를 인양하려 하는 탐사대원의 이야기로 다큐멘터리처럼 시작하여, 인양 소식을 접하게 된 늙은 로즈의 회상으로, 내용이 전개된다. 세계 최고의 배 타이타닉 호의 출항을 앞두고 망해가는 명문가의 로즈와, 가난한 화가 잭은 타이타닉 호의 각 1등실, 3등실을 타게 된다.잭은 특히 출항 직전 포커로 티켓을 따게 되는데, 티켓을 잃게 된 이탈리아 사람의 운없는 포커 한 판이 사실은 자신의 목숨을 건진 한 판이었다는 점은 상당한 아이러니. 전화위복이라는 한자성어가 떠오른다. 그 후 둘은 우연한 만..

문제 코드 * div1과 div2는 문제를 공유하므로 혹시 없는 문제는 같은 Round의 다른 division을 찾아보시기 바랍니다 총평: 맞왜틀의 향연... 이건 순전히 실력부족이다. A. Polycarp's Pockets최대 횟수로 출현하는 숫자를 찾는 문제. B. Binary String Constructing0 a개, 1 b개로 구성된 string을 만들어야되는데, 숫자가 바뀌는 경우가 정확히 x번인 것.많은 답이 존재할 수 있지만, 이런 문제의 경우 극단적인 케이스를 만드는 것이 경험상 편합니다. 총 x번 바뀔 때, 마지막 바뀌는 것만 빼고 숫자 하나씩 쓰면서 바꿔주다가,맨 마지막 바뀔 때는 남은 숫자를 몽땅 다 사용하는 것도 간단한 답이 될 수 있습니다. 예를 들어서 a = 8, b = 7, ..

요즘 경제 관련 기사들을 틈틈히 챙겨보고 있는데, 재미있는 기사가 있었다. "비트코인, 아직 안 팔았니?" 포기 모르는 코인맹신족 기사의 내용을 요약하면, 자신의 지인 A라는 사람이 가상통화 투자를 했고,10000%의 수익을 낸 12월부터 자신은 가상통화를 팔라고 조언했지만 A씨는 줄곧 "자신은 앞으로 4~5년 후를 내다보기 때문에 안 팔 것이다"라고 일관했고,12월부터 지금까지 가상통화 시장에 하락세가 계속되어 4000%로 수익이 감소하였다는 일화를 소개하며 "A씨의 가상통화에 대한 맹신이 흔들지 않는 가장 큰 이유는 A씨가 가상통화에 대해서 좋은 뉴스만 골라서 듣기 때문이다.""원금의 80~90%를 날리고도 여전히 가상통화를 포기 못하고 있는 사람은 하루 빨리 확증편향에서 빠져 나와야 한다. 한가하게..

내 인생 중 가장 낭비한 시간을 고르라면, 나는 1초도 망설이지 않고 카트라이더를 뽑을 것이다. 초등학교 어린 시절 카트라이더가 처음 나올 때 카트라이더를 처음 접했다. 잘 기억은 나지 않지만, 스피드전을 좋아했고 광꼬를 제일 좋아했던 것은 기억에 남는다. 아빠가 나 루찌차를 사주신다고, '아빠의노력'이라는 아이디를 만들어서 몰래몰래 조금씩 하신건 지금 생각해도 감동이다. 그 후 중학교 때 시나리오 위주로 아주 조금 심심풀이로 하다가, 대학교 때 친구 덕에 다시 카트라이더를 하게 되었다. 그렇게 잘하진 못했고, 친구들과 친목 위주로 했고 별짓을 다했다. 예를 들어서 3분 넘어서 완주한 사람, 1등, 3등, 리타이어 벌칙인 게임을 했는데, 결승선 앞에서 대기타다가 시간 맞춰서 잘 들어가야했다... 하는 시..

우선순위 큐를 이용한 다익스트라 알고리즘의 구현. 출처는 책 알고리즘 트레이닝. 특이한 점으로는 pq에 동일한 원소들이 추가되도록 방치한다는 것이다. 어차피 나중에 continue가 포함된 if문에서 다 걸러지게 된다. 느긋한 삭제라고 부른다. 코드는 다음과 같다. #include using namespace std; typedef pair ii; // index는 0 ~ v - 1 // v은 vertex 갯수, s는 시작점 // edge에 (번호, 거리)로 저장 int v, s; vector edge(v); vector dist(v, INF); dist[s] = 0; priority_queue pq; pq.push(ii(0, s)); while (!pq.empty()) { ii now = pq.top(..

초보자들에게 이항 계수는 보통 DP를 이용하여 계산하는 것이 정석이라 여겨진다. 하지만 어느 정도 문제를 풀다보면 DP의 메모리 범위 이상의 숫자들을 더 빠르게 계산해야 한다. 이번 AtCoder Grand Contest 025 B번 문제에서도 이를 이용하는 문제가 있었는데, 버벅이다가 결국 못풀었다. 따라서 이항계수를 구하는 방법들을 간단하게 공부해보았다. 이 분야의 한줄기 빛과도 같은 구사과님의 블로그를 참고하였다. 1. DP 생략. 시간, 공간 복잡도가 $O(n^2)$이라 쓸모가 없다. 대신 여기서 사용하는 점화식 $_n C_k = _{n-1}C_{k-1} + _{n-1}C_k$은 많은 아이디어의 기반이 되니 기억하자. * 아래 2~4번의 방법은 MOD가 N보다 크다고 가정하자. 예기치 못한 오류가..

Elo Rating System은 각종 게임이나 바둑, 체스 등 실력을 점수화시키는 곳이라면 널리 쓰이는 평점 시스템이다. 기본적으로 다음과 같은 가정을 만족시키도록 설계되었는데, "A가 B를 10배 많이 이기고, B가 C를 10배 많이 이기면 A가 C를 100배 많이 이긴다" 다시 말해, A가 B가 11경기를 했을 때 10:1이고, B가 C와 11경기를 했을 때 10:1이면 A와 C는 101경기를 했을 때 100:1이 되도록 설계된 것이다. 이길 확률인 '승률'과는 미묘하게 차이가 있음을 확인하자.승률끼리의 곱인 $\frac{10}{11} * \frac{10}{11} = \frac{100}{121}$를 만족하지는 않는다는 것에 유의. 이길 확률이 10배 차이날 때의 점수차를 400점으로 한다. (여기서..

문제 코드 * div1과 div2는 문제를 공유하므로 혹시 없는 문제는 같은 Round의 다른 division을 찾아보시기 바랍니다 A. Infinity Gauntlet생략. 저는 map 만들어놓고 하나씩 지웠습니다. B. High School: Become Human예상 외의 킬러 문제였습니다. 저를 포함한 많은 분들이 실수 다루는 데에 익숙하지 않다는 것을 잘 알 수 있었습니다. $x^y$와 $y^x$을 직접 계산하려는 분들은 없을것이고, 보통 생각하는게 "양변에 로그를 씌우자!" 일 것입니다. double x, y; cin >> x >> y; double t1 = y * log(x); double t2 = x * log(y); if (t1 > t2) cout > y; double t1 = y * l..

* 코드는 맨 아래에 있습니다 쉬운 문제는 거의 다 푼 것 같다. 이제 난이도 있는 문제들이 슬슬 나올.. 것 같다. # 백준 1406번: 트리의 지름# 백준 1967번: 트리의 지름트리의 지름을 구하는 좋은 알고리즘이 있다.http://blog.myungwoo.kr/112여기에 잘 설명되어 있음 # 백준 11650번: 좌표 정렬하기# 백준 11651번: 좌표 정렬하기 2pair은 문제의 조건대로 비교 연산자가 잘 정의되어 있으므로 사용하면 된다11651번의 경우 연산자 정의를 새로 하기보단 순서를 바꾸어주면 된다. # 백준 10814번: 나이순 정렬stable_sort 문제이다.그런데 한쪽이 string이라 약간 번거로운 면도 있고, swap시 시간도 오래 걸릴 것 같아서string은 따로 저장하고, ..

* 코드는 맨 아래에 있습니다 울 학교 학생분께 ACM-ICPC 같이 나가자고 연락이 왔다나랑 같은 휴학생이고 되게 열심히하실 것 같고 성격도 완전 천사같다앞으로 더 열심히 해야겠다 # 백준 10799번: 쇠막대기간단한 스택 문제. 스택에 막대 n개가 쌓여 있을 때 레이저가 자르면 n개의 조각이 더 생긴다. # 백준 1406번: 에디터특이하게 list를 사용하는 문제이다.list에서 insert와 erase할 때 iterator 위치가 약간 헷갈릴 수 있으니 주의 # 백준 10820번: 문자열 분석맨 마지막줄이 엔터가 있는지 없는지 참 아리까리하다..이것 때문에 틀림 ㅠ # 백준 11655번: ROT13뭐... 엄청 많이 접해봤을법한 카이사르 암호이다.오버플로우가 일어날 수 있으니 편하게 unsigned..