척척학사의 코딩 여행💻

문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 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..

이분 탐색 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다.배열의 원소가 정렬되어있어야만 사용할 수 있다. 사용하는 상황 1) 특정 배열 안에 원소 x가 존재하는지 확인해야할 때 2) x이하, 또는 x이상의 원소가 몇 개 존재하는지 확인해야할 때 3) x와 가장 가까운 원소가 무엇인지 확인해야할 때 코딩테스트에서의 사용 상황 탐색 범위가 큰 상황에서 사용해라!1) 탐색 범위가 2000만을 넘어가는 상황2) 처리해야할 데이터의 개수나, 값이 1000만 단위 이상으로 넘어가는 상황-> 이진탐색과 같이 O(log N)의 속도를 갖는 알고리즘으로 처리해야함을 기억해야한다. 알고리즘 1. 탐색하고자 하는 배열을 오름차순 정렬한다 array.sorted() 2. start, end를 변수에 저장한다. a...

문제 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 알고리즘 정렬, 자료구조 1. n을 입력받는다. 2. 다음 과정을 n번 반복한다. a. 사용자에게 단어를 입력받는다. b. set에 삽입에 성공한다면 중복이 되지 않았다는 의미 -> (단어, 길이)를 배열에 저장한다. c. set 삽입 실패시 다음 반복문으로 넘어가면 된다. 3. 해당 배열을 삼항연산자를 이용해 다음과 같이 정렬하면 된다. a. 만약 단어의 길이가 같다면 단어(사전..

문제 https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 알고리즘 정렬 1. n을 입력받는다. 2. 반복문을 n번 반복한다. a. 입력을 받아서 점의 위치와 색을 입력받는다. b. 색은 key, 점의 위치를 value에 저장한다. (Int 배열 -> append) 3. dictionary의 value들을 정렬하여 sumOfArrow라는 함수를 호출한다. 1. 입력받은 배열의 길이가 1 이하라면 0을 return 한다. -> (런타임에러 예..

문제 https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 알고리즘 정렬, 자료구조 1. n을 입력받는다. 2. 반복문을 n번 수행한다. a. 입력된 정보를 파일명과 확장자로 분리한다. b. 딕셔너리에 저장한다. (key = 확장자, value = 횟수 3. key를 기준으로 정렬 한 후 key와 value를 출력한다. 나의 코드 let n = Int(readLine()!)! var fileSuffix = [String: Int]() for _ in 0 ...

문제 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 정렬 알고리즘 1. 국어 점수를 내림차순으로 정렬한다. 2. 국어 점수가 같다면, 영어 점수를 오름차순으로 정렬한다. 3. 영어 점수가 같다면, 수학 점수를 내림차순으로 정렬한다. 4. 수학 점수가 같다면, 이름을 오름차순으로 정렬한다. 나의 코드 struct Score { // 이름 및 점수 저장 var name: String var korean: Int var english: Int var math: Int } let n = Int(..

부르트포스 - 모든 경우의 수를 찾아 출력해야한다. - 재귀함수를 이용하여 문제를 해결하였다. 알고리즘 1. N과 M을 입력받는다. 2. 1번부터 N번까지 다음과 같은 함수를 호출한다. a. 현재 선택된 번호를 방문처리한다. (중복 없도록 구현하기 위해) b. selected[i]에 현재 번호를 저장한다. c. 다음 번호로 이동하여 재귀함수를 호출한다. d. 호출 횟수가 M과 동일하다면, selected에 저장된 것을 result에 저장한다. 3. result를 출력한다. let input = readLine()!.split(separator: " ").map{ Int(String($0))! } let n = input[0], m = input[1] var selected = [Int](repeating..