코딩하는 드래곤 🐲

[링크] programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr [풀이] 문제 설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항..

[링크] programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr [풀이] 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 예를 들어 begin이 hit, target가 cog, words가 [hot, dot, dog, lot, log, cog..

[링크] programmers.co.kr/learn/courses/30/lessons/67258# 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr [풀이] 프로그래머스 2020 카카오 인턴 기출문제입니다. 문제 설명은 다음과 같습니다. 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 ..

[링크] programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr [풀이] 2020 카카오 인턴십 문제인 키패드 누르기입니다. 단순히 구현하면 되는 문제이기 때문에 난이도가 Level 1인 것 같습니다. 문제 설명은 다음과 같습니다. 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 ..

[링크] programmers.co.kr/learn/courses/30/lessons/42579# 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr [풀이] 장르별로 노래들을 정리하고, 재생 횟수가 가장 많은 장르부터 차례대로 두곡씩 선택하면 되는 문제입니다. 한 장르에서 두 곡을 선택하는 기준은 재생 횟수가 가장 많은 곡부터 차례대로 선택하는 것이며, 재생 횟수가 같은 곡이라면 고유 번호가 낮은 곡부터 선택하면 됩니다. 따라서 문제 조건에 따라 고려해야 할 것은 다음과 같습니다. 장르별 노래 정리 장르별 재..

[링크] programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr [풀이] 그래프를 탐색하여 시작 노드로부터 가장 멀리 떨어진 노드의 개수를 세는 문제입니다. 문제에 주어진 조건에 따르면 시작 노드는 1이고, 무방향 그래프입니다. 그래프를 탐색하는 문제이기 때문에 BFS 또는 DFS를 사용하면 될 것 같다는 생각이 떠오릅니다. 그러나 탐색 시작 노드로부터 거리를 재는 것이기 때문에 DFS가 아닌 BFS를 사용하여 문제를 풀었습니다. BFS는 큐를 사용해서 구현할 수 있습니다. 우선 BFS로 탐색할 그래..

[링크] programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같�� programmers.co.kr [풀이] 주어진 음식들의 스코빌 지수가 K이상이 되도록 섞고, 그 섞은 횟수를 return 하면 되는 문제입니다. 문제에서 제시하는 조건은 다음과 같습니다. 모든 음식들의 스코빌 지수가 K이상이다. 가장 맵지 않은 음식과 두번째로 맵지 않은 음식을 더해 새로운 음식을 만든다. 섞어서 새롭게 만든 음식의 스코빌 지수는 다음과 같이 계산합니다. 섞은 음식..

[링크] programmers.co.kr/learn/courses/30/lessons/68935 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr [풀이] 숫자 n을 3진법으로 변환한 뒤, 변환된 3진법을 반전시킨 다음 다시 10진법으로 계산하는 문제였습니다. 숫자 n을 k진법으로 변환할 수 있는지 확인하는 문제입니다. 1. 숫자 n을 k진법으로 변환하는 방법은 다음과 같습니다. 1) n을 k로 나눈 나머지를 k진법으로 변환한 숫자의 오른쪽부터 채워감 2) n을 k..

[링크] programmers.co.kr/learn/courses/30/lessons/42577# 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조�� programmers.co.kr [풀이] 한 번호가 다른 번호의 접두어인 경우 false를 return 하면 되는 문제이다. vector의 find(value)함수를 이용하면 value의 위치의 시작 인덱스를 리턴하는데, 이 성질을 이용해서 문제를 풀었다. 따라서 접두어인 경우는 find가 반환하는 인덱스가 0일 것이다. 모든 원소들에 대해서 확인하기 위해서 이중 for문을 이용했다. [참..

[링크] programmers.co.kr/learn/courses/30/lessons/12906 코딩테스트 연습 - 같은 숫자는 싫어 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 programmers.co.kr [풀이] n이 최대 1,000,000이기 때문에 O(n)으로 문제를 풀었다. arr 벡터를 첫 원소부터 확인하면서 answer 벡터에 추가하는데, answer 벡터의 마지막 원소가 현재 확인하고 있는 원소랑 같은 원소면 추가하지 않고 continue하도록 구현했다. [참고] 벡터의 erase와 알고리즘 헤더에 존재하는 unique함수를 같이..