코드 낙서장

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..

문제 주소 : programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제 확인 투포인터 문제입니다. 트라이를 활용해서 풀 수 있지만 최악의 경우 100000개의 보석의 이름 모두 10글자이며 중복이 없고 각 단어가 하위 트라이를 계속해서 만드는 경우 메모리 사용량이 너무 커질 수 있습니다. ex) "abcdefghij", "bcdefghijk", ... "aabcdefghi" .. 풀이 2가지 풀이법이 있습니다. 배열을 탐색해서 미리 보석의 종류를 map에 기록해둔 후 투포인터..

문제 주소 : programmers.co.kr/learn/courses/30/lessons/70130 코딩테스트 연습 - 스타 수열 programmers.co.kr 문제 확인 특별한 알고리즘이 필요없는 구현 문제입니다. 나오는 값들을 그래프 형식으로 저장한 후 하나씩 탐색하면서 최대 스타수열의 길이를 찾습니다. 풀이 수열의 길이가 길어지면 스타 수열을 찾기 위해 배열을 탐색하는 시간이 길어지므로 중복된 숫자를 다시 탐색하는 것은 비효율적입니다. 이를 방지하면서 해당하는 인덱스만 탐색을 하기 위하여 그래프를 사용합니다. 문제에서 나올 수 있는 숫자의 범위가 배열의 길이 이하이므로 2차원 배열 형태를 사용하며, 나오는 인덱스만 저장을 하면 되기 때문에 vector을 사용하여 저장합니다. ex) {0, 1, ..

문제 주소 : programmers.co.kr/learn/courses/30/lessons/1831 코딩테스트 연습 - 4단 고음 4단 고음 I'm in my dream~↗ ~↗ ~↗ IU는 본인의 장기인 3단 고음으로 유명하다. 그러던 그녀가 어느 날 4단 고음을 성공했고 그녀의 고음은 학계에서 연구가 될 만큼 유명해졌다 [1]. [1] 견두헌, 배명 programmers.co.kr 문제 확인 간단하게 시뮬레이션처럼 풀 수 있지만 시간 초과가 납니다. 또한 단순 dfs로 풀어도 시간 초과가 나게 됩니다. 따라서 가지치기, 혹은 추가 조건을 통해서 통과할 수 있습니다. * 이후에 2개의 + 가 나와야 하므로 이를 이용하여 조건을 만들 수 있습니다. 하향식 dfs와 가지치기를 통해 풀 수 있습니다. 풀이 ..

문제 주소 : programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제 확인 dp문제 처음 집을 선택하는가에 따라 2가지 스텝으로 분류합니다. 풀이 처음 집을 선택한 경우 마지막 집을 선택할 수 없으므로 size -1 까지 탐색을 합니다. 선택하지 않은 경우는 size 까지 모두 탐색을 합니다. n개의 배열을 둘 필요없이 2칸 단위로 잘라 최댓값을 지정하기 위해 3칸의 배열을 사용합니다. 현재 집을 털었을 때 비용과 털지 않고 ..

문제 주소 : programmers.co.kr/learn/courses/30/lessons/12902 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 문제 확인 dp 문제로 수열식으로 풀 수 있습니다. 홀수인 경우 모든 답이 0이며 짝수인 경우 생길 수 있는 경우의 수를 체크하면 쉽게 풀 수 있습니다. 풀이 n을 2 단위로 생각하면 두 가지 종류로 나눌 수 있습니다. 영역이 겹치는 문양 : 매 단계에서 새로 생기는 문양 영역이 분리된 문양 겹치는 문양의 경우 매 단계에서 2개 추가됨 분리된 문양의 경우 따라서 n이 2 증가할 때 생각할 수 있는 경우의 수는 다음과 같습니다. 이를 수식으로 나타내면 f(n) = f(n-2) * 3 + f(n-4) * 2 + f(n-6) * 2 + ....