kthng

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가 생겨 이 방법으로는 불가능하다.세준이가 내리막길로만 이동하기 때문에 가능하다.

boj 1935 : 후위표기식2 https://www.acmicpc.net/problem/1935 자료구조시간에 단골로 나올 법한 문제이다. 1. 피연산자가 나오면 stack에 push,2. 연산자가 나오면 stack의 위에 2개를 연산한 후 push 위의 과정을 반복한다. ABC*+DE/- 와 같은 후위표기식을 우선 저장해놓고, 아스키코드 배열에 정수값을 입력받은 후 stack에서는 value만으로 모든 연산을 진행하였다.

boj 1978 : 소수 찾기 https://www.acmicpc.net/problem/1978 에라토스테레스의 체를 이용하여 1000 이하의 자연수 중의 소수를 구하고,주어진 수들 중 소수의 갯수를 센다. for i = 2 ; i * i

boj 1003 : 피보나치 함수 https://www.acmicpc.net/problem/1003 introduction to dynamic programming이라는 책이 있다면 앞부분에 수록될만한 문제이다. 1. fibonacci[n][0] : fibonacci(n)이 0을 호출하는 횟수2. fibonacci[n][1] : fibonacci(n)이 1을 호출하는 횟수 위와같이 두면, 3. fibonacci[n][0] = fibonacci[n-1][0] + fibonacci[n-2][0]4. fibonacci[n][1] = fibonacci[n-1][1] + fibonacci[n-2][1]

boj 1874 : 스택 수열 https://www.acmicpc.net/problem/1874 스택수열은 큐와 스택으로 해결된다.1. Ai : i번째 문자2. queue : 1~N까지 순서대로 담켜있다.3. stack : stack의 top은 0.- 여기까지가 전처리. 1. Ai가 queue의 front보다 같거나 작을 때까지 queue를 pop하고 stack에 push.;2. Ai가 stack의 top과 같으면 pop.3. i++ 1,2,3의 과정을 반복하면 답을 구할 수 있다. 올바르지 않은 수열은 어떻게 구할 수 있을까?stack의 top보다 Ai가 작다면 만들어질 수 없는 스택수열이다. stack의 top보다 Ai가 작으면 stack의 pop 과정이 이루어진 후에 Ai를 pop할 수 있는데, 이..