Dolphins의 HelloWorld

문제링크 : https://www.acmicpc.net/problem/1912 연속한 숫자중에 최대치를 구하는 문제이다. 처음으로 문제를 풀 때는 수열을 돌면서 음수가 나오면 그 전까지의 합계를 저장하고 만약 합계가 0보다 작을 떄는 합계를 다시 초기화하여 그 다음부터 다시 합계를 시작하고 저장하는 식으로 문제를 풀었다. #include #include #include #define SIZE 1000001 using namespace std; int arr[SIZE]; int main() { memset(arr, -1, sizeof(int)*SIZE); //모든 수를 -1로 초기화 long long n; scanf("%lld", &n); //받을 숫자의 갯수 for (int i = 1; i

문제를 보고 곰곰히 생각하다보면 숫자가 1, 2, 4 로 표현된다는 차이만 있을 뿐 수가 나타내어지는 원리는 3진법을 표현하는 방식과 같다는 것을 알 수 있다. 다만 유의해야할 점은 기존 n진법과는 다르게 숫자가 0이 아니라 1부터 시작된다는 점이다. 이를 보정하기 위한 방법이 여러가지가 있는데 나는 n%3 = 0 인 경우에 n에서 3을 뺴준 상태에서 3을 나눠주는 방식을 사용하였다. #include #include using namespace std; string solution(int n) { string answer = ""; do{ if(n%3 == 0){ answer = "4" + answer; n = n-3; } else if(n%3 == 1){ answer = "1" + answer; } e..

난이도가 매우 쉬운 문제이다. 변수를 저장하는 공간 tmp를 할당한 후 arr을 처음부터 끝까지 도는 for문을 실행하는 동안 해당 arr[i]를 tmp에 저장하고 다음 arr[i+1]이 tmp와 같다면 저장하지 않고 넘어가는식 으로만 코드를 짠다면 문제를 푸는데 큰 문제가 없다.

문제링크 : https://www.acmicpc.net/problem/11054 #include #include #include using namespace std; int A[1001]; int B[1001]; int memo1[1001]; int memo2[1001]; int main() { int n; scanf("%d", &n); for (int i = 1; i A[j] && memo1[i] B[j] && memo2[i] < memo2[j] + 1) { memo2[i] = memo2[j] + 1; } } //기존의 LIS 방식으로 각 배열의 수 까지의 최대 수열의 길이 구하는 과정 if (memo2..

LIS 알고리즘을 통해 푸는 문제이다. 동적할당법을 통해 풀게되는데 문제에 있는 예제를 통해 살펴보자. 먼저 A = [10,30,10,20,20,10] 에 대응하는 가장 긴 수열의 길이를 저장하는 memo배열을 할당한다. A[1] 은 첫번째 배열이며 최장 부분수열의 길이도 1이 된다.(편의상 A[0]이 아닌 A[1]이 첫번째 배열이라고 가정한다.) A 10 30 10 20 20 10 memo 1 다음으로 A[2]는 30이며 먼저 기본적으로 가지는 수열의 길이인 1을 먼저 할당한다. 그 후 앞에 있는 배열을 검사한다. 감소하는 수열의 길이를 구하는데 앞에있는 A[1]은 A[2]보다 작으므로 A[2]까지 최장 부분수열의 길이는 1에서 변화없이 끝나게 된다. A 10 3010 20 20 10 memo 1 1 ..

문제링크 : https://www.acmicpc.net/problem/11053 LIS알고리즘이 적용되는 과정에 대한 이해가 필요하다면 : http://dolphins-it.tistory.com/82 참조 #include #include #include #include using namespace std; int A[1001]; int memo[1001]; int main() { int n; scanf("%d", &n); for (int i = 1; i

#include #include #include #include #define SIZE 10001 using namespace std; int arr[SIZE]; int memo[3][SIZE]; // 0 -> 0번 연속인 경우 // 1 -> 1번 연속인 경우 // 2 -> 2번 연속인 경우 int main() { int n; scanf("%d", &n); for (int i = 1; i

문제풀이 x x o x -> 0번경우 o -> 1번경우x -> 2번경우 o o -> 이 경우는 조건에 맞지 않으므로 pass memo[a][b] 에서 b는 경우의 수, a는 어떤 열인지 나타내는 용도로 사용하자. #초기값 memo[0][0] = 0 (둘다 x이므로) memo[0][1] = arr[0][1] (첫 열에서 밑에 스티커의 점수를 그대로 가져옴) memo[0][2] = arr[0][2] (첫 열에서 위의 스티커의 점수를 그대로 가져옴) #점화식 1. 다음에 나올 경우가 0번 경우일 떄 memo[a][0] = max(memo[a-1][0], memo[a-1][1], memo[a-1][2]) -> 그 전까지 누적된 경우 중에 가장 큰 것을 가져옴 2. 다음에 나올 경우가 1번 경우일 때 memo[a..

대표적인 Dynamic Programming 문제이다. 좀더 자세한 풀이가 필요하다면 Baekjoon 11726문제를 참조하자 #include #include #define mod 1000000007 using namespace std; long long memo[60001]; int solution(int n) { long long answer = 0; memo[0] = 0; memo[1] = 1; memo[2] = 2; for(int i=3; i

적당한 함수의 활용을 통해 적은 코드의 길이로 결과를 출력할 수 있는 문제이다. 문제를 읽어보면 vector에 있는 각 원소의 특정 인덱스를 비교하면서 정렬을 해야함을 알 수 있다. 고로 그냥 순수하게 정렬알고리즘을 구현하면 다음과같은 코드가 나온다. #include #include #include using namespace std; vector solution(vector strings, int n) { vector answer; int len = strings.size(); for (int i = 0; i strings[j][n]) swap(strings[i], strin..