척척학사의 코딩 여행💻

문제 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 고정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오 코드 (반복문 사용) 더보기 // 반복문 사용 import Foundation let input = readLine()!.split(separator: " ").m..

문제 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고, 룰은 다음과 같다. 숫자가 쓰인 카드들이 N * M 형태로 놓여있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 예를 들어 3 * 3 형태로 카드르이 다음과 같이 놓여 있다고 가정하자. 3 1 2 4 1 4 2 2 2 여기..

문제 ‘큰 수의 법칙’은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순..

문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러줘야 할 동전의 최소 개수를 구해라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 풀이 탐욕적인 아이디어: 가장 큰 화폐 단위부터 돈을 거슬러준다. 코드 import Foundation var n = Int(readLine()!)! var result = 0 let coinTypes = [500, 100, 50, 10] for coin in coinTypes { result += (n / coin) n %= coin } print(result) 분석 시간 복잡도 O(K) 시간 복잡도는 동전의 총..

그리디(탐욕법)가 무엇인가? 어떤 문제가 있을 때, 단순 무식하게 문제를 푸는 알고리즘 지금 당장 좋은 것만 고르는 방법이다. 현재 선택이 나중에 미칠 영향은 고려하지 않는다. 언제 적용하면 되는가? 문제의 유형이 매우 다양해서 많이 풀어보며 감을 익히자. 우선 문제를 많이 풀어서 감을 익히자! 사전 지식 없이도 풀 수 있는 경우가 존재하지만, 아이디어 떠올리려면 연습이 필요! 문제를 읽었는데 어떤 유형인지 감이 안 잡히면 Greedy -> DP / Graph 순서로 의심해보자 Greedy로 풀기 위해서는 탐욕적인 방법을 떠올리고, 정당한지 검토할 수 있어야한다! 연습문제 1. 거스름 돈 2. 큰 수의 법칙 (해설 있음) 3. 숫자카드게임 4. 1이 될 때까지 (해설 있음) 이것이 코딩테스트다를 읽고 작..

문제 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 않에 들어가는 떢의 총 길이는 절단기로 잘러서 맞춰준다. 절단기에 높이를 지정하면 줄지어진 떠을 한 번에 절단한다. 높이가 H보다 긴 떡은 H위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 19, 14, 10, 17cm인 떡이 나란히 있고, 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15 cm가 될 것이다. 잘린 떡의 길인느 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 길이가 총 M일 때 적어도 M만큼의 떡을 얻기..

문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개의 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 5 8 3 7 9 2 3 5 7 9 no yes yes 이분 탐색 알고리즘 이용 1. 재귀함수 이용 let n = Int(readLine()!)! let parts = readLine()!.split(separator: " ").map { Int($0)! }.sorted() let m = Int(readLine()!)! let estimate = readLine..