[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 > 삼각 달팽이 코딩테스트 연습 - 삼각 달팽이 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 > 후보키 코딩테스트 연습 - 후보키 [["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.
[Programmers] 자물쇠와 열쇠
문제 2020 KAKAO BLIND RECRUITMENT > 자물쇠와 열쇠 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 아이디어 이번 문제는 처음 접했을 땐 풀지 못하고 시간이 흘러 다시 접했을 때 풀게 된 문제였습니다. 풀이 방법은 단순히 회전을 하며 자물쇠를 열 수 있는 모든 경우를 찾는 완전탐색을 하면 되었습니다. 자물쇠는 고정 시키고 열쇠를 좌측 상단부터 우측 하단까지 옮기며 자물쇠를 열 수 있는지를 확인해주면 됩니다. 마치 2차원 배열을 탐색하는 것처럼요. 그림으로 나타내면 이런 모습이 나오겠습니다. 구현 코드 (Java) class Soluti..
2021. 3. 19.
