Algorithm20 [Level 2] 큰 수 만들기 숫자로 이루어진 문자열과 k가 주어진다. 해당 문자열에서 k개의 숫자를 제외하고 만들 수 있는 가장 큰 수를 반환하는 것이 문제이다. 숫자의 순서는 바뀌면 안된다. 예를 들어 4912에서 가장 작은 수 2개를 제외 후 9와 4로 94라는 수를 조합하는 게 아니라, 순서는 유지하되 가장 큰 수의 배열인 92를 만드는 것이다. 따라서 맨 앞자리부터 값을 채운다고 할 경우, 특정 범위에서 가장 큰 값을 골라 현재 채워야 할 자리에 넣어주면 된다. 채워야 할 문자열의 길이는 (number.size - k) 이다. 예제 2의 경우 1231234에서 3자리를 제외한 4자리를 채우면 된다. 그러면 다음과 같이 빈칸을 4개 두고 맨 앞자리부터 차례대로 채운다고 생각하면 이해하기 쉽다. _ _ _ _ 그런데 단순히 모든.. 2021. 9. 20. [Hackerrank] Sherlock and The Beast https://www.hackerrank.com/challenges/sherlock-and-the-beast/problem Sherlock and The Beast | HackerRank Find the largest number following some rules having N digits. www.hackerrank.com void decentNumber(int n) { if(n < 3) { cout 2021. 9. 8. [Level 2] 점프와 순간이동 | C++ 문제 설명 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return.. 2020. 9. 23. 합병 정렬(Merge sort)을 구현해보자 개인적으로 공부하는 내용이므로 틀린 부분이 있을 수 있습니다. 있다면 알려주세요 :) Merge sort는 분할정복법(Divide and Conquer)을 사용한다. 분할정복을 사용하는 대표적인 정렬 알고리즘은 퀵 소트, 머지 소트, 힙 소트가 있다. 분할정복이란 해결하고자 하는 하나의 큰 문제를 동일한 크기의 여러개의 분할로 나누고, 분할된 작은 문제를 해결(정복)하여 합병을 통해 합쳐주는 것이다. 각각의 문제를 순환적으로 해결하기 위해 보통 재귀를 사용한다. 머지 소트의 동작을 그림으로 나타내면 다음과 같다. 정렬이 되지 않은 배열 {4, 8, 13, 2, 23, 16}이라는 하나의 큰 문제를 동일한 크기로 재귀적으로 분할한다. 가장 작은 크기인 1개의 분할에 도달하면 각 분할을 정렬된 상태로 합친다.. 2020. 8. 3. [Level 2] 위장 - 해시 | C++ [문제] 문제는 우선 간단하다. 얼굴, 상의와 같은 종류의 의상들이 주어지는데 그들 중 최소 1개 이상의 조합의 가지수를 구하는 것이다. 물론 같은 종류의 의상은 중복으로 착용할 수 없다. 예제를 살펴보면 첫 번째 예제의 경우 headgear 종류의 의상이 2개 eyewear에 해당하는 의상이 1개이므로 총 2개의 종류와 의상의 개수는 3개이다. 따라서 1개의 조합, 2개의 조합으로 입을 수 있으며 총 5가지의 수가 나온다. [풀이] 우선 해시맵을 이용하여 key-value 쌍을 (종류-의상들)로 저장한다. 예를 들면 "face" - ["crow_mask, "blue_sunglasses, ...]와 같은 식이다. 이렇게 분류한 뒤 종류 별로 조합하여 가능한 경우의 수를 모두 구하면 된다. 이 부분이 핵심.. 2020. 5. 28. [Level 2] 소수 찾기 - 완전 탐색 | C++ [문제] 인자로 0~9의 연속된 문자열이 주어지는데, 각 숫자(문자)로 만들 수 있는 소수(prime number)의 수를 구하는 문제이다. 레벨은 낮은데 뭔가 접근하기가 어려워서 구글링을 하던 도중 에라토스테네스의 체라는 알고리듬에서 아이디어를 얻었다. 에라토스테네스의 체는 간단하게 말해서 소수를 구하는 방법인데, 구하고자 하는 구간의 값을 모두 구한 뒤 그 중에서 소수가 아닌 수를 걸러내는 방법이다. 나는 위 문제에서 주어진 값을 내림차순으로 정렬하여, 주어진 수로 만들 수 있는 최대 값을 구하고, 해당 값 이하의 모든 값을 구하여 그 중에서 소수를 걸러내었다. 그리고 그 소수 중 주어진 수로 만들 수 있는 개수를 구하였다. 요약해서 단계로 나타내면 다음과 같다. 주어진 문자열(numbers)를 1개.. 2020. 5. 26. 이전 1 2 3 4 다음
