링크: https://www.acmicpc.net/problem/2517문제최선의 등수는 다시 말하면, "a[k] = 어떤 k 입장에서 왼쪽으로 자신보다 높은 실력의 개수" 이다."왼쪽으로"의 뜻은 "이전까지 등장한"과 같은 말이고, 자신보다 높은 실력의 개수는 기록을 통해서 셀 수 있다.문제는 수의 범위가 1,000,000,000 이하라서 수를 직접 저장하기는 힘들어 보인다.문제 조건 중, 참가한 선수들의 실력은 모두 다르다는 조건이 있다. 그럼 같은 의미로 그 사람의 등수를 기록하자.N은 50만 이하이므로, 등장한 등수(rank)를 1로 기록하고 k 위치에서 자신보다 높은 실력(=등수)는 세그먼트 트리로 쉽게 셀 수 있다.선수 k의 최선의 등수는 query(자신의 등수 + 1, 범위 끝) + 1이다...

세그먼트 트리는 임의의 위치의 값들이 계속 변화하고, 특정 구간에 대한 연산(어떤 구간의 합, 어떤 구간 중 최소값 등)을 빠르게 구할 때 용이한 자료구조이다.한국어로는 구간 합 트리?라고도 하는 것 같다. 이 글을 적는 이유는 세그먼트 트리 자체를 다루기 위한 것은 아니고, 크기를 2배로 잡는 대신에 비재귀 형태로 간단하게 작성할 수 있는 코드를 소개하려고 한다.처음 접한 건 2016년 쯤 코드포스에서 읽었다. 워낙 간단하고 명료해서 아직까지 외우고 있다.링크: http://codeforces.com/blog/entry/18051대회에서도 자주 사용했는데, 블로그 포스팅은 한 적이 없어서 나중을 위해 다시 적어둔다. 자세한 설명은 원문 링크에 자세히 나와있으므로 생략한다.사용할 때 주의할 점은, que..

링크: https://www.acmicpc.net/problem/1308문제풀이 재활훈련을 시작했다.문제를 푸는 데 실수가 너무 많아진다..문제날짜, 시간 차이를 구하는 문제는 정수 하나로 변환해서 퉁 치는게 제일 편하다. (년/월/일 -> 총 X일)단, 조건 중에 천년을 넘어가면 gg를 출력해야하는데, 2000/05/05 ~ 2100/04/30 같은 경우는 천년을 넘기지 않음에 조심해야한다.코드

링크: https://www.acmicpc.net/problem/17520풀이균형잡힌 문자열에서 확인하는 모든 부분 문자열은 첫번째 문자를 포함한다. 즉, 앞에서부터 순차적으로 확인하여 0와 1의 개수가 1 이상 차이가 난다면 균형잡힌 문자열이 아니라는 뜻이다. 우선 무식하게 모든 경우의 수를 다 확인해볼 수 있다. i번째 위치를 0 또는 1로 결정하면서, 균형잡힌 문자열이 되는 경우만 탐색했다. n=3일 때, 010, 011, 100, 101 네 개의 문자열이 나온다. n=1부터 하나씩 확인해보면 $2, 2, 4, 4, 8, 8, \dots, 2^{n-1}, 2^{n-1}, 2^{n}, 2^{n}$ 로 규칙성이 보인다. 이제 문제는 \(f(n)=2^{\lfloor{(n+1)}/2\rfloor}~mo..

링크: https://www.acmicpc.net/problem/1699문제주어진 N을 최소 몇 개의 제곱수의 합으로 표현할 수 있는 지 구하는 문제이다. 문제를 풀기 전에, 라그랑주 네 제곱수 정리를 알고 있으면 좋다. 백준 온라인 저지에 문제로도 등장했다. BOJ 3933 - 라그랑주의 네 제곱수 정리 요약하면, 모든 양의 정수가 많아야 4개의 제곱수의 합이라는 정리인데, 다시 말하면 이 문제의 정답은 최대 4라는 뜻이다. $x^a + y^b + z^c + w^d = N$ 에서 $a,~b,~c,~d$ 를 모두 확인해 볼 필요는 없다. 라그랑주의 정리에 의하면 모든 $a,~b,~c$를 찾았는 데 없으면 4개로 표현할 수 있기 때문이다. 즉, 3중첩 반복문으로 해결 가능하다.코드

링크: https://www.acmicpc.net/problem/17521문제보자마자 주식 문제가 생각났다.주식 문제들은 최대 이익을 내기 위해서 그리디하게 행동하면 된다. 값쌀 때 사서 값비쌀 때 팔면 된다.이 문제에서는 늘어난 코인만큼 다시 투자를 할 수 있으니, 상승 곡선이면 무조건 사는것이 이득이다. (늘어난 코인을 배로 불릴 수 있으니)코드 직관적으로 풀었지만 내심 불안했다.그래서 dp로도 풀어보았다. 물론, 같은 결과가 나왔고 정답이다.점화식은 dp[k] := k일까지 벌 수 있는 최대 코인이다.$i < j$ 인 $i$일째에 가진 돈으로 전부 매수하고, $j$일에 모두 매도한다면 (두 날짜 사이의 변폭) * (i일에 살 수 있었던 코인의 수)만큼 벌 수 있을것이다.

https://www.acmicpc.net/problem/5612 문제 1분 단위로 터널에 들어간 차량의 수와 터널에서 나온 차량의 수가 주어졌을 때, 터널에는 차량이 최대 몇 대 있었는가? 풀이 처음에 터널에 있었던 차량 수에서, 매분 들어간 차량의 수를 더하고 나간 차량의 수를 빼면 된다. 중간에 한번이라도 터널 안 차량의 수가 음수가 되면 0을 출력하는 것에 주의하면 정답. 코드

2014년 만들었던 심플 포스터 디자인이다. 재밌는 점은, 노트북에 적힌 코드는 9*9단이었다.