성장 일기 - Small Step

https://www.acmicpc.net/problem/11052 풀이2662번 기업투자를 푸는데...왠지 붕어빵과 비슷한 느낌이나서 다시 풀어보았다. 기업투자는 조만간 올리겠다!! 붕어빵을 어떻게 묶어 팔아야 제일 비싸게 팔 수 있느냐를 구하는 문제이다...DP문제는 글로 설명하기가 어렵다. 붕어빵이 n개 있으면 다음과 같이 생각할 수 있다.1. 처음에는 0~n개 까지 붕어빵을 묶어 팔 수 있으며, 이때 i 개를 팔았다.2. 전에 묶어판 붕어빠의 개수가 i개이면 지금 팔 수있는 붕어빵의 개수는 0~n-i이다. 이 경우의 수에서 j개를 팔았다.3. 위의 1,2 경우에서 i+j개를 팔았으므로 지금 팔 수 있는 붕어빵의 개수는 0~n-i-a개이다. 이와 같은 방식으로 팔 수있는 경우의 수가 0개가 될 때 ..

https://www.acmicpc.net/problem/4883풀이 지금까지 경로의 수나 최소값을 구하는 DP들의 풀이와 재귀 함수의 형태가 대부분 비슷하다. 함수가 시작할 때 빠져나오는 조건과 마지막에 return 사이의 구성을 어떻게 해주냐만 해주면 되는데...이게 어려운 것 같다. 처음에는 N,2 지점까지가면 이 값을 max로 하여 이 값과 비교해가면서 모든 경로를 비교하면서 답을 구했다. 이랬더니...시간 초과가 나버렷다. 나름 DP라고해서 짠건데...ㅜ,ㅠ 생각이 안 나..친구의 설명을 듣고 다시 풀었다. 우선 N,2에 도달 후 return하면서 그 전에 DP배열에 저장된 값과 지금 return된 값중에 최소값으로 DP배열에 저장하면서 올라오는 방법인데...글로 설명하기가 어려다... 중요한건..

https://www.acmicpc.net/problem/2688풀이오랜만에 알고리즘을 다시 풀었다...최근에 피파에 빠져서......ㅜ,ㅠ이건 예전에 풀었던 오르막수와 90%동일한 문제이다. 다이나믹 프로그래밍이며 이차원 배열을 통해서 풀어야된다. 이 문제에서 다음에 올 수는 맨 마지막에 있는 숫자보다 큰 수들이다. 따라서 맨 뒤의 숫자들에 따라 다음에 올 경우의 수들이 달라진다. n=1일 경우0일 경우 0과 같거나 큰 0~9의 숫자들이 올 수 있으므로 경우의 수가 101일 경우 1과 같거나 큰 1~9의 숫자들이 올 수 있으므로 경우의 수가 9....9일 경우 9와 같거나 큰 수는 9 하나이므로 9뒤에 올 수 있는 경우의 수는 1이다. 따라서 n은 1일 경우 총 경우의수가 55이다. n=2일 경우는0뒤..

https://www.acmicpc.net/problem/1520 풀이예전에 푼 문제이나 오늘 내리막길과 완~~전 비슷한 점프를 풀어서 포스팅하는김에 같이 올린다. 이 문제는 내가 처음으로 DP라는 것을 알게 되었고 메모이제이션이라는 단어를 처음 들어본 문제이다. 단순한 탐색으로 풀면은 시간초과가난다. 좀 설명하기 어려운데...나름 자세히 설명을 하겠다. 1. 해당 y x 좌표에서 현재 위치에서 작은 값으로 진행을 하면서 나아간다.2. 이렇게 작은 수로 나아가다가 y==N,x== N 지점이 되면 return 1;을 한다.3. y==N, x==N가 return되면 리턴된 값을 DP배열에 저장하고 이 함수는 DP배열을 return한다.4. 이렇게 상하좌우로 갈라지는 지점에서 그 경로에서 N,N까지 가는 경로..

https://www.acmicpc.net/problem/1057 풀이 처음에 생각한 아이디어!처음에 참가자가 16명이면 배열을 전부 1로 초기화 한다. 그리고 1이 연속으로 2개 나오면 둘 중 하나는 1로 다음 라운드에 진출시키고 하나는 0으로 탈락시킨다. 그리고 지민이와 한수는 둘이 연속으로 나올때 까지 1로 다음 라운드에 진출시킨다. 그리고 지민이와 한수가 연속으로 나오면 반복문을 멈추고 해당 라운드수를 출력한다. 다음은 라운드 진행을 표현한 그림이다. 연속된 1이 두 개이면 둘 중 아무거나 진출시키며 지민이와 한수의 번호는 무조건 다음 라운드로 진출시킨다. 이 경우 최대 참가자 수가 10만이라 최악의 경우 10만*10만의 시간 복잡도로 2초를 만족하지 못 한다.. 그래도 이렇게 설명하는 이유는??..

https://www.acmicpc.net/problem/10757 풀이 풀이라고할 것도 없다. 이건 그냥 아래 블로그의 답을 보고 이해한 다음 고대로 베꼇다. http://programmerchoo.tistory.com/40 구성은 크게 두 부분으로 나뉜다.1. 배열 reverseEx) 987 -> 789 2. 두 문자열 배열의 합reverse된 문자열의 합. 만약 올림수가 발생하면 다음 배열에 +1을 해준다. 처음 그림은 입력받은 문자열 A와 B이다. 그리고 A+B이다. A+B의 경우 올리수가 발생하면 배열 전체를 뒤로 밀어야되어 번거롭다. 그래서 Reverse함수를 만들어서 배열의 압뒤를 바꾸어준다. 그 뒤 두 배열을 더해주면 올림수가 발생하여도 다음 인덱스에 +1만 해주면 되기 때문에 매우 간편하..

https://www.acmicpc.net/problem/5427 풀이 얼마전에 풀었던 3055번 탈출과 매우 유사한 문제라 풀이를 생략한다.문제 푸는데 헛짓을 좀 해서...시간을 많이 소비했더니 피곤하다..... 궁금하게 하나 있는데...상근이가 먼저 이동하고 불이 퍼져도 맞다고 생각되는데 틀렷다.그래서 불을 먼저 퍼트리고 상근이를 이동시켯는데 맞았다....예외 케이스가 생각이 안 난다.. 그리고!!!! 탈출과 불 문제의 차이점이 하나가 있는데탈출은 다음에 물이 찰 곳으로 이동을 못 하며불은 다음에 불이 와도 바로 이동이 가능하여 불이 올 곳으로도 이동이 가능하다는 것이다. 제출코드12345678910111213141516171819202122232425262728293031323334353637383..

https://www.acmicpc.net/problem/1074 풀이 어렵지 않은 문제 같은데..맞추는데 시간이 오래걸린 문제이다. 처음에 문제에서 말하는대로 배열 채워가면서 정답을 출력하려고 하였으나...시간도 초과날 뿐만아니라 배열이 너무커서 선언도 안 되었다. 그래서 생각을 해보니 규칙이 있었다!!!! 위 사진에서 보는 것 처럼 왼쪽 위를 x라고 하며, 오른쪽 위 - 왼쪽 위 = y라고 하겠다. 그럼왼쪽 위 : x오른쪽 위 : x + y왼쪽 아래 : x + 2*y오른쪽 아래 : x + 3*y의 규칙이 있다. y는 N에 따라 계산가능하다.N은 1일때 1, 2일때 4, 3일때 16 ....과 같이 증가한다. 문제에서 예제로 주어진 3 7 7을 예로 들어보겠다.재귀 함수에서 전달되는 인자값은 3개이다...

https://www.acmicpc.net/problem/3055 Ah....재밌는 문제였으나......나한테는 너무 어렵게 접근한 나머지.........꽤 많은 시간을 소비하고..내 정답률도 많이 떨어뜨린 문제였다. 조만간 다시 풀어봐야지!!!! 풀이최단거리를 구하는 문제이므로 당연히!!!BFS를 이용해야 될 것 같다. 그래서 BFS로 접근하여 문제를 풀었다. 내 풀이에서 일반적인 BFS 문제들과 다른 점이 두 가지가 있다.1. 물이 퍼져나가는 것에 대한 BFS와 고슴도치의 이동에 대한 BFS, 총 BFS를 2번 사용해야 된다는 것.2. 물은 퍼져나가고 고슴도치는 길을 찾기 위해 탐색하는데 물과 두더지의 BFS를 무조건 한 차례씩 돌아가면서 돌리는 것이 아니라 물과 고슴도치 모두 BFS를 수행하면서 같..

https://www.acmicpc.net/problem/9935 풀이 문자열의 중간을 특정 문자열과 같으면 없애는 문제이다. 왠지 문제가 백준 1406번 에디터문제와 비슷한 것 같아 스택을 2개 놓고 두 스택으로 문자를 옮겨가면서 비교하여 비슷한 문자열이 있으면 제거하면서 출력했는데....코드 길이도 길어지고.....제출하니 시간초과가 떳다...ㅎㅎ 그래서 스택을 하나로 쓰기로 결정!!1. 우선 arr배열과 bomb 배열로 문자열을 입력받은 후 arr[bottom]배열이 bomb[0]과 같으면 arr[bottom]부터 bomb배열과 비교를 한다. 만약 같을 경우 arr배열을 인덱스 값에 bomb문자열 길이만큼 더해주어 폭탄이 정답을 저정하는 answer배열에 저장이 안 되게한다. 2. 그리고 cc44와..