728x90
반응형
DP Easy문제들을 풀어보았다.
자세한 설명들은 주석에 달아두었다.
easy부터 시작해서 감을 익혀 나가야겠다.
1. Best Time to Buy and Sell Stock
- Point
- 사고 파는 이윤을 최대로
- 구입가를 최저로
class Solution {
func maxProfit(_ prices: [Int]) -> Int {
// 현재 최대 수익은 0
var maxProfits = 0
// 현재 최소 구입가는 prices[0]
var buy = prices[0]
// price를 돌며
for i in 1..<prices.count {
// 현재 최고 수익과, 현재가 - 구입가를 비교
maxProfits = max(maxProfits, prices[i] - buy)
// 구입가는 현재 구입가와 현재가를 비교한다.
buy = min(buy, prices[i])
}
// 배열이 순차적으로 진행되기에 index를 거스르는 판매행위는 일어나지 않는다.
return maxProfits
}
}
2. Counting Bits
- Point
- 비트연산
- 몫과 나머지
// 첫 풀이
class Solution {
func countBits(_ n: Int) -> [Int] {
// 1의 갯수를 세줌
for i in 0...n {
ans.append(String(i, radix: 2).filter {$0 == "1"}.count)
}
return ans
}
}
// 비트 연산 사용 풀이
class Solution {
func countBits(_ n: Int) -> [Int] {
if n == 0 {
return [0]
}
// 0,1인 경우 모두 적어두고
var ans = [0,1]
// 2부터 시작
var idx = 2
// n까지 조건을 주고 돌면서
while idx <= n {
// ans[몫] + ans[나머지]
// 비트 연산으로 계산
ans.append(ans[idx >> 1] + ans[idx % 2])
idx += 1
}
return ans
}
}
3. In Subsequence
- Point
- 등장 순서
- 배열의 크기
class Solution {
func isSubsequence(_ s: String, _ t: String) -> Bool {
// 비어있어도 하위 배열 가능
if s.isEmpty {
return true
}
// 배열화
var s = s.map { String($0) }
// 현 위치
var idx = 0
// t를 돌며
for w in t {
// 같을 경우 다음 idx로
if String(w) == s[idx] {
idx += 1
}
// idx가 s의 배열과 같다면 모두 순서대로 포함하고 있는 것
if idx == s.count {
return true
}
}
return false
}
}
4. Min Cost Climbing Stairs
- Point
- 최소 출발값 선택
- 1,2칸 뛸 수 있기에 마지막, 마지막-1 고려해야함
class Solution {
func minCostClimbingStairs(_ cost: [Int]) -> Int {
// 각 경우의 최소 cost를 저장하기 위함
var arr = Array(repeating: 0, count: cost.count)
// 0,1번째는 바로 저장
// 출발선 위치이기에
arr[0] = cost[0]
arr[1] = cost[1]
// idx 2부터 시작
for i in 2..<cost.count {
// i-1, i-2 중에서 작은 값에서 출발해야 한다.
// 최솟값 + 현재값
// 계속 누적되어 최솟값으로 계산된다.
arr[i] = min(arr[i-1], arr[i-2]) + cost[i]
}
// 마지막 배열 끝 이상으로 나갈 수 있는 경우는
// 배열의 총 길이 -1 , -2인 경우이다.
// 그렇기에 이 두 개를 비교하여 최솟값을 반환해준다.
return min(arr[arr.count-1], arr[arr.count-2])
}
}5. Count Sorted Vowel Strings
- Point
- 이전의 값들을 계속 더해준다.
- 주어진 수만큼 반복
class Solution {
func countVowelStrings(_ n: Int) -> Int {
// 기본 배열
var res = [1,1,1,1,1]
// n만큼 반복
for i in 1...n {
// 이전 값들을 계속 더해준다.
// 결국에 가장 마지막 원소는
// 이전의 원소들을 다 더한 값이 된다.
for j in 1...4 {
res[j] += res[j-1]
}
}
return res.last!
}
}
6. Count_Square_Submatrices_with_All_Ones.swift
- Point
- 행렬을 2x2로만 판단하여 계속 누적해나간다.
--행렬 index--
대각(i-1, j-1) 위(i, j-1)
왼쪽(i-1, j) 기준(i, j)
----
1 1
1 1
----
인 경우 왼쪽, 대각, 위의 최솟값이 1이라는 것은 2x2로 만들 수 있다는 것을 의미한다.
----
1 1
1 2
----
이 처럼 표기하여 2x2가 가능하다는 것을 알린다.
그리고 최솟값이 2인 경우 그건 3x3으로 만들 수 있다는 것을 의미한다.
----
1 1 1
1 1 1
1 1 1
----
기존 배열이 이와 같았다면 아래와 같은 순서로 바뀌게 된다
----
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 > 1 2 1 > 1 2 2 > 1 2 2 > 1 2 2 > 1 2 2
1 1 1 1 1 1 1 1 1 1 2 1 1 2 2 1 2 3
----
최종 배열에서 원소들의 합을 구해주면 답이 된다.
class Solution {
func countSquares(_ matrix: [[Int]]) -> Int {
// matrix 복사
var temp = matrix
// 행
for i in 1..<matrix.count {
// 열
for j in 1..<matrix[0].count {
// temp 행렬 그림
// 대각 위
// 왼쪽 기준
// 왼쪽
let l = temp[i-1][j]
// 위
let u = temp[i][j-1]
// 대각
let c = temp[i-1][j-1]
// 최솟값 구하기
let minC = min(c,min(l,u))
// 박스의 최솟값이 0이면 그냥 값 그대로 두기
if min(temp[i][j], minC) == 0 {
continue
// 최솟값이 0이 아닌 경우
} else {
// 오른쪽 아래 원소에 최솟값 + 1을 할당한다.
// 1 1
// 1 1
// 위 케이스에 해당하기에
// 1 1
// 1 2
// 이처럼 변경하여 해당 박스는 2x2도 가능하다는 것을 기입해둔다.
// 이후 돌면서 최솟값이 2가 되면 3개까지 가능하다는 말이다!
temp[i][j] = (minC+1)
}
}
}
return temp.flatMap{$0}.reduce(0,+)
}
}728x90
반응형