Outgoing Introvert

△ 투 포인터, 누적 합 Gold 4 백준 1806 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 부분합의 합이 S 이상이 되는 것들 중에서, 가장 짧은 부분합의 길이를 구하는 문제. 내 답안 - 76292 KB,..

△ 그리디 Silver1 백준 1931번 회의실 배정 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주..

○ 그리디 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 그리디 유형의 대표 문제 동전 가능한 범위 내에서 무조건 가치가 큰 동전부터 더해나가면 되는 문제. 처음에 결과값..

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..

○ 프린터 큐 Silver3 (40분) 백준 1966번 프린터 큐 포인터를 사용한 큐로 구현 : 69108KB 8ms 히히 제출 답안들 중에 내가 시간 젤 빨라뚬 ^^ 뿌듯 근데 구현 중에 계속 조건 몇개 놓치느라 생각보다 오래걸림,, 40분이라니,, 집중해서 시간만 좀 단축하자..! 구현 방법 중요도 배열 priority 에서 최대값 max를 먼저 구해준다. priority 의 인덱스 0 부터 탐색 1) 해당 인덱스의 중요도가 max일 경우 - 해당 인덱스의 element를 0으로 변경해준 후 프린트가 되었기 때문에 result += 1 해준다. - 만약 해당 인덱스가 타겟 인덱스와 동일하다면 반복문을 빠져나오기 - 아니면 max 값을 업데이트 해준다. 2) 해당 인덱스의 중요도가 max 보다 낮을 경..

○ 큐 / 구현 Silver5 백준 11866 요세푸스 문제 문제 요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력 와 같이 요세푸스 순열을 출력한다. 큐로 분류..