본문 바로가기
728x90
반응형

프로그래머스25

[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] 불량 사용자 문제 2019 카카오 개발자 겨울 인턴십 > 불량 사용자 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 아이디어 이번 문제의 아이디어는 순열과 조합입니다. 제가 생각해낸 방법은 다음과 같습니다. 1. user_id에서 banned_id의 길이 만큼에 해당하는 원소를 뽑아내는 조합 구하기 2. 만들어진 조합을 가지고 순열 구하기 3. 만들어진 순열을 가지고 제재 아이디가 될 수 있는지를 확인 4. 만약 제재 아이디가 되었다는 것을 확인하면 순열 구하기 중단 5. 모든 조합의 경우에 대해 2~4를 반복 기본적인.. 2021. 4. 22.
[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] 단어 변환 문제 깊이/너비 우선 탐색(DFS/BFS) > 단어 변환 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 아이디어 이번 문제의 아이디어는 BFS입니다. DFS를 이용해도 풀릴지는 정확히 모르겠지만 DFS보단 BFS를 사용하는 게 더 효율적으로 풀릴 수 있는 문제입니다. 풀이법은 다음과 같습니다. 1. 시작단어를 queue에 담기 2. queue에 담긴 단어와 words에 있는 단어를 비교하여 변환이 가능한지 확인 3. 변환이 가능하고 words에 속하는 단어로 더 빠.. 2021. 4. 18.
[Programmers] 네트워크 문제 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 아이디어 이번 문제의 아이디어는 문제 분류에도 나와있듯이 DFS/BFS입니다. 둘 중 아무거나 사용해도 문제는 풀 수는 있습니다. 저 같은 경우는 DFS를 이용하여 풀었습니다. 풀이법은 다음과 같습니다. 1. 컴퓨터를 탐색 2. 아직 방문하지 않은 컴퓨터면 방문 체크 후 DFS로 주변 컴퓨터들 탐색 3. 모든 컴퓨터를 방문할 때까지 1~2를 반복 구현 코드 (JavaScript) const solve .. 2021. 4. 17.
[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] 뉴스 클러스터링 문제 2018 KAKAO BLIND RECRUITMENT > [1차] 뉴스 클러스터링 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 아이디어 이번 문제의 아이디어라고 할만한 것은... 딱히 없는 것 같습니다. 굳이 선택하자면... 집합 연산에 대해 아는지 정도라고 생각합니다. 해당 문제를 풀기에 앞서 집합연산 수식에 대해 알고 가셔야 될 것이 있습니다. n(A∪B) = n(A) + n(B) - n(A∩B) => 집합 A와 집합 B의 합집합 개수 = 집합 A의 개수 + 집합 B의 개수 -.. 2021. 4. 12.
[Programmers] 추석 트래픽 문제 2018 KAKAO BLIND RECRUITMENT > [1차] 추석 트래픽 2021. 4. 11.
[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] 오픈채팅방 문제 2019 KAKAO BLIND RECRUITMENT > 오픈채팅방 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 아이디어 이번 문제의 아이디어는 아이디에 맞는 닉네임 매핑 방법이라고 생각합니다. 그리고 닉네임을 매핑하는 방법은 map을 사용하면 됩니다. key는 아이디, value는 닉네임으로 한 map을 생성하여 채팅방에 사람들이 들어올 때마다 key-value쌍을 지어 순서대로 모두 넣어주게 되면 결과적으로 마지막에 저장되어 있는 값이 아이디에 해당하는 닉네임이 될 것입니다. 들어오거나 나갈 때 발.. 2021. 3. 25.
[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.
[Programmers] 괄호 변환 문제 2020 KAKAO BLIND RECRUITMENT > 괄호 변환 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 아이디어 이 문제의 아이디어는 문제에서 제공해주고 있습니다. 문제에서 설명하는 상황에 맞게 코드를 구현하기만 하면 끝인 문제입니다. 굳이 하나를 선택해보자면 재귀 함수를 이용해야 된다고 말할 수 있을 것 같습니다. 구현 코드 (JavaScript) const solve = (val) => { if(val.length === 0) { return ''; } let count = 0; // '('.. 2021. 3. 18.
[Programmers] 문자열 압축 문제 2020 KAKAO BLIND RECRUITMENT > 문자열 압축 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 아이디어 이 문제는 문제를 푼 사람이 많은 것처럼 큰 아이디어를 요구하지 않았습니다. 문자열을 모두 동일한 길이로 잘라낸 뒤 잘라진 문자열 중 동일한 문자열이 있다면 개수를 세어 그에 걸맞은 새로운 문자열을 만들어주기만 하면 됩니다. 다음과 같은 절차를 통해 코드를 작성하면 됩니다. 1. 자를 문자열 길이 탐색 (1~s문자열의 길이/2) 2. 길이만큼 잘라낸 문자열을 모두 탐색하여 .. 2021. 3. 17.
728x90
반응형