Min:D's Devlog

문제 프로그래머스 해시 - 베스트앨범 (Level 3) 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 �� programmers.co.kr 문제 풀이 접근 방식 아래의 기준에 따라 베스트 앨범에 곡을 수록할 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하는 문제이다. 우선, 장르별 총 재생 수를 알아야 1번 기준을 충족시킬 수 있기 때문에 unordered_map을 사용하여 장르별 총 재생 수를 구해주었다. 위의 결과를 이용하여 result 벡터에 각 노래의 장르별 총 재생 수, 노래 재생 수, 노래 고유 번호를 ..

문제 프로그래머스 그리디 - 섬 연결하기 (Level 3) 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제 풀이 접근 방식 모든 섬을 연결하는 최소 비용을 구하는 문제이다. 이 문제는 프림 알고리즘을 활용하여 문제를 해결하였다. 우선, 주어진 costs 벡터를 활용하여 인접 행렬을 만들어주었다. 그 후, 방문한 섬과 방문하지 않은 섬의 인덱스를 구분해주기 위해, 시작 위치인 0을 visited 벡터에 넣고, 그 외의 섬들의 인덱스를 unvisited 벡터에 넣어주었다. while문에서는 프림 알고리즘을 활용하여 다리를 선택해주었다. 즉, 방문한 섬에서 방문하지 않은 섬으로 연결할 수 있는 다리들 중 최..

문제 프로그래머스 2019 KAKAO BLIND RECRUITMENT - 길 찾기 게임 (Level 3) 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 문제 풀이 접근 방식 이 문제는 2019 카카오 블라인드 공채 1차 코딩테스트 5번 문제로, 이진 트리를 만들어 전위 순회와 후위 순회를 수행하는 문제이다. 이진 트리를 만들기 위해 Node 구조체를 만들어 x, y, index, 왼쪽 노드, 오른쪽 노드를 저장할 수 있도록 하였고, 주어진 nodeinfo에 인덱스를 추가한 후, y값 기준 내림차순, x값 기준..

문제 프로그래머스 월간 코드 챌린지 시즌 1 - 풍선 터트리기 (Level 3) 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 문제 풀이 접근 방식 이 문제는 프로그래머스 월간 코드 챌린지 시즌 1 3번 문제로, 아래의 규칙대로 풍선을 1개만 남을 때까지 터트렸을 때, 최후까지 남기는 것이 가능한 풍선의 개수를 구하는 문제이다. 한 풍선의 양 옆의 풍선들을 숫자가 큰 풍선 먼저 터트려 하나씩만 남기면, 양 옆에는 각각 가장 작은 번호의 풍선만 남게 된다. 그 상태에서 기준이 되는 풍선과 양 옆의 풍선의 숫자를 비교하여 기준이 되는 풍선의 숫자보다 더 큰 값이 하나라도 존재한다면, 번호가 더 작은 풍선을 터트리는 행..

문제 프로그래머스 2020 KAKAO BLIND RECRUITMENT - 기둥과 보 설치 (Level 3) 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 문제 풀이 접근 방식 이 문제는 2020 카카오 블라인드 공채 1차 코딩테스트..

문제 프로그래머스 2020 KAKAO BLIND RECRUITMENT - 자물쇠와 열쇠 (Level 3) 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 문제 풀이 접근 방식 이 문제는 2020 카카오 블라인드 공채 1차 코딩테스트 3번 문제로, 주어진 열쇠로 자물쇠를 열 수 있는지를 판단하는 문제였다. 열쇠 영역의 일부분이 자물쇠 영역을 벗어나는 것이 가능하다. 그렇기 때문에 자물쇠 영역을 (M - 1) × 2 + N의 크기로 만들고, (M-1, M-1)에서부터 자물쇠의 값을 복사하여 열쇠를 가능한 모든 방법으로 맞춰볼 수 있도록 하였다. (M은 열쇠 영역..

문제 프로그래머스 2020 KAKAO BLIND RECRUITMENT - 블록 이동하기 (Level 3) 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 문제 풀이 접근 방식 이 문제는 2020 카카오 블라인드 채용 1차 코딩테스트 7번 문제로, 정답률이 1.7%인 쉽지 않은 문제였다. 구하고자 하는 것은 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간이다. 이 문제는 최소 시간을 구하는 기존의 BFS + DP 문제와 푸는 방식은 비슷했지만, 로봇이 점 두 개로 이루어져 있어서 구현하기가 복잡하였다. 이 문제를 기존의 방식처럼 풀..

문제 프로그래머스 2020 카카오 인턴십 - 보석 쇼핑 (Level 3) 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제 풀이 접근 방식 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 구하는 문제이다. 문제를 해결하기 위해 우선, unordered_set을 이용하여 보석 종류의 개수를 구하였다. 그 후, for을 수행하며 unordered_map에 각 보석의 인덱스를 저장해주었다. 처음으로 모든 종류의 보석을 발견했을 때, map에 저장되어 있는 인덱스의 최솟값을 answer의 시작 구간, 현재 인덱스(i + 1)를 끝 구간으로 저장해주었다. 또한,..

문제 프로그래머스 2017 카카오코드 예선 - 보행자 천국 (Level 3) 코딩테스트 연습 - 리틀 프렌즈 사천성 리틀 프렌즈 사천성 언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 programmers.co.kr 문제 풀이 접근 방식 출발점에서 도착점까지 이동 가능한 전체 경로의 수를 구하는 문제이다. 이 문제는 단순한 맵이 아닌 조건이 있는 맵이기 때문에 이를 고려하여 DP 방식으로 문제를 해결해주었다. 우선, map의 값이 0인 경우에는 모든 방향으로 움직일 수 있고, 1인 경우에는 갈 수 없으며, 2인 경우에는 직진만 가능하다. 2인 경우에 직진만 가능하기 때문에 수직 방향(↓)..

문제 프로그래머스 그리디 - 단속카메라 (Level 3) 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 문제 풀이 접근 방식 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 구하는 문제이다. 어느 위치에 카메라를 설치하는 것이 좋은지 판단하기 위해 다음과 같이 구현하였다. 우선, 차량의 이동 경로를 오름차순으로 정렬하였다. 그 후, 처음 차량의 이동 구간의 시작과 끝을 start와 end로 지정하고, 다음 차량의 이동 구간이 start와 end 사이인지를 확인하였다. 구간 내에 있는 경우에는 end를 해당 구간의 끝 지점으로 바꿔주고, 이 과정을 반복하여 한 대의 카..