Jenikeju

내가 푼 풀이

- N자리 숫자에서 K개를 지울 때, 가장 큰 수로 만들려면, 앞자리일수록 수가 커야 한다.

- 이 말은 N자리 숫자를 지워서 재배열하는 것이 아닌, 단순히 그 위치에 있는 숫자를 지우기 때문에, 앞자리 쪽일수록 큰 수가 배치되어야 큰 수가 되는 것이다.

- 앞자리 인덱스부터 스택에 담아서, 그다음 인덱스의 숫자가 클 경우, 스택에 들어가 있는 숫자들 중 작은 값들을 모두 지워낸다.

- 예로 스택에 [1,2,3] 이 담겨있을 때, 그다음 숫자가 4라면 스택에 있는 4보다 작은 숫자를 K횟수만큼 빼낸다.

- 위 방법은 만약 숫자가 내림차순이 된 경우, 다음 인덱스와 비교해도, 큰 수가 나오지 않기 때문에

54321 인경우 앞자리부터 이미 큰 값으로 배치가 되어있으므로 K횟수만큼 pop 한다.

예제)

7자리 숫자 1231234에서 숫자 3개를 지웠을 때

숫자 1 :

• stack: []
• 스택이 비어있으므로 넣는다.

숫자 2 :

• stack: [1]
• 스택에서 2보다 작은 숫자들은 pop 하고, 2를 넣는다
• stack: [2]

숫자 3 :

• stack: [2]
• 스택에서 3보다 작은숫자들은 pop하고, 3을 넣는다.
• stack: [3]

숫자 1 :

• stack: [3]
• 스택에서 1보다 작은숫자들은 없다. 1을 넣는다.
• stack: [3, 1]

숫자 2 :

• stack: [3, 1]
• 스택에서 2보다 작은 숫자 1을 pop하고, 2을 넣는다.
• stack: [3, 2]
• 여기서 3번의 횟수를 모두 사용하였다.

숫자 3 :

• stack: [3, 2]
• 스택에서 3보다 작은숫자 2가 있지만, 이미 제거 횟수를 모두 썼기에, 3을 넣는다.
• stack: [3, 2, 3]

숫자 4 :

• stack: [3, 2, 3]
• 스택에서 4보다 작은 숫자들이 있지만, 이미 제거 횟수를 모두 썼기에, 4를 넣는다.
• stack: [3, 2, 3, 4]

이로써 만들어 낼 수 있는 가장 큰 수는 3234가 된다.

위 방식대로 코드로 구현해 보자.

import Foundation

let input = readLine()!.split(separator: " ").map{ Int($0)! }
var rmCount = input[1]
var num = readLine()!.map{ Int(String($0))! }
var stack = [Int]()

// 앞자리부터 스택에 넣는다.
// 스택의 맨 뒤가 현재 원소보다 작을 경우, 현재 원소보다 작은값들은 k번 만큼 지워준다.
// 숫자가 내림차순으로 되있는 경우, k번 지울 수 없기에 뒷부분을 남은 횟수만큼 지워준다.
for i in 0..<input[0] {
    if stack.isEmpty {
        stack.append(num[i])
        continue
    }
    while !stack.isEmpty && stack[stack.count - 1] < num[i] && rmCount > 0 {
        rmCount -= 1
        stack.popLast()
    }
    stack.append(num[i])
}

if rmCount > 0 {
    while rmCount > 0 {
        rmCount -= 1
        stack.popLast()
    }
}
print(stack.map{ String($0)}.joined(separator: ""))

내가 푼 풀이

- 처음에는 단순히 자연수 N과 크기가 비슷하고 작은 제곱수부터 빼면서 카운트를 했는데 실패가 떴다.

$$43 = 6^{2}+7 = 6^{2}+2^{2}+1^{2}+1^{2}+1^{2}$$

$$43 = 5^{2}+18 = 5^{2}+3^{2}+3^{2}$$

- 43은 위와 같이 N보다 작은 값중에 가장 큰 값을 빼가며 카운트하는 것은 정답이 아니게 될 수 있다.

- 가장 큰값을 빼가는 그리디방식은 이문제와 맞지 않다.

- dp[n] = 자연수 n의 제곱수의 항의 최소 개수라 정의하자.

- 제곱수 항의 개수가 최대가 되는 방법은 모든 제곱수가 1의 제곱이 되는 것이다.

- 초기값은 dp[n] = arr[n]이다.

- 1부터 n의 제곱근까지 자연수 n을 빼가며, 항의 최소개수를 입력한다.

- dp[n] = min(dp[n], dp[n - idx * idx] + 1) ( idx는 1부터 n의 제곱근까지의 범위)

이를 코드로 구현해 보자

import Foundation

var num = Int(readLine()!)!
var dp = [0] + Array(1...num)

// dp 입력
// dp[n]의 제곱수항의 갯수 최댓값은 모든 제곱수가 1인것
// n이 제곱수라면 dp[0] + 1 인 값이 최솟값이 되는것이다.
for i in 1...num {
    var idx = 1
    while idx * idx <= i {
        dp[i] = min(dp[i], dp[i - idx * idx] + 1)
        idx += 1
    }
}
print(dp[num])

내가 푼 풀이

- dp[i] = i번 인덱스 까지의 가장 큰 부분 수열의 합으로 정의하자.

- i번째 인덱스까지의 부분수열중 가장 작은부분수열은 arr[i] 자기 원소 하나만 가졌을때이다.

- dp[i] = arr[i]의 초기값을 가진다.

- 1부터 i-1번째 원소중 i번째 원소보다 작은 원소가 j번째에 있을때,

- j번째까지의 가장 큰 부분수열의 합이 i번째 원소와 더했을때 arr[i]의 초기값보다 커야한다.

위의 예시로 주어진 수열을 dp로 구하면 다음과 같다.

코드로 구현해보자.

import Foundation

// 배열 입력
let count = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
arr.insert(0, at: 0)
var dp = Array(repeating: 0, count: count+1)
var max = Int.min

// dp 입력
// dp[n] = n번째 인덱스까지의 가장 긴 부분수열의 합
for i in 1...count {
    dp[i] = arr[i]
    for j in 1..<i {
        if arr[j] < arr[i] && dp[i] < dp[j] + arr[i] {
            dp[i] = dp[j] + arr[i]
        }
    }
}

print(dp.max()!)

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

내가 푼 풀이

- 1번을 통해 접근할 수 있는 모든 노드의 갯수를 구한다.

- 단순히 1번과 연결되어 있는지 판단만 하기 때문에, 순서는 상관이 없으므로 BFS DFS 둘 다 사용 가능하다.

- 연결된 리스트들을 모두 탐색후, 방문했던 노드들의 개수 -1 출력 (1이 포함되어 있기 때문)

import Foundation

let comCount = Int(readLine()!)!
let netCount = Int(readLine()!)!
var graph = [Int: [Int]]()

// 인접리스트 저장
for i in 0..<netCount {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    if graph[input[0]] == nil {
        graph[input[0]] = [input[1]]
    } else {
        graph[input[0]]!.append(input[1])
    }
    if graph[input[1]] == nil {
        graph[input[1]] = [input[0]]
    } else {
        graph[input[1]]!.append(input[0])
    }
}

// BFS
// 인접한 노드를 방문하는것에 중점이기에, 순서는 상관이없어서 DFS를 사용해도 된다.
var visitedQueue = [Int]()
var needVisitQueue = [1]

while !needVisitQueue.isEmpty {
    var node = needVisitQueue.removeFirst()
    if visitedQueue.contains(node) { continue }
    visitedQueue.append(node)
    
    needVisitQueue += graph[node]!
}
print(visitedQueue.count - 1)

내가 푼 풀이

-  0번째열에 있는 지점에서 C-1열까지 연결이 된다면, 횟수를 올려준다.

- 연결이 되었다면, 연결된 지점들은 다른 문자열로 변환한다. (파이프는 겹칠수없기때문에)

- 만약 연결할 수 없더라도 이전에 연결했던 파이프라인들은 다른문자열로 변환한다. 다른지점에서 출발을해도, 연결될 수 없기때문이다.

- 위의 조건대로 코드로 구현해본다.

재귀적호출을 이용해 한 지점에서 연결할 수 있는 모든 위치들을 불러온다.

그렇게 마지막지점까지 도달한다면, 연결이된것이므로 연결된 위치들을 다른 문자열로 바꿔준다.

import Foundation

var inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [[String]]()
var result = 0
var isFind = false

// 배열 입력
for i in 0..<inputs[0] {
    var a = readLine()!.map{String($0)}
    arr.append(a)
}

// 현재 위치에서 오른쪽대각위, 오른쪽, 오른쪽대각아래 순으로 검사한다.
// 마지막열에 도달했다면, 경로를 찾은것,
// 경로를 찾았다면 이전의 재귀함수들을 모두 실행중단해준다.
func find(x: Int, y: Int) {
    arr[x][y] = "O"
    if y == inputs[1] - 1 {
        isFind = true
        result += 1
        return
    }
    if x > 0 && arr[x-1][y+1] == "." {
        if isFind { return }
            find(x: x-1, y: y+1)
    }
    if arr[x][y+1] == "." {
        if isFind { return }
        find(x: x, y: y+1)
    }
    if x < inputs[0] - 1 && arr[x+1][y+1] == "." {
        if isFind { return }
        find(x: x+1, y: y+1)
    }
    
}
for i in 0..<inputs[0] {
    isFind = false
    find(x: i, y: 0)
}
print(result)

ㅈ 

내가 푼 풀이

- (N K)는 (a+b)^N의 k번째 항의 이항계수이다.

- N = 0이면 (a+b)^0 = 1

- N = 1이면 (a+b)^1 = a + b 이므로 이항계수는 1 1 이된다.

위 이항계수는 다음과 같이 성립한다.

dp[n][k] = dp[n-1][k-1] + dp[n-1][k]가 된다.

점화식을 토대로 코드로 구현하면 다음과 같다.

import Foundation
// dp생성
var inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var dp = Array(repeating: Array(repeating: 0, count: inputs[0]+1), count: inputs[0]+1)

// k = 0 , k = n 인경우 1 저장
// k는 n보다 클 수 없다.
// 나머지 경우 점화식에따라 입력
for i in 0..<dp.count {
    for j in 0..<dp.count {
        if j > i {
            continue
        }
        if j == 0 || i == j {
            dp[i][j] = 1
        } else {
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007
        }
    }
}
print(dp[inputs[0]][inputs[1]])

내가 푼 풀이

- 주어진 배열 N x M에서 (1, 1)에서 (N, M)까지 이동하는 최소 칸 수를 구하면 된다.

- dp로 풀 수 있을꺼같지만, BFS를 이용해서 풀었다.

- 주어진 인덱스와 인접한 4방향 위치 중에 1인값들을 저장했다.

- maze[[Int]: [[Int]]] = key는 x, y값이고 value는 인접한 위치 중 이동할 수 있는 위치의 인덱스 x, y 들로 구성되었다.

- x =1, y = 1 부터 시작해서 인접한 위치를 탐색하며, 그 위치 중 이미 방문했던 곳이 있다면, 그곳까지의 칸수 + 1을 하는 방법을 사용했다.

위에 예시로 주어진 배열을 이용해서 예로들어본다.

네 방향으로 인접한 위치 중 방문할 수 있는 위치인지 파악하기 위해 (N+2) * (M+2) 크기로 만들어준다.

그리고 해당 위치까지 이동했을 때, 이동한 칸수의 최솟값을 저장할 배열 하나를 같은 크기로 만들어주고, [1,1]에 1을 저장.

인접한 인덱스 중 방문할 수 있는 위치를 리스트로 만든다.

[1,1]은 [2,1]과 인접하고, [2,1]은 [1,1]과 [3,1]이 인접한다.

[1,1]: [2,1]

[2,1]: [1,1], [3,1]

BFS를 이용해 1,1 이 인접한 위치로 이동하며, 이동한 위치 [2,1]에서 인접한 위치 [1,1], [3,1] 중 이미 방문했던 위치가 있다면,

그 위치 [1,1] 값 +1을 해준다.

그러면 결과배열에 다음과 같이 저장된다.

위 방법을 통해 방문할 수 있는 모든 위치를 지나게 된다면, 결과 배열은 다음과 같이 저장된다.

마지막 m, n 위치의 값을 출력하면 된다.

해당 알고리즘을 코드로 구현하면 다음과 같다.

import Foundation

// 결과배열 result
// 인접된 인덱스리스트 maze
var index = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [Array(repeating: 0, count: index[1]+2)]
var maze = [[Int]: [[Int]]]()
var result = Array(repeating: Array(repeating: 0, count: index[1]+2), count: index[0]+2)
result[1][1] = 1

// (N+2) * (M+2) 크기의 배열 만들기
for i in 0..<index[0] {
    var nums = Array(readLine()!).map{ Int(String($0))!}
    arr.append([0] + nums + [0])
}
arr.append(Array(repeating: 0, count: index[1]+2))

// 인접리스트 maze 입력하기
for i in 1...index[0] {
    for j in 1...index[1] {
        if arr[i][j] == 1 {
            if arr[i-1][j] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i-1,j]]
                } else {
                    maze[[i,j]]!.append([i-1,j])
                }
            }
            if arr[i][j-1] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i,j-1]]
                } else {
                    maze[[i,j]]!.append([i,j-1])
                }
            }
            if arr[i+1][j] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i+1,j]]
                } else {
                    maze[[i,j]]!.append([i+1,j])
                }
            }
            if arr[i][j+1] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i,j+1]]
                } else {
                    maze[[i,j]]!.append([i,j+1])
                }
            }
        }
    }
}

// 방문한 위치 배열
// 방문해야 할 위치 배열
var visitedQueue = [[Int]]()
var needVisitQueue = [[1,1]]

// BFS
while !needVisitQueue.isEmpty {
    var node = needVisitQueue.removeFirst()
    
    if visitedQueue.contains(node) { continue }
    visitedQueue.append(node)
    needVisitQueue += maze[node]!
    // 해당 위치가 시작지점이면 패스
    // 해당위치 이전의 방문한 위치가 있다면 그 위치의값 + 1
    if node == [1,1] {
        continue
    } else {
        for i in maze[node]! {
            if visitedQueue.contains(i) {
                result[node[0]][node[1]] += result[i[0]][i[1]] + 1
                break
            }
        }
    }
}

print(result[index[0]][index[1]])

내가 푼 풀이

- 그리디의 단골문제로 높은단위의 동전으로 최대한 거슬러주면된다.

- 무작정 거슬러주면 주어진 거스름돈으로 줄 수 없으므로, 5원을 받은 돈을 나눈 몫부터 1씩 차감하면서 나머지 2원으로 거슬러준다.

- 거스르지못하면 -1 출력

import Foundation

var money = Int(readLine()!)!
var result = 0
var max = money / 5
var isDone = false

// 5원으로 최대한 걸러줬을때, 2원으로 거를 수 있다면 동전갯수 출력
// 거스르지 못하면 5원의 갯수 1씩차감
// 5원의 갯수가 0개인데 2원으로 거스르지 못하면 -1 출력
while max >= 0 {
    var m = money - (max * 5)
    if m % 2 == 0 {
        result = max + (m / 2)
        isDone = true
        break
    } else {
        max -= 1
    }
}

if isDone {
    print(result)
} else {
    print(-1)
}