5 DERECHA
2024년 Softeer 정기 역량 진단 후기 : 문제 유형 (1. Stack, 2. 3차원DP) 본문
Softeer 역량 진단 이란?
현대 그룹에서 보는 자체 시험으로, 시험에 PASS하게 될 시에 현대 그룹 코딩테스트 면제라는 특혜를 주는 시험입니다.
1번 문제 : Stack + Deque
기존의 괄호 문제에서 물음표가 추가 되었을때, 물음표(?)를 '('나 ')'로 바꿔서 괄호가 맞는 쌍으로 만들수 있는지 물어보는 문제였습니다. 문제에서는 '('가 들어오는 사람, ')'가 나가는 사람으로, ')'의 수가 (나가는 사람의 수가) 들어온 사람 보다 더 많으면 안 되고, 마지막에는 스택에 아무것도 안 남아 있어야합니다.
N이 5000까지 가능하였기에, dfs같은 재귀함수로 모든 물음표가 나오는 경우를 탐색하기에는 시간초과의 우려가 있었습니다. 그리디로 처음에 접근해서 문제를 풀었으나, 어떤 경우에 괄호를 열어주고 닫아줘야할지 계산이 안 되어서 틀리는 경우를 발견했습니다. (다만, 조심해야할게 주어진 테스트케이스 3개는 너무 빈약해서 해당 테스트케이스는 통과했습니다.)
결국, '('는 stack에 담아주고, ?는 deque에 담아주었습니다. 둘다 idx와 함께 담아주었고, ')'가 올때 idx를 계산해서 해주는 방식으로 했는데 생각해보니, 그리디로도 해당 문제를 풀 수 있을것 같습니다. stack과 deque을 같이 사용해주면서 idx까지 계산해주면 코드는 복잡하긴한데, 해당 문제를 풀 수는 있습니다.
아래와 같은 두 문제가 그나마 비슷합니다.
괄호 : https://www.acmicpc.net/problem/9012
괄호 채우기 : https://www.acmicpc.net/problem/11882
2번 문제 : 3차원 Dynamic Programing
해당 문제는 2차원 Map이 주어지고 각 좌표에 양수나 음수의 숫자가 적혀있습다. 1,1에서 N,N까지 움직여야 하고 우측이라 아래로만 움직일 수 있습니다. 여기까지만 읽었을때 이미 우측과 아래로만 움직일 수 있다고 하여서 Dynamic Progaming이 바로 생각이 나야합니다. 문제에서는 시간을 T만큰 한 번 되돌릴 수 있었고, 그러면 본래의 자리로 해당 자리로 돌아가는데, 획득한 점수는 그대로 가지고 돌아갑니다. 그래서 우측에 큰 값이 있고, 아래로 내려가는게 더 유리할 경우에는 우측으로 이동하여서 큰 값을 먹고, 시간이동을 해서 과거의 길로 돌아간 다음 아래로 가야합니다.
1000*1000 map에서 시간이동을 하여셔 bfs를 할경우 시간 초과가 날 것이기 때문에 bfs탐색은 하지 않았습니다.
애초에 map이 2차원 이니까 3차원 dp로 풀었습니다. 시간이동을 하기 전과 하고 난 후로 해줬고, -1000부터 1000까지 값이 가능해서 -1001로 초기화를 해줘야 했습니다.
시간이동을 하기 전의 dp는 아래와 같이 할 수 있습니다. 여기서 mapp을 구조체로 만들어서 num과 dir를 다 담을수 있게 했다. 시간이동을 할때 어떤 방향으로 왔는지를 기록하기 위해서 입니다. 여기서 update함수에서는 이제 각 위치에서 시간이동을 해줘서 돌아갔습니다. dir방향으로 다 탐색해서 돌아갔는데, 해당 부분까지 구현하면 너무 문제를 다 구현하는 것이라서 적지는 않았습니다.
struct {
int num,
int dir,
}mapp[1001][1001][2];
dr[3] = {0, -1, 0};
dr[3] = {0, 0, -1};
// 제일 윗줄, 제일 왼쪽 줄 초기화 진행
if (dp[i-1][j][0].num > dp[i][j-1][0].num) {
dp[i][j][0].num = dp[i-1][j][0].num + arr[i][j];
dp[i][j][0].dir = 1;
} else {
dp[i][j][0].num = dp[i-1][j][0].num + arr[i][j];
dp[i][j][0].dir = 2;
}
update(i,j);아래와 같은 문제가 그나마 비슷합니다.
https://www.acmicpc.net/problem/2206
코딩테스트 온라인 과외 수업 진행
안녕하세요.
Software Maestro 10기 였으며 삼성전자에서 2020년 3월부터 2024년 3월까지 4년 근무하고 퇴직하였습니다. 현재 본격적으로 코딩테스트 온라인 과외 수업을 진행합니다.
삼성전자 근무시에 PRO 등급 취득하여 삼성전자 코딩테스트의 경우 2번 문제 풀이(PRO)에 큰 도움 드릴 수 있습니다. 또한 네카라쿠배나 LG, Hyundai 코딩테스트 대비도 가능하며, 기업 맞춤형으로 준비 가능합니다.
관심있으신 분들은 문의 부탁드립니다.
아래는 제 링크드인 주소와 카카오톡 오픈 채팅 주소입니다.
Linkedin : https://www.linkedin.com/in/kaykim30/
Kakao : https://open.kakao.com/o/sceoQ9dg