kthng

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를 지원해서 문제를 풀 때엔 라이브러리를 이용하면 된다.

boj 1036 : 36진수 https://www.acmicpc.net/problem/1036 힘이 많이 들어가는 문제인 듯 싶다.내가 구현한 방법은 +,-,

boj 1915 : 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 2가지 방법으로 풀었다.첫번째 방법은 sum을 이용하여 해결하는 것.sum[i][j]를 sum{ a[u][v] } (u는 1~i까지, v는 1~j까지)sum[i][j] - sum[i-k+1][j] - sum[i][j-k+1] + sum[i-k+1][j-k+1] == k*k 일때 한변의 길이가 k인 정사각형이다. 아래의 사진을 보면 참고가 될지도 모르겠다. 하지만 위의 방법은 아슬아슬하게 시간초과를 면한다. 시간복잡도는 n*m*min(n,m)이다. 두번째 풀이법은 다른사람들의 코드를 보고 나서야 떠올릴 수 있었는데, c[i][j]를 i,j를 오른쪽 아래로 둘 때의 가장 큰 정사각형이라고 생각하자. 그러면..

boj 11049 : 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 divide&conquer와 메모이제이션을 이용하여 해결하였다.a[i][1] : i번째 행렬의 row, a[i][2] : j번째 행렬의 col.위와같이 두면, 1. f(i,j) : i번째 행렬에서 j번째 행렬까지의 최소 곱셈 수2. f(i,j) = min { f(i,i) + f(i + 1,j) + a[i][1]*a[i+1][1]*a[j][2] , f(i,i+1) + f(i+2,j) + a[i][1]*a[i+2][1] + a[i][1]*a[i+2][1]*a[j][2], ... , f(i,j-1) + f(j,j) + a[i][1]*a[j][1]*a[j][2] } 중복된 연산을 제거하기 위해 f(i,j)를..

boj 2011 : 암호코드 https://www.acmicpc.net/problem/2011 a[i] : i번쨰 숫자c[i][1] : i번째를 1개로 인식할 때의 경우의 수.c[i][2] : i번째를 2번째 숫자로 인식할 때의 경우의수위와 같이 두면,1. c[i][1] = c[i][2] + c[i][1] (a[i] 는 0이 아닐 때)2. c[i][2] = (a[i - 1] == '1' || a[i - 1] == '2' && a[i]

boj 1520 : 내리막 길 https://www.acmicpc.net/problem/1520 메모이제이션을 적용한 재귀함수로 문제를 해결할 수 있다. 1. f(1,1) = 12. f(i,j) = f(i,j - 1) + f(i, j + 1) + f(i - 1,j) + f(i + 1,j) 만약 세준이가 평지도 이동하였다면 재귀에 loop가 생겨 이 방법으로는 불가능하다.세준이가 내리막길로만 이동하기 때문에 가능하다.