본문 바로가기
728x90
반응형

Algorithm/Programmers28

[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 카카오 개발자 겨울 인턴십 > 징검다리 건너기 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 아이디어 이번 문제는 우선순위 큐와 일반 큐의 조합으로 풀어봤습니다. 제가 문제를 읽고 생각한 풀이 방법은 "디딤돌을 k개만큼 순서대로 묶었을 때 묶어진 디딤돌들에서 나오는 최댓값들 중 최솟값을 구하기"였습니다. 왜냐하면 k개 만큼 인접한 디딤돌들은 서로 커버가 가능하기 때문입니다. 그렇기 때문에 인접한 디딤돌들을 k개만큼 묶으면 묶인 디딤돌들은 내부에 존재하는 디딤돌의 최댓값만큼 버틸 수 있고 결국에는 묶인 디딤돌들의 최댓값 중 최솟값을 구하면 최대 건널 수 있는 카카오 친구들의 숫자를 구할 수 있게 됩니다. 1번.. 2021. 4. 23.
[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 > 풍선 터트리기 코딩테스트 연습 - 풍선 터트리기 [-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] 뉴스 클러스터링 문제 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 > 길 찾기 게임 코딩테스트 연습 - 길 찾기 게임 [[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] 오픈채팅방 문제 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.
728x90
반응형