kthng

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할 수 있는데, 이..

boj 9935 : EKSPLOZIJA(문자열 폭발) https://www.acmicpc.net/problem/9935 시간초과를 저격한 문제.1. 폭파문자가 있으면 폭파문자를 제거한다.2. 폭파문자가 없을 때까지 1의 과정을 반복한다 위의 방법으로 하면 시간초과.다른방법을 생각해보아야 한다. stack을 통해 구현하면 보다 편하다.1. stack에 문자열을 담아간다.2. stack의 윗부분이 bomb와 일치하면 bomb부분을 제거한다. 위의 방법으로 해결하면 문제가 풀린다.stack의 윗부분이 bomb와 일치하는지 확인하는 과정도 bomb size의 만큼의 시간복잡도가 필요한데, 이 부분은 character 말고 int도 함께 stack에 쌓아주는 방법으로 접근하면 보다 빠르게 풀 수 있다. stack..