BOJ 13208 - 승현이와 승현이

문제 :  https://www.acmicpc.net/problem/13208 전에는 못 풀었는데 드디어 풀었다~ state[a][b] : 조승현13이 a에 있고 조승현16이 b에 있는 상태 를 정점으로 하고 c[a] * c[b]를 정점의 비용으로 가지는 그래프를 생각해보자. 우리가 해야 할 것은 state[a][b]에서 state[b][a]로 가기 위해서 지나가는 정점들의 비용의 최대값을 최소화 하는 것이다. 만약에 문제가 정점의 비용을 최소화하는게 아니라 간선의 비용을 최소화하는 문제였다면 MST를 만들어서 구할 수 있을 것 같았다. 비슷한 아이디어로 정점의 비용이 작은 것부터 큰 것 순으로 보면서 트리를 만들어보기로 했다. 과정은 대략 다음과 같다 1. 정점을 비용순으로 정렬하고 비용이 작은 것 부터 본다. 2. 현재 보고 있는 정점이 u라고 하자 3. u와 인접한 정점들을 본다. 인접한 정점은 v라고 하자. 4. 만약 uv가 다른 집합에 속하는데 v의 비용이 u의 비용보다 작거나 같다면 uv를 같은 집합으로 합친다. 그리고 간선(u, v)를 따로 저장한다. 위 과정을 반복해서 나오는 간선들을 모으면 트리가 된다. 또한 이 트리상의 경로로만 이동하면 문제에서 요구하는 답을 찾을 수 있다. 직관적으로 이해할 수 있으므로 증명은 생략한다. 이제 문제는 트리에서 두 정점을 연결하는 경로상에 있는 정점의 비용 중 최대값을 찾는 문제로 바뀐다. 이건 LCA 를 이용하면 각 쿼리를 O(lgN)에 처리할 수 있다. 문제를 푸는 총 시간 복잡도는 시간 복잡도는 아마 O(N(N+M)+QlgN)이 될 것 같다. (먼저 맞은 사람들 코드를 보니깐 더 빠른 방법이 있나 보다.) 코드 :  http://ideone.com/eBn2sQ

BOJ 11478 - 서로 다른 부분 문자열의 개수

길이 N인 문자열 S의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP O(NlgN)에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 O(N^2)에 해결할 수 있다. 트라이에 S{N(N + 1)} \over 2개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 O(N^2lgN)에 해결할 수 있다. S{N(N + 1)} \over 2개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n

Lazy propagation 안쓰고 구간 업데이트 쿼리 처리하기

일반적인 구간 업데이트 쿼리 처리 문제는 Lazy propagation을 구현한 세그먼트 트리로 풀 수 있다.  좀 더 특수한 경우의 문제로 먼저 구간 업데이트 쿼리가 쭈~욱 주어지고, 업데이트 쿼리의 중간에는 다른 쿼리를 처리할 필요가 없는 문제를 생각할 수 있다. 이런 경우의 문제는 구간 업데이트 쿼리를 각각 O(1)에 처리할 수 있다. 길이 N인 배열 A가 주어졌다고 하자. 편의상 인덱스를 1 \sim N으로 쓰고 A[0]에는 0이 들어있다고 생각하자. 그리고 다른 배열을 정의하겠다. S[i] : 구간 업데이트 쿼리에 의해 A[l, \infty]에 일정하게 더해진 값 P[i] : A[0] ~ A[i]의 구간합 만약 S를 알고 있다고 하면 P[0] = 0 P[i] = P[i - 1] + S[i] + A[i] 가 된다. S는 구간 쿼리가 구간 [l, r]x를 일정하게 더해라는 식으로 들어오면 S[l]x를 더하고 S[r + 1]x를 빼서 처리할 수 있다. 설명하려고 SP를 따로 썼지만 실제 구현에서는 하나의 배열로 처리해도 무방하다.  -------------------------------------------------------------- 관련 문제 http://codeforces.com/gym/100571/problem/B https://www.acmicpc.net/problem/12746

블로거에 마크다운으로 글 작성하기

http://dillinger.io/ 저기서 마크다운으로 작성한 다음에 HTML로 바꿔서 적으면 된다 테스트 : Untitled Document.md Hello World Hello world Hello world apple banana italic bold npm start show me the money black sheep wall function sayHello ( ) { console .log( 'hello world' ); } sayHello(); for ( int i = 0 ; i < n; ++i) { puts ( "Hello World" ); } <addr> 뭔가 애매하게 되는데 만족스럽다.

BOJ 2401 - 최대 문자열 붙여넣기

문제 :  https://www.acmicpc.net/problem/2401 각각의 짧은 문자열들이 긴 문자열에서 어디에 등장하는지만 알 수 있다면, 이 문제는 전형적인 다이나믹 프로그래밍 문제가 된다. 그러니깐 KMP를 돌리면서 테이블을 채우면 된다. 시간 복잡도는 긴 문자열 길이 S, 짧은 문자열 길이 T, 짧은 문자열의 수 N이라 할때 O(N * (S + T))가 된다. 코드 :  http://ideone.com/zloOUb

BOJ 1034 - 램프

문제 :  https://www.acmicpc.net/problem/1034 램프에 K번의 조작을 다 하고 나서 최종적으로 몇 개의 행의 불이 완전히 켜져있다고 생각해보자. 불이 완전히 켜져있는 행들은 초기에 서로 켜져있는 불의 상태가 완전히 같았어야한다. 왜냐하면 램프에 가해지는 조작은 열 단위로 가해지기 때문이다.  위 사실을 알고나면, 문제를 이렇게 생각할 수 있다. K번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는가? 만약에 켤 수 있다면 그 행과 똑같이 생긴 행의 수를 답으로 고려해 볼 수 있고, 최종 답은 그러한 행의 수 중 최대가 된다. 이제 K번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는지를 알 수 있으면 되는데, 이는 처음에 꺼져있는 열의 수보다 K가 크거나 같을 때 홀짝만 잘 따지면 알 수 있다. 코드 :  http://ideone.com/tcrFIU

BOJ 1727 - 커플 만들기

문제 : https://www.acmicpc.net/problem/1727 더 쉬운 문제로 남녀 모두 k명이 있는 문제를 생각해보자. 이 경우는 두 집합을 각각 정렬한 뒤 그 순서에 맞게 매칭을 시키면 최적이 된다. 본 문제는 남자 n명, 여자 m(n >= m 이라 가정)이라 할때, 매칭될 남자 m명을 고르는 문제로 생각할 수 있다. 남녀 집합을 모두 정렬하고 테이블을 아래와 같이 정의하자. D[i][j] : 남자 i번, 여자 j번까지 매칭(j쌍 커플) 했을 때 최소 성격 차이의 합. 상태전이는 LCS와 비슷하게 시켜주면 된다. 코드 : http://ideone.com/ehzO4C