Profile cover photo
Profile photo
Hongjun Jang
13 followers -
Korea Univ. CS undergraduate
Korea Univ. CS undergraduate

13 followers
About
Posts

Post has attachment
Computational Geometry
2002 메릴랜드 대학교 계산기하학 수업자료 스탠포드 대학교 계산기하학 수업자료 Computational Geometry Algorithms and Applications, Cimec Book
Add a comment...

Post has attachment
Latin America Regional Contests 2010 G번(BOJ 5699번)
문제 링크(acmicpc.net 5699번) Aho-Corasick 알고리즘으로 풀 수 있다. 주어지는 입력 문자열들로 트라이를 구성하고, 기존의 노드(x)에서 새로 뻗어나가는 노드(y)의 실패링크(yf) 걸어줄 때 d[y] = max(d[x], d[yf]) + "노드 y에서 끝나는 string의 개수" O(   문자열의 길이의 합 ) 에 해결할 수 있다. 내 소스 코드
Add a comment...

Post has attachment
Coder's High 2013 J번 Bookthief
평범한 0-1냅색이라고 가정하면 다음과 같은 DP식을 세울수있다: D [ N , V ]  := N종류의 아이템에 대해 고려해서, V칸을 채웠을때의 최대 값어치 D [ N , V ] = m a x { D [ N − 1 , V ] , D [ N − 1 , V − (volume of item) ] + (value of item) } v i = (volume of item) ,  c i = (value of item) 이라고 하고, 아이템의 갯수를  k i 라 하...
Add a comment...

Post has attachment
KOI 2005 고등부 3번 - 소방차
문제 링크 우선 가장 쉬운 건 O(NM)의 dynamic programming. D(i, j) = min(D(i-1, j), D(i,j-1), D(i-1,j)+|P(i)-F(j)|). D(i-1, j)랑 D(i, j-1)을 참조할 때는 min(i-1, j-1)+1과 같은 지 확인하면서 compute하면 된다. 그런데 사실 해법은 dynamic programming과는 다르게 greedy method이다. 펌프 2개 P1<P2가 있고, 소방차 2개 F1<F2...
Add a comment...

Post has attachment
Croatian Olympiad in Informatics 2009 OTOCI
문제 링크(Problem Link) 주어진 쿼리를 수행하다보면 최종 그래프의 형태가 Forest가 된다. 따라서 Heavy-Light Decomposition이나 Link-Cut Tree로 그래프를 모델링하여 각 쿼리마다 수행되는 시간을 줄여볼 수 있다. 그런데 나는 조금 다르게 접근하여 보다 쉽게 풀었다. 우선 쿼리를 다 저장하여두고, 최종 그래프가 어떤 형태인지 알아낸다. 거기서 각 트리마다 dfs를 순회하면서 chain을 표시하고, 인접한 chain의...
Add a comment...

Post has attachment
IOI 2007 Sails
Observation 1 The inefficiency of a level is determined by the number of sails at that level. The order of the masts does not matter, so we can rearrange them in ascending order of height. Greedy strategy: Place the sails from front (shortest) mast to rear ...
Add a comment...

Post has attachment
TODO: 20150705
KOI 2007   고등부  2번 3번 KOI 2009   고등부  2번 2012 Arab Collegiate Programming Contest  J번 Baltic Olympiad in Informatics   2015  6번
Add a comment...

Post has attachment
USACO US Open 2015 Contest Gold - Palindromic Paths
문제 링크(Problem Link)   우선, 첫 번째로 관찰할 수 있는 게 주어진 그리드가 N by N이어서 생성되는 string들의 길이는 항상 (2N-1)이다. 따라서 길이는 항상 홀수이며 그 가운데에 위치하는 문자는 그리드에서 오른쪽 위에서 왼쪽 아래로 내려가는 대각선 위에 위치하게 된다.   여기서 착안해서 다음과 같이 DP Table을 정의할 수 있다.   D(L , a , b) = 가운데에서 양쪽으로 뻗어나가는 길이가 현재 L이고, 왼쪽으로 L...
Add a comment...

Post has attachment
JAG Spring Contest 2013 E번 / KOI 2014 고등부 4번
문제 링크 (Problem Link) 주어진 그래프에서 MST G(m)이 있다고 하자. G(m)에 포함되지 않은 간선을 자르는 경우에만 Gi가 현재 MST의 weight sum(=S)과는 다른 값을 가지게 된다. i번째 간선을 자르면 G(m)은 이분 그래프가 되는데, 이 때 두 subgraph를 연결하는 가장 작은 간선을 골라주면 되는 것이다. Kruskal Algorithm을 기반으로 MST를 구성했다고 가정하자. MST에 포함되지 않는 간선들을 가중치 ...
Add a comment...

Post has attachment
Number Theory
2013/2학기 응용정수론 청강 중 필기 내용. 모듈러, 오일러 정리, 확장 유클리드 알고리즘, 오일러 파이 함수, 뫼비우스 함수와 반전 공식, 뤼카의 정리. Dropbox - PDF FIle
Add a comment...
Wait while more posts are being loaded