kthng

codeground : 프리랜서 [SCPC 2016 - 2차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=31 간단한 DP로 해결할 수 있다.일하는 데 일주일이 걸리는 P사의 각 주당 금액 을 Pi, 이주일이 걸리는 Q사의 각 주당 금액을 Qi라 하고, i번째 주에 받을 수 있는 가장 큰 금액을 Ai라 한다면, Ai = max(Ai-1+ Pi, Ai-2 + Qi) 위와같은 단 하나의 점화식으로 DP를 구성하면 가뿐하게 AC를 받을 수 있다.

codeground : 대피소 [SCPC 2016 - 1차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=28 떠올릴 수 있는 가장 간단한 방법은 v번의 다익스트라를 하는 것. 하지만 이 방법은 간단히 시간초과임을 알 수 있다. 그렇다면 다른 해결방법이 있을까? 이 문제는 단 한번의 다익스트라로 해결이 가능하다.heap에 모든 대피소를 넣고 시작하면 된다. 또한, 경로의 길이가 같을 경우 대피소번호가 작은 대피소를 선택하는 것도 동시에 해결해주면 된다. 알고리즘을 간략히 써보면, 1. 새로운 경로가 더 작으면 힙에 push. dist 갱신 위에께 일반적인 다익스트라 알고리즘이라면, 이문제에 해당하는 알고리즘은 다음과 같다. 1. 새..

codeground : 캠퍼스와 도로(1) [SCPC 2015 - 1차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=15 SW역량테스트를 맞아 codeground문제들도 써보려고 한다.그 첫번째 문제..이 문제는 v번의 다익스트라 알고리즘으로 떠오르는 아이디어 그대로 해결할 수있다.시간복잡도는 v*(v+e)log(v+e)가 되어 시간안에 충분히 해결할 수 있을 듯 하다.다만, 방문하는 도시까지의 거리가 같을 때가 문제 ㅜㅜ...힙에 push하기 전에 방문노드를 체크해주면 왜안되는지 모르겠다. 아직 밝혀내지 못했음... 해결한 방법은, 코드가 조금 길어지긴하지만 스타팅 지점인 v번째 도시에 대해 다익스트라 알고리즘으로 모든 경로까지..

boj 2381 : 최대거리 https://www.acmicpc.net/problem/2381 n^2만에 해결할 수 있는 방법은 간단히 떠올릴 수 있다. 하지만 n이 최대 50000이기 때문에 시간초과. nlongn 이하의 해결법을 찾아야한다. 답은 (x+y의 최대값) - (x+y의 최소값), (x-y의 최대값) - (x-y의 최소값) 둘 중 큰값이 답이다.응??? 증명을 해보자.1. (x+y의 최대값) - (x+y의 최소값)이 답일 경우1.1 앞 괄호를 (x1,y1), 뒷 괄호를 (x2,y2)라 두면,1.2 x1 > x2이고, y1 > y2의 경우만 가능하다.1.3 그렇다면 만약 x1 < x2이거나 y1 < y2라면? 답에 모순이 생기지 않을까?x1 < x2이거나 y1 < y2라도 상관없다는것을 증명해..

boj 1238 : 파티 https://www.acmicpc.net/problem/1238 시간초과가 나지 않겠나? 라는 의문을 가졌지만, 잘 생각해본다면 단 두번의 다익스트라로 해결이 가능하다.^^.. 우선 파티장소에서 모든마을까지는 단순한 다익스트라의 구현으로 구할 수 있다.그렇다면 각각의 마을에서 파티장소까지의 경로는 어떻게 구할 수 있을까?답은 경로를 거꾸로 저장한 edge를 저장하는 것으로 해결 가능하다.a->z 경로의 최단거리는 반대경로의 최단거리와 같다. 호기심에 floyd로 시간초과인지 테스트해보았지만 역시나 시간초과^^

boj 11060 : 점프점프 https://www.acmicpc.net/problem/11060 삼성 코드그라운드에서도 비슷한 문제를 본 기억이 있다. 해결방법은 간단하다. dist[i]를 i번째 돌까지의 최소 점프 횟수, a[i]는 i번째 위치의 점프력이라고 두면 1. dist[j] = min(dist[j],dist[i] + 1) { i+1

boj 2343 : 기타 레슨 https://www.acmicpc.net/problem/2343 얼핏 보면 간단하지만, 아이디어가 쉽게 떠오르지 않아 고생했던 문제이다.ㅜㅜ 1. f(a) : 블루레이 크기가 a일 때 M개 모두 녹화할 수 있는가? true or false2. f(a)가 true인 최소의 a값이 답이다. 이분탐색을 이용하면 시간안에 문제를 해결할 수 있다.f()의 시간복잡도는 n, 이분탐색의 시간복잡도는 logn이므로 총 시간복잡도는 nlogn이다.

boj 11501 : Stock(주식) https://www.acmicpc.net/problem/11501 언뜻 간단해보이지만 아이디어를 떠올리기가 쉽지만은 않은 문제이다. a[i]를 i번째 주식의 가격이라 할 때, i번째를 산다면 얼마에 팔 수 있는가?term_max를 팔게될 가격이라고 한다면, 1. term_max = max(a[k]) {k = i~n} 그렇다면 이득은 얼마인가? 2. i번째 얻는 이득 : term_max - a[i]; 위 알고리즘의 시간복잡도는 n이다.

boj 10453 : String Transformation (문자열 변환) https://www.acmicpc.net/problem/10453 A,B는 모두 좋은문자열이다.그러므로 A 에서 B로 바꾸는 과정은 모두 좋은문자열이다. 왜그럴까?A가 좋은 문자열이면 임의의 위치 i를 잡는다면 i전까진 b보다 a가 많고, i부터 끝까진 a보다 b가 많기 때문.따라서 A,B모두 좋은 문자열이라면 A에서 B로 최소이동으로 바꾸는 경로 또한 모두 좋은문자열이다.(정확한 증명은 안되었다..ㅜㅜ 직관적으로....) 그렇다면 이제, A를 B로 옮기기 위한 최소 이동횟수를 구해보자.예제의 aabbabab -> aaaabbbb 를 생각해보자.편의를 위해 b를 공백으로 생각하고, a만을 움직인다 생각해도 문제는 변함이 없다...

boj 10814 : 나이순 정렬 https://www.acmicpc.net/problem/10814 stable sort란 무엇인가? 라는 문제와 같다.stable sort란, 정렬을 하되 정렬값 순서를 제외한 순서는 바꾸지 않는 sorting방법이다. merge sort로는 간단하게 구현할 수 있고, quick sort에선 stable sort를 위한 모종의 작업이 필요하다. 다행히 c++과 java에선 stable_sort를 지원해서 문제를 풀 때엔 라이브러리를 이용하면 된다.