-

제곱 ㄴㄴ 수https://www.acmicpc.net/problem/1016 [문제 풀이] min과 max의 범위를 살펴보면, 1

욕심쟁이 판다 1937 https://www.acmicpc.net/problem/1937 map[][]에 대나무 숲 정보를 다 집어넣고 map[1][1]부터 dfs로 이동 가능한 곳 모두 탐색한 뒤 최댓값 출력하면 될것같은데...알고리즘 공부하던 초창기에 푼거라 빙빙 돌아간 것 같다.. 어쨋든, 코드를 설명하자면 1. bamboo[][] 배열에 입력받은 정보들을 집어넣는 동시에 ArrayList al에도 집어넣는다. 2. al을 대나무 양을 기준으로 sort 한다. 3. al에 들어있는 정보들을 하나씩 get 해와서 탐색한다. 4. 탐색 종료 후 최댓값을 찾아서 출력한다.이렇게 된다... 예전에 풀었던 문제를 다시 보니 뭔가 실력이 향상된것 같아 뿌듯하다. 물론 코딩테스트는 다 떨어졌지만..ㅠ__ㅠ 12..

2186 문자판 https://www.acmicpc.net/problem/2186 [문제 풀이] 문제 분류는 BFS라고 되어 있으나, 나는 DFS와 DP를 이용해서 풀었다.나는 이 문제를 푸는 아이디어를 1937번 욕심쟁이 판다에서 얻었다. 신경써야 할 점이 있다면 1. 한번에 K칸씩 직선으로 움직일 수 있다 2. BREEZE와 같이 같은 단어가 있는 문자열을 어떻게 처리할 것인가두 가지 정도로 생각할 수 있다..

연속합 1912https://www.acmicpc.net/problem/1912 [문제 풀이]dp[i]를 index가 i일때의 연속합이라고 정의하면 dp[i] = max(ar[i], dp[i-1]+ar[i])이런 점화식을 구할 수 있다. 우선 10개의 숫자가 입력됐을 때 방금 구한 점화식으로 연속합을 구해보면index 1 2 3 4 5 6 7 8 9 10 입력 10 -4 3 1 5 6 -35 12 21 -1 연속합10 6 9 10 15 21 -14 12 33 32 표와 같고, 연속합의 최댓값은 index가 9일때 33(12+21)이라는 것을 알 수 있다. 계산을 모두 마친 후, dp배열에 저장된 연속합들 중 가장 큰 값을 출력하면 끝!! 1234567891011121314151617181920212223..

자두나무 2240 https://www.acmicpc.net/problem/2240 [문제 풀이]dp[T][W] 2차배열 생성하고,dp[T][W]는 T초에 W번 이동했을 때 먹은 자두의 개수 라고 했을 때W % 2 == 0일때 dp[i][j] = jadu[i] == 1 ? Math.max(dp[i-1][j-1] + 1, dp[i-1][j]+1) : dp[i-1][j];W % 2 == 1일때 dp[i][j] = jadu[i] == 2 ? Math.max(dp[i-1][j-1] + 1, dp[i-1][j]+1) : dp[i-1][j]; 연산을 마치고 dp[T][0] ~ dp[T][W] 중 최댓값 출력 123456789101112131415161718192021222324252627282930313233343..

1학년 5557https://www.acmicpc.net/problem/5557 [문제 풀이]눈여겨 볼 점은 계산을 하다보면 범위가 int형 범위를 넘어갈 수도 있다는 점.상근이가 아는 수는 다행히 0부터 20까지라는 점이다. 1. 숫자의 개수 N을 입력받고 2. 다음 줄에 나오는 N개의 숫자를 long형 ar[]배열에 집어넣는다. 3. 2차원배열 dp[N+1][21]를 생성한다. 어떻게 풀어나갈 생각이냐면.... dp[i][j]를 'i번째 수 까지 계산을 했을 때 j를 만들 수 있는 경우의 수'로 생각한다. 예를들어, dp[1][8] = 1 (8 = 8) dp[2][5] = 1 (8 - 3 = 5) dp[2][11] = 1 (8 + 3 = 11) 이다. 4. dp[i-1][]와 dp[i][]와의 관계를..

케빈 베이컨의 6단계 법칙 1389https://www.acmicpc.net/problem/1389 [풀이 방법]이 문제 역시 dfs, bfs, 플로이드 와샬 알고리즘 등 다양한 방법으로 풀 수 있다.난 플로이드 와샬 알고리즘으로 풀어봐야지... 가장 간단한 방법인 것 같다. 1. 첫째 줄에 N과 K를 입력받는다. N은 정점, K는 간선의 수라고 생각했다. 2. relation이라는 N+1 X N+1 행렬을 생성 후 이후에 나오는 간선 정보들을 저장했다. 여기서, 1이 3을 알때 3도 1을 안다고 볼 수 있으므로 relation[1][3] = 1 relation[3][1] = 1 을 해준다. 3. 탐색을 시작한다.relation[r][k] != 0이고 relation[k][c] != 0 일때 -relat..

경로 찾기 11403https://www.acmicpc.net/problem/11403 [문제 풀이] 이 문제를 푸는 방법은 여러 가지가 있다. 나는 bfs, dfs, 플로이드 와샬 알고리즘 중 플로이드 와샬 알고리즘을 이용해 풀었다.플로이드와샬 알고리즘은 형태가 정해져있기 때문에 모든 경로를 탐색하는 문제에 적용하기 쉬운 것 같다. 1. 모든 입력은 0과 1로 이루어져있다. 나는 입력을 받은 후 int형으로 바꾸지 않고 String형 그대로 map에 저장했다. 2. 정점 r에서 k로 가는 경로가 존재하고, 정점 k에서 c로 가는 경로도 존재한다면 정점 r에서 c로 가는 경로 또한 존재한다고 볼 수 있기 때문에 map[r][c]를 1로 설정해 주면 된다. 3. 탐색을 모두 마치고 출력하면 끝. 12345..

K번째 수 11004https://www.acmicpc.net/problem/11004 [풀이]숫자의 최대 입력 개수가 꽤 크다.수 정렬하기 3번 문제가 생각나서 비슷하게 풀려고 했으나 입력받은 수의 범위가 -10^9 < A < 10^9여서 포기.정렬 하면 분명히 시간초과걸릴텐데.... 하며 고민하던 중퀵소트를 변형해서 풀어보기로 했다. 설명하기가 좀 애매한 관계로 소스코드를 참고해 보자 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.io.BufferedReader;import java.io.InputStreamReader;i..

수 정렬하기 3 10989https://www.acmicpc.net/problem/10989 [풀이 방법]무턱대고 정렬 알고리즘으로 정렬을 시도했다간 시간초과 나기 십상이다. 퀵소트로 해도.그도 그럴것이 정렬해야 하는 숫자의 개수가 최대 10000000개 니까 정렬 말고 다른방법으로 풀어야한다. 여기서 힌트를 얻은 곳은 입력되는 수가 최대 10000이라는 것!크기 100001 짜리 배열 ar을 생성한 후 입력받은 숫자의 인덱스의 값 ar[index]를 1 증가시켜준다. 입력을 다 받았으면 ar[1]부터 ar[10000]까지 해당하는 값 만큼 index를 출력해준다. 1234567891011121314151617181920212223import java.io.*; class Main { public sta..