코드 낙서장

2021 카카오 코딩 테스트 문제입니다. 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr 문제 확인 dfs, 그리디로 풀 수 있지만 depth가 깊어지면 stack의 모든 상황을 확인하기 때문에 느리므로 트리 dp로 풉니다. 풀이 dp 배열을 dp[현재 노드 번호][선택 상태]로 둡니다. 선택 상태는 현재 노드가 워크숍에 참가 여부로 두고 조건을 고려합니다. dp[cur_idx][0] : 현재 노드가 워크숍에 참가하지 않을 때 팀의 최소비용, 자식 노드 중 하나 이상 워크숍에 참가가 필요합니다. dp..

2021 카카오 코딩 테스트 문제입니다. 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 문제 확인 초로 환산했을 때 최대 크기가 360000이므로 배열과 prefix sum을 이용하여 풀 수 있습니다. 풀이 들어오는 string은 모두 길이가 고정이므로 간단하게 시간과 정수로 변환하는 함수를 만들어 활용합니다. log가 시작되는 지점에 +1, 끝나는 지점에 -1을 해 두고 이들을 prefix sum을 구하여 각 시간마다 시청하는 사람의 ..

2021 카카오 코딩 테스트 문제입니다. 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 문제 확인 그래프 탐색 응용문제입니다. 풀이 합승 후 무지, 어피치 중 한 사람이 내리는 지점을 i로 두면 총요금은 dist[i][start] ..

2021 카카오 코딩 테스트 문제입니다. 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 문제 확인 배열 탐색 문제입니다. 크기가 4x4로 작으므로 dfs, 가지치기를 통해 문제를 풀 수 있습니다. 풀이 각 움직임을 dfs로 나타내면 depth와 크기가 너무 커지므로 카드 짝을 맞추는 것을 dfs, 카드 위치를 찾는 것은 queue를 이용한 bfs를 사용합니다. 상하좌우 방향으로 이동을 함을 cost 1로 두고 bfs 탐색을 통해 cost가 가장 적은 위치의 카드를 선택합니다. 카드를 선택하고 나면 같은 카드 쌍..

2021 카카오 코딩 테스트 문제입니다.

2021 카카오 코딩 테스트 문제입니다. 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 문제 확인 조합과 자료구조를 사용하는 문제입니다. 풀이 dfs로 메뉴 조합을 찾을 수 있지만 최대 depth가 10이고 손님마다 dfs를 모두 돌면 많은 시간이 걸리기 때문에 조합을 찾는 특별한 알고리즘을 사용합니다. 파이썬에서 사용하는 combination 함수를 구현하여 사용합니다. combination 함수는 permutation 방식을 사용하여 조합을 구하는 방식이며 std::next_permutation 함수를 사..

2021 카카오 코딩 테스트 문제입니다. 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가 programmers.co.kr 문제 확인 코딩 테스트에 단골 문제인 문자열 처리 문제입니다. 모든 테스트 케이스에서 최대 0.02ms 정도 빠른 시간을 받기 위해 한 번의 루프로 처리를 해 줍니다. 풀이 객체 처리는 일반 char 배열에 비하여 느리므로 char와 인덱싱을 통해 풀어줍니다. 좀 더 빠른 실행을 위해 7단계를 3단계로 합칩니다. 1, 2, 3, 6 단계와 4단계 일부분을 처음 문자열 탐색에 모두 마치고 4단계를 한번 더 검증한 후 5..