1, 3, 4번 문제는 꽤 쉬웠지만, 2번 문제는 많은 시간을 요했다. 코테 당락은 2번에서 결정날 듯 하다. (개인적인 난이도 : 1 < 3 < 4 < 2)
보통 난이도 순으로 출제되는 코딩테스트와는 조금 달랐다. 2번 문제를 읽고, "이 문제는 빨리 못풀겠구나." 하고 바로 뒷문제로 넘어가서 다행이였다.
테스트 케이스가 주어지지 않아서 내 코드가 맞는 지 틀린 지 확인할 수 없었다.
총평
2020 하반기에 네이버, 라인, 쿠팡, 카카오 코테를 봤는데, 난이도 순은 카카오 >>>>> 라인 >>> 쿠팡 > 네이버 이 순서인 것 같다.
사실 코딩 테스트가 어느 정도 할만 하다는 것은 "피시험자가 어느 정도 알고리즘을 알고있구나." 를 판단하기 위함인데, 쿠팡 면접이 얼마나 극악일지 상상이 안간다. 쿠팡 면접은 단 한 번 보던데, 라이브 코딩에 인성 면접에 직무 면접에... 마구마구 버무리지 않을까 싶다.
필자는 원래 C++를 이용해서 알고리즘을 풀었지만, JSON Pharser 때문에 파이썬을 급하게 배웠어야 했다. 구글링을 통해 C++로는 REST API와 JSON Pharsing에 시간을 너무 많이 투자한다는 블로그 글들이 보였다. 점프 투 파이썬에서 6시간 동안 1회독하고, 시험 직전에 리스트, 딕셔너리 등 주요 함수들을 한번 훑어보았다. 아래 기본서로 아마도 2차 코테 합격에는 문제 없었을 것이다.
SELECT HOUR(DATETIME) AS 'HOUR', COUNT(*) AS 'COUNT'
FROM ANIMAL_OUTS
GROUP BY HOUR(DATETIME)
HAVING HOUR >= 9 AND HOUR <= 19
ORDER BY HOUR(DATETIME) ASC
SET @hour := -1;
SELECT (@hour := @hour + 1) as HOUR,
(SELECT COUNT(*) FROM ANIMAL_OUTS WHERE HOUR(DATETIME) = @hour) as COUNT
FROM ANIMAL_OUTS
WHERE @hour < 23
SELECT b.ANIMAL_ID, b.NAME
FROM ANIMAL_INS a RIGHT JOIN ANIMAL_OUTS b on a.ANIMAL_ID = b.ANIMAL_ID
WHERE a.ANIMAL_ID IS NOT NULL AND a.DATETIME > b.DATETIME
ORDER BY a.DATETIME
SELECT ANIMAL_INS.NAME, ANIMAL_INS.DATETIME
FROM ANIMAL_INS
LEFT OUTER JOIN ANIMAL_OUTS
ON ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID
WHERE ANIMAL_OUTS.ANIMAL_ID IS NULL
ORDER BY ANIMAL_INS.DATETIME ASC
LIMIT 3
SELECT ANIMAL_INS.ANIMAL_ID, ANIMAL_INS.ANIMAL_TYPE, ANIMAL_INS.NAME
FROM ANIMAL_INS
LEFT OUTER JOIN ANIMAL_OUTS
ON ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID
WHERE ANIMAL_INS.SEX_UPON_INTAKE != ANIMAL_OUTS.SEX_UPON_OUTCOME
SELECT ANIMAL_ID, NAME, SEX_UPON_INTAKE
FROM ANIMAL_INS
WHERE NAME = 'Lucy' OR NAME = 'Ella' OR NAME = 'Pickle' OR NAME = 'Rogan' OR NAME = 'Sabrina' OR NAME = 'Mitty'
SELECT ANIMAL_ID, NAME, SEX_UPON_INTAKE
FROM ANIMAL_INS
WHERE NAME IN ('Lucy', 'Ella', 'Pickle', 'Rogan', 'Sabrina', 'Mitty')
SELECT ANIMAL_ID, NAME,
IF(SEX_UPON_INTAKE LIKE "%Neutered%" OR SEX_UPON_INTAKE LIKE "%Spayed%", 'O', 'X') AS '중성화'
FROM ANIMAL_INS
ORDER BY ANIMAL_ID ASC
SELECT ANIMAL_INS.ANIMAL_ID, ANIMAL_INS.NAME
FROM ANIMAL_INS, ANIMAL_OUTS
WHERE ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID
ORDER BY ANIMAL_OUTS.DATETIME - ANIMAL_INS.DATETIME DESC
LIMIT 2
기존에 후보키였던 것을 포함한다면, 지금 검사하는 칼럼의 인덱스는 최소성을 만족하지 못하므로 return
기존에 후보키였던 것을 포함하지 않는다면,
vector<vector<string>> relation의 모든 레코드에 대해 칼럼의 인덱스의 값들을 추출해서, 한 vector<string>으로 잡는다. 잡은 vector<string>을 vector<vector<string>>에 넣는다.
모두 넣고, 일일히 대조해서 처음부터 끝까지 일치하는지 확인한다.
일치하는게 있다면, 후보키가 되지 못하므로 return
일치하는게 없다면, 후보키가 될 수 있다.
조금 말이 어려운데, 코드를 보면서 이해해보자.
아래 코드는 후보키의 가짓수를 토대로 dfs를 돌리는 함수다.
vector<vector<string>> rel;
// answer는 후보키의 vector를 저장한다.
vector<vector<int>> answer;
int col, row, arr[21];
int solution(vector<vector<string>> relation) {
row = relation.size();
col = relation[0].size();
rel = relation;
// i는 후보키의 가짓수
for(int i = 1; i <= col; i++){
// arr은 칼럼의 인덱스를 저장할 예정.
memset(arr, 0, sizeof(arr));
dfs(i, 0, -1);
}
return answer.size();
}
아래 코드는 조합을 시행하는 dfs다.
// 벡터 a와 벡터 b가 모두 같은 원소를 가지고 있는지 판단하는 함수다.
bool vector_is_equal(vector<string> a, vector<string> b){
int vec_size = a.size();
for(int i = 0; i < vec_size; i++){
if(a[i] != b[i]) return false;
}
return true;
}
// goal : 나는 인덱스를 goal개 만큼 집기로 했다.
// cnt : 나는 인덱스를 cnt개 만큼 집었다.
// idx : 나는 인덱스를 idx까지 골랐었다.
void dfs(int goal, int cnt, int idx){
// 조합을 통해 모두 집었다면,
if(goal == cnt){
// 기존에 찾아놓은 후보키를 포함하고 있는 지 검사
for(auto i : answer){
int ans_idx = 0;
for(int j = 0; j < goal; j++){
if(i[ans_idx] == arr[j]) ans_idx++;
if(ans_idx >= i.size()) break;
}
if(ans_idx >= i.size()) return;
}
// 후보키가 될 수 있는지 검사할 예정
// vector<vector<string>> relation에서 골라놓은 인덱스를 저장해놓은 arr에 존재하는 인덱스대로 하나의 tmp 벡터를 만들고, 이를 cmp 벡터에 넣어준다.
vector<vector<string>> cmp;
for(int i = 0; i < row; i++){
vector<string> tmp;
for(int j = 0; j < goal; j++)
tmp.push_back(rel[i][arr[j]]);
cmp.push_back(tmp);
}
// 비교하는 과정
for(int i = 0; i < row; i++){
for(int j = i + 1; j < row; j++){
// 벡터가 하나라도 같은 게 있으면 후보키가 되지 못함
if(vector_is_equal(cmp[i], cmp[j])) return;
}
}
// 벡터가 모두 다르므로 후보키가 될 수 있다.
vector<int> answer_temp;
for(int i = 0; i < goal; i++)
answer_temp.push_back(arr[i]);
answer.push_back(answer_temp);
}
// 다음 조합 진행
else {
for(int i = idx + 1; i < col; i++){
arr[cnt] = i;
dfs(goal, cnt + 1, i);
}
}
}
코드
#include <bits/stdc++.h>
using namespace std;
vector<vector<string>> rel;
vector<vector<int>> answer;
int col, row, arr[21];
bool vector_is_equal(vector<string> a, vector<string> b){
int vec_size = a.size();
for(int i = 0; i < vec_size; i++){
if(a[i] != b[i]) return false;
}
return true;
}
void dfs(int goal, int cnt, int idx){
if(goal == cnt){
for(auto i : answer){
int ans_idx = 0;
for(int j = 0; j < goal; j++){
if(i[ans_idx] == arr[j]) ans_idx++;
if(ans_idx >= i.size()) break;
}
if(ans_idx >= i.size()) return;
}
vector<vector<string>> cmp;
for(int i = 0; i < row; i++){
vector<string> tmp;
for(int j = 0; j < goal; j++)
tmp.push_back(rel[i][arr[j]]);
cmp.push_back(tmp);
}
for(int i = 0; i < row; i++){
for(int j = i + 1; j < row; j++){
if(vector_is_equal(cmp[i], cmp[j])) return;
}
}
vector<int> answer_temp;
for(int i = 0; i < goal; i++)
answer_temp.push_back(arr[i]);
answer.push_back(answer_temp);
}
else {
for(int i = idx + 1; i < col; i++){
arr[cnt] = i;
dfs(goal, cnt + 1, i);
}
}
}
int solution(vector<vector<string>> relation) {
row = relation.size();
col = relation[0].size();
rel = relation;
for(int i = 1; i <= col; i++){
memset(arr, 0, sizeof(arr));
dfs(i, 0, -1);
}
return answer.size();
}
각 칸에 오른쪽으로 얼마나 갈 수 있는지 적혀있고, 그 규칙대로 마지막 칸까지 도달했을 때, 최소 몇 번 점프해야 갈 수 있는지 구하는 문제다.
int dp[i]
i번째 칸에 왔을 때, 최소 몇 번 점프해서 왔는지 기억하는 배열
초기 dp는 int의 최댓값으로 잡는다. 점프 수의 최솟값을 구하기 위함이다.
dp 과정
// 맨 첫 칸은 점프를 하지 않았으므로 0
dp[1] = 0;
for(int i = 1; i < n; i++){
// j : i번째 칸에서 점프해서 갈 수 있는 칸(j)에 대해서 최소 점프 수 검사.
for(int j = i + 1; j <= min(arr[i] + i, n); j++){
dp[j] = min(dp[i] + 1, dp[j]);
}
}
코드
#include <bits/stdc++.h>
using namespace std;
int n, arr[1001], dp[1001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> arr[i];
dp[i] = 2147000000;
}
dp[1] = 0;
for(int i = 1; i < n; i++){
for(int j = i + 1; j <= min(arr[i] + i, n); j++){
dp[j] = min(dp[i] + 1, dp[j]);
}
}
if(dp[n] == 2147000000) cout << -1;
else cout << dp[n];
}
