그리디
-
백준 1049 기타줄Algorithm/BOJ 2020. 6. 8. 16:18
출처: www.acmicpc.net/problem/1049 분류: 그리디 접근방식 패키지와 낱개의 가격이 주어지고 고장난 기타줄 이상을 살 수 있는 최소가격을 구하는 문제입니다. 최소 가격을 구하는 문제이므로 패키지와 낱개 각각의 최소값에만 신경쓰면 됩니다. 동전나누기와 비슷하죠? 낱개 6개 가격이 패키지 가격보다 싸지만 않다면 패키지만큼 다 나눠주고 나머지랑 패키지랑 비교해서 풀면 됩니다. 해결방법 let n = readLine()!.split(separator: " ").map{Int($0)!} var minPackage = Int.max var minPiece = Int.max for _ in 0.. minPiece * 6 { print(n[0] * minPiece) } else { var tota..
-
백준 1946 신입 사원Algorithm/BOJ 2020. 6. 8. 15:54
출처: www.acmicpc.net/problem/1946 분류: 그리디 접근방식 다른 사람보다 서류와 면접 점수가 모두 낮은 경우엔 탈락, 합격한 사람의 수를 구하는 문제입니다. 서류 1등은 무조건 합격입니다. 1등보다 면접 등수마저 낮다면 그 사람은 탈락이 되겠죠. 이때 1등의 면접 등수가 서류 2등 ~ 나머지 사람의 합격을 가르는 기준점이 됩니다. 1등의 면접 점수보다 낮은 사람을 모두 거르고 나면 남아있는 사람 중 서류 1등이 다시 합격의 기준점이 되죠. 이를 반복해주면 합격자의 수를 구할 수 있습니다. 하지만 이렇게 해주면 시간 초과가 납니다. (Swift 기준) 매번 나머지를 다시 도는건 너무 비효율적인 방법이죠. 보다 효율적으로 해결할 수 있는 방법이 있습니다. 서류 1등의 면접 등수를 기준..
-
백준 1120 문자열Algorithm/BOJ 2020. 6. 8. 14:58
출처: www.acmicpc.net/problem/1120 분류: Greedy 접근방식 앞뒤로 아무 문자나 붙여서 길이를 같이 만들 때 차이가 가장 적은 경우를 찾는 문제입니다. 앞뒤로 아무 문자나 붙일 수 있으므로 현재 문자열과 비교할 문자열만 가지고 비교하면 나머지는 길이를 맞춰버릴 수 있습니다. 예제 케이스처럼 adaabc aababbc 를 보면, 0번 인덱스부터 adaabc와 adaabc의 길이만큼인 aababb 와 비교해보면 다른 개수는 3개입니다. 나머지는 adaabc 뒤에 c를 붙여버리면 길이를 똑같이 만들 수 있겠죠 1번 인덱스부터 adaabc와 adaabc의 길이만큼인 ababbc 와 비교해보면 다른 개수는 2개입니다. 마찬가지로 앞에 a를 붙여서 길이를 똑같이 만들 수 있겠죠 해결방법 ..
-
백준 1541 잃어버린 괄호Algorithm/BOJ 2020. 6. 7. 15:18
출처: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 분류: Greedy +와 -만으로 이루어진 연산이 들어올 때 괄호를 묶어서 최소인 수를 만드는 문제입니다. + 연산부터 해주고 - 연산을 해주면 최소의 값을 구할 수 있습니다. - 로 우선 다 잘라준 다음에 각각을 다 더해주고 마지막에 빼주는 방식으로 해결했습니다. import Foundation var str = readLine()! var plusOpers = str.components(sepa..
-
Programmers) Lv2 조이스틱Algorithm/Programmers 2020. 1. 29. 16:50
출처: https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 | 프로그래머스 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 예를 들어 아래의 방법으로 JAZ를 만들 수 있습니다. - 첫 번째 위 programmers.co.kr 분류: Lv2, Greedy 너무너무 어려웠던 문제... 하 어렵네..