Outgoing Introvert

○ 그리디 Silver4 백준 11047번 동전 0 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 그리디 유형의 대표 문제 동전 가능한 범위 내에서 무조건 가치가 큰 동전부터 더해나가면 되는 문제. 처음에 결과값..

내가 사랑하눈 네이버 지도를 사용해 볼 일이 생겼다. 내가 제일 많이 사용하는 앱이 네이버 지도 앱이라 몬가 지도 사용해서 뭔가를 만들어 보고싶었는데 드디어 사용해봄!! 문서에 사용 설명도 친절하게 잘 되어 있어서 어렵지는 않았다. 신기하고 재미써뚬 ㅎㅎ 1. SDK 설치 네이버 지도 SDK 사용하려면 cocoapods로 설치해야 하는데 대용량 파일을 받기 위해서는 또 brew 를 먼저 설치 해줘야 된대서 homebrew 먼저 설치,, 요기 가서 다운 받으면 됨 👉🏻 https://brew.sh/ /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)" 요러케만 하면 M1에서는 오류가 난다...

그리디 Greedy 알고리즘이란? 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않고, 오직 현재 시점에서 가장 좋은 선택을 하는 알고리즘 ex) 대표적인 문제 : 백준 11047 동전 0 미래를 고려하지 않고 현재 내릴 수 있는 최선의 선택에만 집중하기 때문에 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지는 않는다. 항상 최적의 해를 찾을거라는 보장은 없기 때문에 근사 알고리즘이라고도 한다. 코테에서 그리디 알고리즘 사용 가능한 조건? 코딩테스트에서는 최적 해가 보장되는 조건에서만 그리디 알고리즘을 사용해야 한다. (보통 코테에서 그리디 문제는 이렇게 얻은 해가 최적의 해가 되는 상황으로 풀리도록 출제가 된다고 함) - 현재의 선택이 미래의 선택에 영향을 주지 않을 때 - 부분의 최적 ..

누적 합 Prefix Sum 배열에서 구간 합을 구해야 하는 문제에서 중첩 for 문을 사용해 값을 계속 더해주면 O(n^2) 시간 만큼 걸리지만 누적 합을 사용하면 계속 더해줄 필요 없이 마이너스 연산 만으로 해결 가능하다. O(1) 동적 계획법 문제들에서 DP로 연산 결과를 저장할 때에도 누적 합 방식이 많이 사용되는 듯 하다. * prefixsum 만들 때 index 0 말고 1부터 담아야 만들기 쉬움 psum 1, ~2, ~3, ~4 … suffix sum 은 뒤에서 부터 더하는 것. 알고리즘 대회 같은데서 가끔 나오긴 하는데 코테에서는 잘 안나옴. 구간쿼리 구할 때 배열의 요소가 정적일 경우 psum 동적일 경우 펜윅트리(?) 1차원 배열일 때 누적 합 구하는 건 간단하지만 2차원 배열은 좀,,..

Gold3 × 누적 합, 수학, 순열과조합 백준 10986번 나머지 합 능력 밖의 문제였다,, 절대 풀 수 없어 1차 시도 : 시간초과 직관적으로 누적 합만 사용해서 간단하게 구현해보면 다음과 같다. n 의 범위가 100만 이하이니까 중첩 반복문으로 돌리면 O(n^2)으로 당연히 시간초과 뜰 줄 알았음 let nm = readLine()!.split(separator: " ").compactMap { Int($0) } let (n, m) = (nm[0], nm[1]) let arr = readLine()!.split(separator: " ").compactMap { Int($0) } var psum = Array(repeating: 0, count: n+1) for i in 1...n { psum[i]..

○ 다이나믹 프로그래밍, 누적 합 Silver1 백준 11660번 구간 합 구하기 5 시간은 한시간 넘게 걸린거같은데 한번만에 통과함 ㅎㅎ 어떻게 계산해야될지 방법을 찾기만 하면 구현이 어렵진 않았음. 생각해내는건 쉽지않았음 ㅎㅎ (뻔한 말인가,,?) 누적 합과 DP의 경계가 살짝 모호하지만 행렬을 사용하니깐 공간에 값을 저장해나가는 게 누적합을 사용한 DP에 좀 더 가까운 것 같다는 느낌? //85696KB 584ms let nm = readLine()!.split(separator: " ").compactMap { Int($0) } let n = nm[0] let m = nm[1] var matrix: [[Int]] = [Array(repeating: 0, count: n+1)] for _ in 0..

○ 누적 합 Silver3 백준 2559번 수열 문제 매일 측정한 온도(정수)의 수열이 주어질 때, 연속적인 며칠 동안의 온도 합이 가장 큰 값을 계산 입력 - N은 온도를 측정한 전체 날짜의 수. 2 ≤ N ≤ 100,000 - K는 합을 구하기 위한 연속적인 날짜의 수. 1 ≤ K ≤ N - 온도를 나타내는 N개의 정수는 모두 -100 이상 100 이하 구현 까지는 18분 걸렸고, 예외 처리(?) 9분 해서 총 27분 걸림 예외처리랄것도 없는데 result 값을 처음에 0으로 초기화 해서 틀렸다고 뜸. 모든 온도가 음수일 경우, max() 해주면 result 값으로 0이 그대로 출력되는 문제,, 처음부터 result 값을 0이 아니라 가능한 합의 값으로 설정해주는 것이 중요. 1. 누적 합 방식으로 ..

△ 누적 합 Silver3 백준 11659번 구간 합 구하기 4 첫번째 시도 - 시간초과 단순하게 받아온 배열 저장 후, 횟수 m만큼 for문을 돌려 합을 구해주는 방법 횟수 m의 범위가 10만이기 때문에, 최악의 경우 O(n^2) 10만 x 10만 으로 시간초과가 뜬다. let nm = readLine()!.split(separator: " ").compactMap { Int($0) } let m = nm[1] let arr = readLine()!.split(separator: " ").compactMap { Int($0) } for _ in 0..

○ 다이나믹 프로그래밍, 누적 합 Silver4 백준 10211번 Maximum Subarray 69104KB 12ms let t = Int(readLine()!)! for _ in 0..

× Dynamic Programming, Divide and Conquer | Medium LeetCode 53. Maximum Subarray for문 중첩해서 돌려서 O(n^2) 으로 풀었더니 당연히 시간초과 뜸,, Time Limit Exceeded 더보기 subarray 하나씩 더해가면서 값 저장하는 방식,, let solution = Solution() print(solution.maxSubArray([-2,1,-3,4,-1,2,1,-5,4])) //6 print(solution.maxSubArray([-2])) //-2 print(solution.maxSubArray([1])) //1 class Solution { func maxSubArray(_ nums: [Int]) -> Int { if ..