Outgoing Introvert

△ 누적 합 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 ..

○ Math, Dynamic Programming, Memoization | Easy LeetCode 70. Climbing Stairs 내 답안. 배열에 저장 class Solution { func climbStairs(_ n: Int) -> Int { if n == 1 || n == 2 { return n } var result = [1,2] for i in 2.. Int { var (first, second) = (1, 1) for _ in 1..

○ Dynamic Programming | Easy 119. Pascal's Triangle II class Solution { func getRow(_ rowIndex: Int) -> [Int] { var row = [1] if rowIndex == 0 { return row } for i in 1...rowIndex { var newRow = Array(repeating: 1, count: i + 1) for j in 1..

○ Dynamic Programming | Easy 118. Pascal's Triangle 제출 답안 30분 append([1]) 해주고 더한 값들 append 해주고 마지막에 append 1 해주는 방법 class Solution { func generate(_ numRows: Int) -> [[Int]] { var result = [[1]] for i in 1..

○ 프린터 큐 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) 출력 와 같이 요세푸스 순열을 출력한다. 큐로 분류..

△ 큐 Silver4 백준 2164 카드2 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.N이 주어졌을 때, 제일 ..

× 큐 백준 18258 큐2 Swift 에 회의감이 들게 하는 문제다,, 계속 시간초과 뜨는데 아무리 다양한 방식으로 구현해봐도 내 코드는 어디가 문제인지 전혀 모르겠고,, 알고리즘 구현을 잘못해서 발생하는 문제는 아닌거같은데 Swift 입출력이 느려서 그렇다나뭐라나 아무튼 개빡침,, FileIO 사용해서 어케어케 하면 통과시켜주는듯,, 백준에서는 시간초과로 통과를 안시켜주지만 Swift에서 더블스택을 사용하여 큐를 구현했을 때 생기는 의문점이 있어 공유해본다. 보통 시간복잡도가 O(n)인 removeFirst()를 사용하지 않고 dequeue를 효율적으로 구현하는 방식으로 다음 두 가지를 흔히 사용한다. 1. 포인터를 사용한 큐 구현 2. 더블 스택 큐 를 제시한다. 1. 포인터 사용 removeFir..