카카오 모의 테스트 풀이(주소 수록)

문제 출처 :

https://www.welcomekakao.com/competitions/35/welcome-kakao

https://www.welcomekakao.com/tryouts/1467/intro

정식 해설 :

https://programmers.co.kr/learn/courses/18

문제 1 ::

어떤 수가 주어질 때 각 자릿수의 합을 구하면 된다.

가장 기초가 되는 알고리즘으로 %와 / 연산을 이용하여 해결한다.

http://www.crocus.co.kr/399

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

using namespace std; int solution(int n) {     int answer = 0;       while(n)     {         answer += n % 10;         n /= 10;     }          return answer; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

문제 2 ::

길이 n인 배열에 1~n까지 값이 제대로 들어있는지 확인해보는 문제이다.

값을 받아오고, visit 배열을 하나 더 두어 확인해보면 되는 문제이다.

#include<vector>
#include <memory.h>
using namespace std;
 
bool visit[100002];
bool solution(vector<int> arr)
{
    memset(visit,0,sizeof(visit));
    bool answer = true;
    
    int len = arr.size();
    for(int i = 0; i < len; i ++)
        visit[arr[i]] = true;
    
    for(int i = 1; i <= len; i ++)
        if(!visit[i])
            answer = false;
    
    return answer;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

문제 3 ::

직사각형의 나머지 한 점을 구하는 것은 다음과 같다.

결국 'ㅁ'와 같이 생겼을 것이니 x좌표, y좌표들의 쌍이 짝수가 되어야 한다.

이때 홀수인 좌표값이 결국 비어있는 좌표가 됨을 의미한다.

#include <iostream>
#include <vector>
#include <map>
 
using namespace std;
 
vector<int> solution(vector<vector<int> > v) {
    vector<int> ans;
 
    map<int, int> mx;
    for (int i = 0; i < 3; i++)
        mx[v[i][0]]++;
 
    map<int, int> my;
    for (int i = 0; i < 3; i++)
        my[v[i][1]]++;
 
    for (auto it = mx.begin(); it != mx.end(); it++)
        if (it->second == 1)
            ans.push_back(it->first);
 
    for (auto it = my.begin(); it != my.end(); it++)
        if (it->second == 1)
            ans.push_back(it->first);
 
    return ans;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

 

문제 4 ::

사각형 최대 넓이는 min을 이용하여 찾아 낼 수 있다.

백준 문제에도 존재하니 참고하여 문제를 풀어보면 좋을 것 같다.

풀이는 아래 링크에 더 자세히 기술해 두었다.(문제가 같다.)

[1915번] 가장 큰 정사각형 :: http://www.crocus.co.kr/826

#include <vector>
#include <memory.h>
#include <algorithm>
 
using namespace std;
 
int dp[1111][1111];
int arr[1111][1111];
 
int solution(vector<vector<int>> board)
{
    memset(dp, 0, sizeof(dp));
    memset(arr, 0, sizeof(arr));
 
    int answer = -1;
 
    int n = board.size();
 
    for (int i = 0; i < n; i++)
    {
        int m = board[i].size();
        for (int j = 0; j < m; j++)
            arr[i + 1][j + 1] = board[i][j];
    }
 
    for (int i = 1; i <= n; i++)
    {
        int m = board[i - 1].size();
        for (int j = 1; j <= m; j++)
        {
            if (arr[i][j])
                dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                
            answer = max(answer, dp[i][j]);
        }
    }
    return answer * answer;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

문제 5 :: 

삼성 소프트웨어 멤버십 1차 문제와 동일하다.

http://www.crocus.co.kr/706 링크의 N*3 행렬 게임이라는 문제를 보면 된다.

전형적인 DP문제이다.

각 라인마다의 최대치를 계속해서 조건에 맞게 구해나가고, 마지막 라인에서의 MAX를 찾아내면 된다.

#include<vector>
#include <memory.h>
#include <algorithm>
 
using namespace std;
 
int dp[100002][4];
 
int solution(vector<vector<int> > land)
{
    memset(dp, 0, sizeof(dp));
    
    int answer = 0;
 
    for(int i = 0 ; i < 4; i ++)
    {
        dp[0][i] = land[0][i];
        answer = max({dp[0][0], dp[0][1], dp[0][2], dp[0][3]});
    }
    int n = land.size();
    for(int i = 1; i < n; i++)
    {
        dp[i][0] = max({dp[i-1][1], dp[i-1][2], dp[i-1][3]}) + land[i][0];
        dp[i][1] = max({dp[i-1][0], dp[i-1][2], dp[i-1][3]}) + land[i][1];
        dp[i][2] = max({dp[i-1][0], dp[i-1][1], dp[i-1][3]}) + land[i][2];
        dp[i][3] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]}) + land[i][3];
        
        answer = max({dp[i][0], dp[i][1], dp[i][2], dp[i][3]});
    }
    return answer;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

문제 6 :: 

5번까지는 한번 제출로 한번만에 통과해왔는데 6번에서 조금 걸리기 시작했다.

처음에는 재귀 DP로 짜서 dp구현을 해보려 하였지만, TLE가 계속해서 발생했고, 결국 다시 생각해본 결과 그냥 1중 포문에서 dp로 해결이 가능한 문제였다.

이 문제를 풀기위해 다음과 같이 생각해본다.

1. 원형을 일자로 펼쳐놓는다.

2. 만약 i번째 값을 선택했다면 i - 2번째를 선택했거나 i - 3번째를 선택하고 있어야 한다.

(최대값이고, 각 배열에는 음수가 없기 때문)

i - 2번째와 i - 3번째의 의미는 아래 두 그림과 같다.

☆☆☆★☆★☆☆

　　　i-2　i

☆☆★☆☆★☆☆

　　i-3　　i

3. 이제 원형으로 다시 만들어야한다.

결국 끝값과 첫값이 원으로 이어지는 부분이니 이에대해 처리를 해야한다.

즉, 첫값으로 시작하고 끝값을 무조건 카운트 하지않는 dp1과

첫값으로 시작하지 않고 끝값을 무조건 카운트하는 dp2로 나눈 것 중 최댓값을 구한다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory.h>
 
using namespace std;
 
int arr[100013];
int dp1[100013]; // 1번째 값 포함
int dp2[100013]; // 1번째 값 미포함
int ans;
 
int solution(vector<int> sticker)
{    
    memset(arr, 0, sizeof(arr));
    memset(dp1, 0, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));
    ans = 0;
 
    int len = sticker.size();
 
    if(len == 1)
        return sticker[0];
    else if(len == 2)
        return max(sticker[0], sticker[1]);
    
    for(int i = 0; i < len; i ++)
        arr[i + 3] = sticker[i];
    
    dp1[3] = arr[3];
    
    for (int i = 4; i <= len + 1; i++)
    {
        dp1[i] = max(dp1[i - 2], dp1[i - 3]) + arr[i];
        ans = max(dp1[i], ans);
    }
    
    dp2[4] = arr[4];
 
    for (int i = 5; i <= len + 2; i++)
    {
        dp2[i] = max(dp2[i - 2], dp2[i - 3]) + arr[i];
        ans = max(dp2[i], ans);
    }
 
    return ans;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

문제 7 ::

해결중에 있다.. 트라이인줄 알았지만, DP라고한다. 또다른 이야기에 의하면 Queue로도 해결이 된다고 한다.