본문 바로가기

백준177

[Swift][DP] 백준 10844번 (쉬운 계단 수) 요구능력 : DP와 2차원 배열을 이용한 규칙 코드설명 : 계단수라고 하여서 1의 자리는 안될거 같았는데 예제보니까 됩니다. 길이가 N인 계단 수라서 N = 1이면 한자리 N = 2이면 두자리입니다. n = 1 1, 2, 3, 4, 5, 6, 7, 8, 9 n = 2 12, 21 23, 32 34, 43 45, 54 56, 65 67, 76 78, 87 89, 98 10 여기까지만 보고 직접 n = 3일때를 맨뒷자리 기준으로 하나만 적어보면 n = 3 dp[3][3] 123 323 543 343 이 됩니다. 맨뒷자리 기준으로 봤을 때 배열을 dp[i][j]라고 하면 3앞에 2와 4는 j - 1과 j + 1이 됩니다. 그리고 2와 4의 앞에 1과 3 5와 3 또한 j - 1과 j + 1이 됩니다. 이렇게 .. 2021. 9. 1.
[Swift][Qeque] 백준 10845번 (큐) 요구능력 : 큐 코드설명 : 큐를 구현하였다. 후기 : 학교에서 자료구조시간에 배운적이 있어서 무난히 풀이했다. var queue: [Int] = [] func push(_ n : Int) { queue.append(n) } func pop() -> Int { if size() == 0 { return -1 } else { return queue.removeFirst() } } func size() -> Int { return queue.count } func empty() -> Int { return queue.isEmpty ? 1 : 0 } func front() -> Int { return queue.first ?? -1 } func back() -> Int { return queue.last ??.. 2021. 8. 31.
[Swift][Greedy] 백준 5585번 (거스름돈) 요구능력 : 그리디 알고리즘 코드설명 : 그리디알고리즘은 말그대로 탐욕 알고리즘으로 현재상황에서 지금 당장 좋은것만 고르는 방법이다. 거스름돈이 적게나오려면 가장 큰 화폐단위부터 잔돈을 거슬러주면 된다. 그렇기 때문에 if문을 가장 큰 단위인 500엔부터 가장작은 단위인 1엔까지 넣어준것이다. 후기 : 그리디알고리즘이라는걸 처음 공부해서 한번 풀어보고 싶어서 풀어봤다. 이전에 풀었던것들중에 그리디가 좀 있는거같은데 그리디라는걸 몰라도 풀 수 있는 느낌? 굳이 그리디를 찾아서 풀려고 안해도될거같다. let n = Int(readLine()!)! var money = 1000 - n var count = 0 while true{ if money == 0 { break } if money >= 500 { mo.. 2021. 8. 31.
[Swift][DP] 백준 15990번 (1, 2, 3 더하기 5) 요구능력 : DP의 개념을 알고 규칙을 찾을 수 있느냐 코드설명 : 맨 오른쪽 수를 기준으로 규칙이 나온다. 1, 2, 3으로만 더하라고 했고, 중복된 수가 없어야한다고 했다. 수가 n이라고 가정하면, f(n) (n - 1) + 1 (n - 2) + 2 (n - 3) + 3 이 있다. 위 그림과 같이 f(5)까지 있다고 가정하면 아래와 같은 규칙이 나온다. f(5)의 4 + 1에서 4는 f(4)에 있는 2 + 2와 1 + 3으로 대체된다. 배열을 보면 dp[i][1] dp[i][2] dp[i][3] 이 있다. dp[i][1]은 수의 마지막자리가 1인 수의 개수를 저장 dp[i][2]은 수의 마지막자리가 2인 수의 개수를 저장 dp[i][3]은 수의 마지막자리가 3인 수의 개수를 저장 dp[i][1] = .. 2021. 8. 31.