알고리즘
-
카카오 블라인드 2021) 합승 택시 요금알고리즘/프로그래머스 카카오 2021. 3. 7. 18:12
합승 택시 요금 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 플로이드-와샬을 이용해서 쉽게 풀 수 있었다. 주어진 각 구간마다의 요금을 플로이드-와샬을 통해, 연결된 구간을 이동하는데 최소 비용을 저장해주었다. 이후, 문제에서 요..
-
카카오 블라인드 2021) 순위 검색알고리즘/프로그래머스 카카오 2021. 3. 7. 18:07
순위 검색 new ArrayList()).add(score); } } for(Map.Entry entry : map.entrySet()) { entry.getValue().sort(null); } return map; } private int getCounts(Map map, String query) { String[] queryCondition = getCondition(query.replaceAll(DEFAULT, NOTHING).replaceAll(QUERY_REGEX, SPACE)); String key = getKey(queryCondition); int score = Integer.parseInt(queryCondition[SCORE_INDEX]); List list = map.getOrDef..
-
카카오 블라인드 2021) 메뉴 리뉴얼알고리즘/프로그래머스 카카오 2021. 3. 7. 17:54
문제 해석을 잘못해서 푸는데 오래걸렸다. 세트 메뉴의 갯수가 같을 때, 주문한 수가 가장 많은 세트로 답을 구해주어야 한다. 처음에는 반대로 주문한 수가 많은 것들을 모아서, 세트 메뉴가 가장 많은 것을 답으로 리턴해주었다.. 이외에도, 주문받은 메뉴를 정수형 배열의 인덱스에 저장하며, 입력받은 course에 따라 리턴해주는 방법도 시도했었지만, 당연히 틀리는 방법이다. (문제 해석을 잘못해서 카운팅만 해주면 된다고 생각했었다.. ㅠ) 각설하고, 여러 차례 시도했는데 계속 틀려서 카카오 해설 힌트를 보고 permutation을 적용했다. 이 때, 미리 메뉴를 정렬해서 하는 방법이 더욱 효율적이겠지만, 처음에 비트마스크로도 접근을 했었어서, 이 코드를 지우기 아까워서 재활용했다. (효율적인 방법이라고는 말..
-
카카오 블라인드 2021) 신규 아이디 추천알고리즘/프로그래머스 카카오 2021. 3. 7. 17:41
신규 아이디 추천 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 문제 조건 아이디의 길이는 3자 이상 15자 이하여야 합니다. 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다. 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다. 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이디가 카카오 아이디 규칙에 맞는 지 검사하고 규칙에 맞지 않은 경우 규칙에 맞는 새로운 아이디를 추천 1단계 new_id의 모든 대문자..
-
BOJ) 카드 게임알고리즘/백준 2021. 3. 7. 17:30
카드 게임 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 문제 조건 1. 왼쪽 카드만 통에 버릴 수도 있고 왼쪽과 오른쪽 카드를 둘 다 통에 버릴 수도 있다. (점수 X) 2. 오른쪽 카드에 적힌 수 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다. 3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된..
-
BOJ) 계단 수 (1562 번)알고리즘/백준 2021. 3. 7. 17:19
계단 수 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 45656, 1210123 과 같이 각 자릿 수의 차이가 1씩 나는 수를 계단 수라고 한다. 자릿 수를 의미하는 n이 주어질 때, 이러한 계단수가 몇 개 존재하는지 구하는 문제다. 이 때, 모든 계단 수는 0으로 시작하지 않는다. DP와 비트 마스크를 활용해서 푸는 문제로, 각 자릿수, 0 ~9의 수, 비트마스크를 저장할 3차원 정수형 배열 DP를 이용해서 풀었다. 우선, n = 1인 경우, 0 ~ 9는 각각 자신 수 하나를 가진다. 이를 비트마스크로 표현해주면서, n을 증가시켰다. 0인 경우에는 0으로 시작할 수 없기 때문에, 0다음에 올 수 있는 수인 1만 dp에 추가시켜..
-
BOJ) 작업 (2056 번)알고리즘/백준 2021. 3. 3. 00:45
작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 작업의 개수 N이 주어지고, 다음 N줄에 거쳐 각 작업의 수행 시간과 선행돼야하는 작업의 숫자가 주어진다. K작업에서 선행되는 작업은 1 ~ K-1 사이의 작업이 주어진다. 이 문제는 DP와 위상정렬로 분류되어있다. 그래서, 위상정렬로 접근하려고 했다. ArrayList에 각 선행되는 작업들을 넣어주고, 선행작업이 없는 작업들을 Queue에 넣어주어 순회했었다. 각 작업은 상관관계가 없으면 동시에 진행되니까, group을 넣어주고, depth를 함..