평생공부하는사람

안녕하세요. 오늘은 프로그래머스 큰 수 만들기 문제를 풀어보도록 하겠습니다. 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 우선 탐욕(greedy) 알고리즘에 대해서 알아보겠습니다. 탐욕 알고리즘은 순간순간에서 local한 최적값을 선택하여 global한 최적값을 도출해나가는 알고리즘입니다. 하지만 알고리즘 예시에서 보듯이 완전하게 정렬되지 않은 경우(Heap)에는 최적값을 못찾는 단점이 있습니다. 이제 문제를 풀어보겠습니다. 이 문제는 한 숫자씩 최대값을 찾아서 answer에 넣어주면 되는 문제입니다. 첫 탐색에서는 0 ~ K 번째 까지 탐색하고 최대값은 N1 번째자리수에서 찾았을경우 두번째 탐색에서는 N1 + 1 ~ K+1까지 탐색하고 최대값은 N2번 번째자리수에서 찾았을경우 세번..

안녕하세요. 오늘은 프로그래머스 완전탐색 카펫문제를 풀어보겠습니다. 이 문제는 간단한 방정식 문제인데요. 다들 중학교때 배웠던 근의 공식을 이용해서 문제를 쉽게 푸실수 있으니 식을 보시고 천천히 상기해보시기 바랍니다! import Foundation func solution(_ brown:Int, _ yellow:Int) -> [Int] { // 2x + 2y - 4 = brown // x * y - 2x - 2y + 4 = yellow // x * y = brown + yellow // x = (brown + yellow) / y // x + y = (brown + 4) / 2 // y + ((brown + yellow) / y) = (brown / 2) + 1 // y^2 - ((brown + 4) ..

안녕하세요. 오늘은 프로그래머스 H-Index문제를 풀어보겠습니다. 이 문제가 정렬 카테고리에 있지만 정렬로 굳이 안풀어도 문제가 해결 됩니다. 우선 정렬로 문제를 해결하려면 인용횟수를 정렬시키고 h-index를 찾아가는 방법이 best이겠지만 문제 제약 조건을 보면 굳이 그럴 필요가 없어 생구현으로 문제 풀이가 가능합니다. import Foundation func solution(_ citations:[Int]) -> Int { var count:Int = Int() var hIndex = 0 while true { count = 0 hIndex += 1 for i in citations { if i >= hIndex { count += 1 } } print(count) if count < hIndex..

안녕하세요. 오늘은 다리를 지나는 트럭 문제를 풀어보겠습니다. 우선 이 문제는 제약조건에 의해 문제에서 제시해준 방법대로 풀어도 시간 초과가 나지 않으므로 문제의 풀이 방법대로 구현하였습니다. 우선 구조체로 weight와 seconds를 포함한 다리 위의 truckStatus 구조체를 만들어 주었습니다. 그리고 while문에서 시간(answer)을 측정하면서 문제의 풀이처럼 구현해줍니다. 우선 while문 조건으로 "두가지 queue가 모두 비어있으면 탈출합니다"로 설정하였습니다. 그리고 다리위의 queue가 비어있지 않다면 시간을 증가시켜주고 맨앞의 트럭이 다리길이만큼 시간이 지났다면 dequeue해줍니다. 그리고나서 다리위의 트럭의 토탈 무게를 측정하고 대기트럭이 있다면 대기 트럭의 앞트럭이 올라갈수..

안녕하세요. 오늘은 프로그래머스 괄호 회전하기 문제를 풀어보겠습니다. 괄호와 관련된 문제는 대부분 Stack 자료구조를 이용하면 문제를 해결하실수 있습니다. Stack은 Swift의 배열을 이용해서 append()와 removeLast()만 이용해서 사용하시면 됩니다! 이 문제도 마찬가지로 Stack 자료구조를 이용해서 문제를 풀어보겠습니다! 1. 문자열을 회전시킨다. var s1 = s[s.index(s.startIndex, offsetBy: i)...s.index(s.endIndex, offsetBy: -1)] if i != 0 { s1 += s[s.startIndex...s.index(s.startIndex, offsetBy: i-1)] } 2. push or pop 결정한다. var isPop =..

안녕하세요. 오늘은 프로그래머스 후보키 문제를 풀어보겠습니다! 후보키 문제는 여러가지 알고리즘을 섞어만든 문제인데요! 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr row&column이 max 8*20이기 때문에 어떤 방법으로해도 전략만 잘 세운다면 시간초과날 일은 없을듯합니다! 처음에는 재귀알고리즘을 이용하여 combination을 하여 후보키 후보조합을 만들어줍니다! 이 후 sort..

안녕하세요! 오늘은 프로그래머스의 예상 대진표 문제를 풀어보겠습니다! 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 이 문제는 tree의 공통 부모 노드를 찾는 문제입니다! 대진표가 완전 이진트리여서 동일한 부모노드가 나올때까지 ÷2 로 나누어주시면 됩니다! 그러기 위해서는 각각의 Index를 이진트리에 맞춰주어야하는데요. n이 2^x 이기 때문에 n - 1 + a, n - 1 + b로 인덱스를 바꾸어주시면 됩니다! import Foundation func solution(_ n:I..

안녕하세요. 오늘은 프로그래머스 조이스틱 문제를 풀어보겠습니다! 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 조이스틱 문제는 분류된 카테고리와 같이 탐욕알고리즘으로 문제를 해결하실 수 있습니다! 우선 알파벳과 알파벳간의 최소 이동거리를 구해줍니다! 삼항연산자를 이용해 최적값을 구해줍니다! for i in name.utf8 { count = Int(i)-Int(a.asciiValue!) count = count > 26-count ? 26-count : count makeNameCount..

안녕하세요. 오늘은 프로그래머스 소수 찾기 문제를 풀어보겠습니다. 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 이 문제는 재귀를 이용한 완전탐색을 통해 소수판별 알고리즘을 적용하여 문제를 해결 하실 수 있습니다! 우선 순서가 상관없으니 순열을 적용해야합니다. 순열은 재귀의 for문에 0부터 시작하면 순열입니다! (순서가 상관있다면 이전 index를 가져와서 index+1부터 탐색하시면 됩니다.) 또한 모두 안뽑아도 되고 모두 뽑아도 되므로 해당 숫자가 들어가있을때 한번 안들어가있을때 한번 재..

안녕하세요! 오늘은 프로그래머스 2레벨 가장 큰 수 문제를 풀어보겠습니다! 이번 문제는 음... 반례를 못찾아 실수를 많이해서 시간이 오래걸렸는데요! 우선 반례를 제공해드릴테니 테스트 해보시기 바랍니다! // 1-6 번 걸리시는 분 [3, 32] "332" [3, 34] "343" [0, 0, 1000, 1] "1100000" [87, 878] "87887"