코드 낙서장

2019 카카오 채용 코딩 테스드 문제입니다. 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr문제 확인 알고리즘을 사용하여 푸는 것보다 계산식과 몇 개의 루프 문을 통해 푸는 것이 훨씬 성능이 좋습니다. 풀이 위와 같은 식으로 모든 루프를 처리하면 정확도 테스트도 통과하기 어렵습니다. 배열에 접근, 원소 수정과 함께 모든 루프를 돌게 되므로 O(n^2)이 되기 때문입니다. 따라서 각 루프 문을 압축하여 가능한 루프를 한 번에 처리해야 합니다. food_times 배열의 길이를 length로 두고 k와 비교하여 몇 번의 루프를 돌고 난 후 몇 번을 움직이는지 확인하여 풉니다.루프 횟수 : k / length남은 움직임 횟수 : k % length이를 통하여 루프 횟수 loop 보다 ..

2019 카카오 채용 코딩 테스트 문제입니다. 코딩테스트 연습 - 블록 게임 [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2 programmers.co.kr 문제 확인 구현 문제입니다. 풀이 블록을 3x3 크기기에서 경우의 수를 두어 풉니다. 1 2 3 4 5 6 7 8 9 위와 같은 배치에서 문제에서 주어진 블록의 형태는 ㄴ, ㅗ 를 뒤집거나 회전하여 만들..

2020 카카오 블라인드 채용 코딩 테스트 문제입니다. 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제 확인 트라이를 활용하는 문제입니다. 트라이 (컴퓨팅) 위키백과, 우리 모두의 백과사전. "A", "to", "tea", "ted", "ten", "i", "in", "inn"를 키로 둔 트라이. 이 예제에는 모든 자식 노드가 알파벳 순으로 왼쪽에서 오른쪽으로 정렬되어 있지는 않습니다. (루트 ko.wikipedia.org 풀이 트라이의 가지를 알파벳에 대하여 만듭니다. 와일드카드 문자 ? 는 조건에 따라 접두사, 접미사에서만 나오므로 역순으로 읽은 문자열에 대하여 트라이를 하나 더 생성합니다. 와일드카드 문자 특징은 길이가 1로 고정되어 있으므로 각 문자열의 길이를 map 컨테이너를..

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

문제 주소 : 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 + ....

문제 주소 : programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 문제 확인 dp나 그래프 MST로 풀 수 있지만 크기가 작기 때문에 간단하게 bfs로도 풀 수 있습니다. 사다리 비용은 길이만큼 들기 때문에 여러개의 사다리를 놓는것에 대한 추가 비용이 없습니다. 따라서 최소 비용의 사다리를 선택 해 가면서 모든 지형을 방문하면 문제를 해결할 수 있습니다. ..