카카오 모의 테스트

2018 1ST KAKAO BLIND DEMO TEST

https://programmers.co.kr/competitions/35/welcome-kakao


1, 2, 3번은 너무 간단하니 생략한다.

<4번 문제>
1 또는 0으로 채워져있는 배열이 주어진다.
이 배열에서 찾을 수 있는 가장 큰 정사각형을 구하는 문제이다.

$O(NM\cdot logT)$으로 풀린다.
구간 합을 구한후에 각 정점위치에서 이분탐색으로 가장 큰 정사각형을 구해주었다.

여기서 약간의 최적화를 해야 효율성 검사에서 시간초과가 나지않는데
이미 지금까지 구한 최대 정사각형보다 큰 범위를 탐색해주게 하면 된다.
<더빠른 방법 있으면 댓글로 달아주세요!!!!>

#include<vector> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; int sum[1001][1001]; int solution(vector<vector<int>> board){     memset(sum,0,sizeof sum);     int N = board.size(), M =board[0].size();     for(int n=0;n<board.size();++n){         for(int m=0;m<board[n].size();++m){             sum[n][m] += board[n][m];             if(n-1>=0)                 sum[n][m] += sum[n-1][m];             if(m-1>=0)                 sum[n][m] += sum[n][m-1];             if (n - 1 >= 0 && m - 1 >= 0)                 sum[n][m] -= sum[n - 1][m - 1];         }     }     int ans = 0;     for (int n = 0;n < N;n++) {         for (int m = 0;m < M;m++) {             int l = 1, r = min(N - n, M - m);             if(r <= ans) continue;             while (l <= r) {                 int mid = (l + r) >> 1;                 if (sum[n + mid - 1][m + mid - 1] - sum[n + mid - 1][m - 1] - sum[n - 1][m + mid - 1] + sum[n - 1][m - 1] == mid*mid)                     l = mid + 1;                 else r = mid - 1;             }             ans = max(ans, r);         }     }     return ans*ans; } Colored by Color Scripter

cs

<5번 문제>

N행 4열로 구성된 땅이있다.

한행씩 내려오는데 같은 행을 연속해서 밟을 수는 없다.

밟은 땅들의 값의 최대 합을 구하는 문제이다.

간단한 DP문제다.

#include <cstdio> #include <algorithm> #include <cstring> #include<vector> using namespace std; int N; int land[100001][4]; int dp[100001][4]; int solve(int y, int x) {     if (y == N) return 0;     int &ret = dp[y][x];     if (ret != -1) return ret;     ret = 0;     for (int n = 0;n < 4;n++) {         if (x == n) continue;         ret = max(ret, solve(y + 1, n) + land[y][n]);     }     return ret; } int solution(vector<vector<int> > l){     memset(dp, -1 ,sizeof dp);     N = l.size();     for(int n=0;n<N;n++){         for(int m=0;m<4;m++)             land[n][m] = l[n][m];     }     int ans = 0;     for(int n=0;n<4;n++){         ans = max(ans, solve(0, n));     }     return ans; } Colored by Color Scripter

cs

<6번 문제>

원형으로 구성된 스티커가있다. 

스티커를 뜯었을 때 점수를 얻을 수 있는데 뜯은 스티커의 양쪽 스티커는 뜯지 못한다.

최대 점수를 구하는 문제이다.

이것도 DP문제이다.

뜯었을 때의 경우와 뜯지 않았을 때의 경우로 나누고 

처음뜯었을때와 아닌 경우로 3차원 DP로 만들어 풀었다.

N이 1인 경우 예외처리를 해줘야 한다.

#include <vector> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int N; int arr[100001]; int dp[100001][2][2]; using namespace std; int solve(int idx, int get, int flag) {     if (flag && idx >= N - 1) return 0;     if (!flag && idx >= N) return 0;     int &ret = dp[idx][get][flag];     if (ret != -1)return ret;     if (get)          ret = max(solve(idx + 2, 0, flag), solve(idx + 2, 1, flag)) + arr[idx];         else          ret = max(solve(idx + 1, 1, flag),solve(idx + 1, 0, flag));     return ret; } int solution(vector<int> sticker){     memset(dp,-1,sizeof dp);     N = sticker.size();     for(int n=0;n<N;n++) arr[n]= sticker[n];     return N == 1 ? sticker[0] : max(solve(0, 0, 0), solve(0, 1, 1)); } Colored by Color Scripter

cs

<7번 문제>

문자열 T를 만드는데 주어지는 단어조각을 최소한만 이용해서 만드는 문제이다.

이것도 DP문제다.

(사실 4, 5, 6, 7 전부 DP였다.)

set을 이용해서 쉽게 풀리는데 주어지는 단어조각의 길이가 5임을 모르고 

$O(N^2)$으로 풀어서 계속 시간초과가 났다.

범위를 최대 +5개로 제한해서 $O(N\cdot 5)$로 풀 수 있다.

#include <iostream> #include <cstring> #include <string> #include <algorithm> #include <unordered_set> using namespace std; #define INF 987654321 int N, M; int dp[20001]; unordered_set<string> visit; string str[101], T; int solve(int idx) {     if (idx == M) return 0;     int &ret = dp[idx];     if (ret != -1) return ret;     ret = INF;     for (int n = idx; n< min(idx + 5, M);n++) {         if (visit.find(T.substr(idx, n - idx + 1)) != visit.end())             ret = min(ret, solve(n + 1) + 1);     }     return ret; } int solution(vector<string> strs, string t){     T = t;     visit.clear();     memset(dp, -1, sizeof dp);     N = strs.size();     M = t.length();     for(int n=0;n<N;n++) str[n] = strs[n];     for (int n = 0;n < N;n++)          visit.insert(str[n]);     int get = solve(0);     if(get == INF) return -1;     return get; } Colored by Color Scripter

cs