링크 : https://www.acmicpc.net/problem/12933 12933번: 오리 첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다. www.acmicpc.net 문제 소요시간: 44분 18초 설계하기(접근방법) 1. 문자열을 입력받는다 2. 구현 오리의 울음 소리 : quack 한 번의 울음이 끝났다면 또 울음소리를 낼 수 있다. 오리의 수를 duck하고 선언하고 가장 오리가 많았던 순간을 duck_max라고 선언한다 오리가 한 번 울음을 마치면 재울음이 가능하다 문자열을 순회하면서 오리가 우는 동안에는 (문자열에 'q'가 옴) duck += 1을 해주고 오리가 울음을..
링크 : https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 문제 소요시간: 구현 15분, 디버깅 40분 설계하기(접근방법) 1. n과 target 을 입력받는다 2. 구현 달팽이 모양의 배열은 n* n으로 이루어져 있으며 배열의 형태는 ex) n = 7 인 경우 n - 1개만큼 49 48 47 46 45 44으로 밑으로 뻗고 43 42 41 40 39 38 까지 오른쪽으로 뻗고 32 33 34 35 36 37 위쪽으로 뻗고 26 27 28 29 3..
링크 : https://www.acmicpc.net/problem/20436 20436번: ZOAC 3 첫 번째 줄에는 두 알파벳 소문자 sL, sR이 주어진다. sL, sR은 각각 왼손 검지손가락, 오른손 검지손가락의 처음 위치이다. 그 다음 줄에는 알파벳 소문자로 구성된 문자열이 주어진다. 문자열의 www.acmicpc.net 문제 소요시간: 15분 20초(오류 검수에 시간이 좀 걸렸다) 설계하기(접근방법) 1. 왼쪽 시작, 오른쪽 시작 자판을 입력받고, 문자열을 입력받는다 2. 구현 좌측 자판을 딕셔너리로 구현 left_list = {'q': (1, 3), 'w': (2, 3), 'e': (3, 3), 'r': (4, 3), 't': (5, 3), 'a': (1, 2), 's': (2, 2), 'd..
링크 : https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 문제 소요시간 : 45분 실패(코드 수정 필요) 설계하기(접근방법) 1. n과, 각각의 에너지를 입력받는다 2. 알고리즘 해석 시작위치 : 돌 1 종료 위치: 돌 n 점프의 종류 1) 작은 점프 + 1 2) 큰 점프 + 2 3) 아주 큰 점프 + 3 식을 풀어보면 dp[2] = jump[1][0] dp[3] = min(dp[2] + jump[2][0], jump[1][1]) dp[4] = min(dp[3] + jump[3][0], dp[2] + jump[2][1], dp[1] + gj) 이런 식으로 진행될 것이다...
링크 : https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 소요시간: 실패 설계하기(접근방법) 1. n, m, 리스트, 좌표를 입력받는다 2. 알고리즘 해석 직접 모든 경우의 수를 더하면 시간을 초과할 것이다. 따라서 동적 계획법을 통해 누적합 리스트를 구해놓아야 할 것이다. 누적합에 따른 일반식은 다음과 같이 나타낼 수 있다 dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[..
링크 : https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 소요시간: 45분 메모리초과 실패 설계하기(접근방법) 1. n을 입력받는다 2. 알고리즘 해석 1의 자리 1 2 3 4 5 6 7 8 9 9 -> 1가지 (9 - 1) * 2 + 1 = 17 10의 자리 12 23 34 45 56 67 78 89 10 21 32 43 54 65 76 87 98 10, 89 -> 2가지 (17 - 2) * 2 + 2 = 32 100의 자리 1가지만 확장 가능한 수들 210 989 789 1000의 자리 1가지만 확장 가능한 수들 1010 1210 3210 8789 ..
링크 : https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 소요시간: 38분 15초 설계하기(접근방법) 1. n과 포도주를 입력받는다 2. 알고리즘 해석 grape = [6, 10, 13 ,9, 8 ,1] dp[1] = 6 dp[2] = 6 + 10 dp[3] = max(6 + 13, 10 + 13, 6 + 10) dp[4] = max(6 + 10 + 9, 6 + 13 + 9, 10 + 13) dp[5] = max(6 + 10 + 9 + 8,..
링크 : https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 문제 소요시간: 45분 10초 설계하기(접근방법) 1. n과 리스트들을 입력받는다 2. 알고리즘 해석 이중배열을 통해서 문제를 해결해야 할 것이다 이동 방향은 오른쪽 혹은 아래로만 이동하므로 전체 이중배열을 순회하면서 이동 가능한 좌표들에 한해서 이동 가능 경우의 수를 기록한다. 이와 같은 형태로 나타날 것이다 1) 현재 리스트의 위치 (graph[i][j])에서는 해당 값 만..
