[Programmers] 여행경로
문제 깊이/너비 우선 탐색(DFS/BFS) > 여행경로 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 아이디어 이번 문제의 아이디어는 DFS입니다. 기본적인 DFS문제라고 생각돼서 DFS이다! 말고는 추가적인 견해는 필요 없을 것으로 보입니다. 재귀 함수를 이용하여 최대 깊이까지 탐색한 후 가능한 경로가 여러 개일 경우는 알파벳 순서가 앞인 경로에 대해서만 결과로 보여주면 쉽게 풀 수 있을 것으로 보입니다. 구현 코드 (JavaScript) const res = []; co..
2021. 4. 24.
[Programmers] 경주로 건설
문제 2020 카카오 인턴십 > 경주로 건설 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 아이디어 이번 문제의 아이디어는 BFS입니다. DFS로 시도하려고 하시는 분들도 있을 것 같아 보이는데 개인적인 견해로는 배열의 크기가 최대 2..
2021. 4. 21.
[Programmers] 보석 쇼핑
문제 2020 카카오 인턴십 > 보석 쇼핑 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 아이디어 이번 문제는 최적화하는 방법이 가장 중요하게 생각될 아이디어로 보입니다. 기본적으로 gems의 배열 크기가 최대 100,000까지 존재할 수 있기 때문에 DFS, BFS와 같은 알고리즘을 사용하면 시간이나 메모리가 펑펑 터지게 됩니다. 최대로 가능한 시간 복잡도는 O(nlogn) 정도이기 때문에 최대한 반복문 한 번만 사용하여 문제를 푸는 방법을 생각해야 됩니다. 제가 생각한 방법은 다음과 같습니다. 1. 결과로 나오게 될 구간 값을 [left, right]라..
2021. 4. 20.
[Programmers] 섬 연결하기
문제 탐욕법(Greedy) > 섬 연결하기 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 아이디어 이번 문제의 아이디어는 MST입니다. 소주제는 Greedy로 되어있지만 저는 MST에 더 적합한 문제라고 개인적으로 생각합니다. MST기법들인 프림이나 크루스칼 중 아무거나 사용해도 문제없이 풀 수 있을 것으로 보입니다. 저는 크루스칼을 이용하여 구현을 해봤습니다. 구현 코드 (JavaScript) class Node { constructor(a, b, val) { this.a = a; this.b = b; this.val = val; } } function solution(n, costs) { const n..
2021. 4. 19.
[Programmers] 카카오프렌즈 컬러링북
문제 2017 카카오코드 예선 > 카카오프렌즈 컬러링북 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 아이디어 이번 문제의 아이디어는 BFS입니다. 풀이 방법은 다음과 같습니다. 1. 배열을 탐색하며 원소 값이 0이 아니고 방문한 적이 없는 인덱스 찾기 2. 찾은 인덱스를 기준으로 원소 값이 같은 인접한 인덱스를 BFS로 모두 방문 3. 배열을 모두 탐색할 때 까지 1~2를 반복 구현 코드 (Java) import java.util.*; class Solution { public int[] solution(i..
2021. 4. 16.
[Programmers] 쿼드압축 후 개수 세기
문제 월간 코드 챌린지 시즌1 > 쿼드압축 후 개수 세기 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 아이디어 이번 문제의 아이디어는 DFS입니다. 원하는 조건이 달성되지 않으면 달성될 때까지 깊이를 최대한 들어가면서 탐색해주면 됩니다. 풀이법은 생각보다 간단합니다. 1. 배열 전체를 탐색 2. 모든 배열 값이 동일하지..
2021. 4. 15.
[Programmers] 풍선 터트리기
문제 월간 코드 챌린지 시즌1 > 풍선 터트리기 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 아이디어 i번째에 존재하는 풍선이 최후까지 남는 지를 확인하기 위해 제가 생각한 방법은 다음과 같습니다. 우선 i번째를 기준으로 좌측과 우측의 풍선을 최대한 터트려서 총 3개의 풍선을 남깁니다. 그리고 좌측에 최후까지 남은 풍선을 i-1번째 풍선, 우측에 최후까지 남은 풍선을 i+1번째 풍선이라고 일컫겠습니다. 1. 만약 풍선을 3개로 만드는 과정에서 번호가 작은 풍선을 터트리지 않았다면?? i-1번째와 i+1번째는 항상 방향마다 가장 작은 번호의 숫자가 담긴 풍선이 남음 그리고 i-1번째와 i+1번째 풍선 중 하나라도 ..
2021. 4. 14.
[Programmers] 삼각 달팽이
문제 월간 코드 챌린지 시즌1 > 삼각 달팽이 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr 아이디어 이번 문제의 아이디어는 달팽이 모양으로 회전을 하는 방법이라고 생각합니다. 제가 생각한 방법은 다음과 같습니다. 아래 방향으로 이동하며 정수 값을 집어넣기 배열을 벗어나거나 값이 존재하는 인덱스를 마주할 경우 우측 방향으로 방향 전환 우측 방향으로 이동하며 정수 값을 집어넣기 배열을 벗어나거나 값이 존재하는 인덱스를 마주할 경우 좌상단 방향으로 방향 전환 좌상단 방향으로 이동하며 정수 값을 집어넣기 배열을 벗어나거..
2021. 4. 13.
[Programmers] 길 찾기 게임
문제 2019 KAKAO BLIND RECRUITMENT > 길 찾기 게임 코딩테스트 연습 - 길 찾기 게임 [[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 아이디어 이번 문제는 주어진 정보를 가지고 이진트리 만들 주 아니? 를 물어보는 것 같습니다. 왜냐하면 이진 트리를 구성하게 되면 자연스럽게 전위 순회와 후위 순회를 했을 때의 순서를 알 수 있기 때문입니다. 이진트리를 만드는 방법은 생각보다 어렵지 않았습니다. 주어진 노드 정보들의 y값들이 트리의 depth가 되기 때문에 y값이 큰 순서부터 차례대로 판단을 해주면 됩니다. 먼저 y에 대해..
2021. 4. 2.
[Programmers] 후보키
문제 2019 KAKAO BLIND RECRUITMENT > 후보키 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 아이디어 이번 문제의 아이디어는 부분집합을 이용한 완전 탐색이라고 생각합니다. 문제에서 요구하는 후보 키가 되기 위해서는 유일성과 최소성을 모두 만족해야 됩니다. 그리고 컬럼값의 최대 길이는 8까지이기 때문에 컬럼들에 대한 모든 부분집합을 구해도 시간 초과 등의 에러를 마주..
2021. 3. 27.
[Programmers] 블록 이동하기
문제 2020 KAKAO BLIND RECRUITMENT > 블록 이동하기 코딩테스트 연습 - 블록 이동하기 [[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 아이디어 이번 문제는 평범한 BFS로 길 찾는 문제들의 심화 버전이라고 생각합니다. 로봇이 차지하는 공간이 2칸이어도 사방탐색을 하는 데는 어려움이 없었지만 회전하는 경우를 구할 때 말썽을 많이 부렸습니다. 초기 코드가 구현되었을 때는 회전하는 부분이 복잡하고 길었지만 구현하고 나서 생각을 다시 정리해보니 회전하는 경우를 판단할 때 매우 간단한 코드로 변경할 수 있었습니다. 생각한 방법에 대해 간단하게 설명드리겠습니다..
2021. 3. 20.
