요 근래 일정이 많아지고 바빠졌다는 핑계(?)로 PS를 소홀히 했다. 근데 사실 핑계가 아니라 정말로 바쁘고 피곤했다.
고로, 문제를 꾸준히 풀기로 다짐했다.
사실 일주일에 5문제는 풀고 싶지만, 바빠서 현실적으로 1주당 3문제가 내가 지킬 수 있는 나와의 약속일 것 같다.
그럼 시작해보자.
문제 풀이를 할 때 마다 계속 추가됩니다.
cmd + F 를 통해 문제번호 찾기를 추천드립니다.
22.07.15 업데이트
22.07.18 업데이트
22.07.20 업데이트
22.07.23 업데이트
22.07.24 업데이트
22.08.14 업데이트
22.08.15 업데이트
22.08.18 업데이트
아래 깃허브 주소에서 모든 백준 문제풀이를 확인하실 수 있습니다.
https://github.com/SuminPark-developer/BaekJoonPS
GitHub - SuminPark-developer/BaekJoonPS: 백준 Swift PS
백준 Swift PS. Contribute to SuminPark-developer/BaekJoonPS development by creating an account on GitHub.
github.com
백준 Swift 1018번
문제 유형 : 완전탐색
난이도 : 실버4
처음 풀이(틀린 풀이)
시작점을 기준으로,
시작점부터 + 8 - 1까지 돌면서, 기준이 될 비교문자를 (B <-> W) 왔다리 갔다리 하면서, board[y][x]와 다르면 count를 증가시켜 answerArray에 저장 후 , 그 중 가장 작은 값을 출력하는 방법으로 풀었다.
TC 답이 안 나오길래 조금 더 고민해보니까, 이렇게 풀면 더 적게 칠할 수 있는 경우들을 놓치게 된다. 잘못하면 1개만 칠해도 되는걸 63개를 칠하게 될 수도 있는 풀이다. 이 방법은 패스! (BBWB... 일 때 사실 가장 처음에 있는 B만 바꾸면 되는데, 가장 처음 문자를 제외한 나머지 63개를 다 바꿔야 한다고 값이 나오게 된다.)
맞는 풀이
방법 1.
1번과 2번의 배열을 만든다. 그 후 board[startY][startX]를 1번배열처럼 만들기 위한 값, 2번배열처럼 만들기 위한 값 중 작은 값을 answerArray에 넣는다. 그 후 answerArray.min()!을 출력하면 된다.
하지만 방법1은 만약 사이즈가 8*8이 아니라, 100*100이라면...? 이 풀이는 사실 매우 매우 확장성이 좋지 않다.
방법 2. (선택)
케이스를 두가지로 나눈 뒤, 두가지 케이스 중 작은 값을 answerArray에 넣고, 그 후 answerArray.min()!을 출력하면 된다.
Case 1. 시작점이 W로 시작
- case 1-1. y홀, x홀 : "W"
- case 1-2. y홀, x짝 : "B"
- case 1-3. y 짝, x홀 : "B"
- case 1-4. y 짝, x짝 : "W"
Case 2. 시작점이 B로 시작
- case 2-1. y홀, x홀 : "B"
- case 2-2. y홀, x짝 : "W"
- case 2-3. y 짝, x홀 : "W"
- case 2-4. y 짝, x짝 : "B"
// MARK: - 1018번(완전탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var board: [[String]] = []
board.append(Array(repeating: ".", count: M + 1))
for _ in 0..<N {
board.append(["."] + readLine()!.map{String($0)})
}
let (endY, endX) = ((N - 8) + 1, (M - 8) + 1)
var answerArray: [Int] = []
for startY in 1...endY {
for startX in 1...endX {
let answerTemp: Int = min(startW(startY, startX), startB(startY, startX)) // W 시작 Case, B 시작 Case 중 작은 값 저장.
answerArray.append(answerTemp)
}
}
print(answerArray.min()!) // 가장 최소값 출력.
func startW(_ startY: Int, _ startX: Int) -> Int { // W로 시작 Case.
var count: Int = 0 // 변경 횟수 카운팅.
for y in startY..<startY + 8 {
for x in startX..<startX + 8 {
if ((y % 2 == 1) && (x % 2 == 1)) || ((y % 2 == 0) && (x % 2 == 0)) { // W여야 함.
if board[y][x] != "W" {
count += 1
}
}
else if ((y % 2 == 1) && (x % 2 == 0)) || ((y % 2 == 0) && (x % 2 == 1)) { // B여야 함.
if board[y][x] != "B" {
count += 1
}
}
}
}
return count
}
func startB(_ startY: Int, _ startX: Int) -> Int { // B로 시작 Case.
var count: Int = 0 // 변경 횟수 카운팅.
for y in startY..<startY + 8 {
for x in startX..<startX + 8 {
if ((y % 2 == 1) && (x % 2 == 1)) || ((y % 2 == 0) && (x % 2 == 0)) { // B여야 함.
if board[y][x] != "B" {
count += 1
}
}
else if ((y % 2 == 1) && (x % 2 == 0)) || ((y % 2 == 0) && (x % 2 == 1)) { // W여야 함.
if board[y][x] != "W" {
count += 1
}
}
}
}
return count
}백준 1018번 코드개선
// MARK: - 1018번(완전탐색 / 코드 개선)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var board: [[String]] = []
board.append(Array(repeating: ".", count: M + 1))
for _ in 0..<N {
board.append(["."] + readLine()!.map{String($0)})
}
let (endY, endX) = ((N - 8) + 1, (M - 8) + 1)
var answer: Int = Int.max
for startY in 1...endY {
for startX in 1...endX {
let answerTemp: Int = min(fill(startY, startX, "W"), fill(startY, startX, "B")) // W 시작 Case, B 시작 Case 중 작은 값 저장.
answer = min(answer, answerTemp)
}
}
print(answer) // 가장 최소값 출력.
func fill(_ y: Int, _ x: Int, _ bw: String) -> Int {
var count: Int = 0 // 변경 횟수 카운팅.
for i in 0..<8 {
for j in 0..<8 {
if (i + j) % 2 == 0 { // (홀, 홀) || (짝, 짝) -> bw와 같아야 함.
if board[y + i][x + j] != bw { // 같아야 하는데 다르면,
count += 1 // 변경.
}
}
else { // (홀, 짝) || (짝, 홀) -> bw와 달라야 함.
if board[y + i][x + j] == bw { // 달라야 하는데 같으면,
count += 1 // 변경.
}
}
}
}
return count
}백준 Swift 2841번
문제 유형 : 스택(Stack)
난이도 : 실버1
문제풀이방법을 생각하는 것 자체는 어렵지 않았다. 단지 원하는대로 구현이 안돼서 조금 당황하는 것 정도?다.
풀이 방법
0. 각 라인에 빈 stack(배열)을 생성한다.
1. 빈 스택이면 넣고 끝.
2-1. 새로 들어온 fret이 스택의 마지막 값보다 작으면, 스택의 마지막 값을 빼낸다. (스택의 마지막 값보다 작거나(2-3) 같아질 때(2-2)까지 반복하게 된다.)
2-2. 새로 들어온 fret이 스택의 마지막 값과 같으면 멈춘다.
2-3. 새로 들어온 fret이 스택의 마지막 값보다 크거나 or 커지게 되면, 이어 붙이고 멈춘다.
// MARK: - 2841번(Stack)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, P) = (input[0], input[1])
var stacks: [[Int]] = Array(repeating: [], count: N + 1)
var count: Int = 0
for _ in 0..<N {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (line, fret) = (input[0], input[1])
while true {
if stacks[line].isEmpty { // 그 줄의 스택이 비었으면,
stacks[line].append(fret) // 넣고 끝.
count += 1
break
}
if stacks[line].last! > fret { // 새로 들어온 프렛이 더 작으면, 그 줄의 스택에서 하나씩 빼냄.
stacks[line].removeLast()
count += 1
}
else if stacks[line].last! == fret { // 같으면, 멈춤.
break
}
else { // 새로 들어온 프렛이 더 커지는 순간이 오면, 그 줄의 스택에 넣고 멈춤.
stacks[line].append(fret)
count += 1
break
}
}
}
print(count)
백준 Swift 4796번
문제 유형 : 그리디
난이도 : 실버5
케이스를 2개로 나눠야 한다.
전체 V 중 P일을 최대한 사용하고, 남은 일수(= V % P)가 L일 이상인지 or 아닌지다.
Case 1. 남은 일수가 L일 이상인 경우의 TC는, (L = 1 / P = 3 / V = 17)
-> 우선 최대한 사용( = (V / P) * L)하고, L일을 사용하는데 문제가 없을만큼 남아 있기 때문에 그냥 L만큼 더해주면 된다.
Case 2. 남은 일수가 L일 미만인 경우의 TC는, (L = 8 / P = 9 / V = 24)
-> 우선 최대한 사용( = (V / P) * L)하고, L일을 사용하는데 문제가 있다. 그래서 남은 일수만큼(= V % P)만 더해줘야 한다.
// MARK: - 4796번
var caseCount: Int = 0
while true {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (L, P, V) = (input[0], input[1], input[2])
if L == 0 && P == 0 && V == 0 {
break
}
caseCount += 1
var answer: Int = -1
if V % P >= L { // 나머지가 이용가능한 L일 이상일 땐, L일만큼만 더해주면 됨.
answer = (V / P) * L + L
}
else { // 남은 나머지가 이용가능한 L일보다 적을 땐, 남은 나머지만큼 더해주면 됨.
answer = (V / P) * L + (V % P)
}
print("Case \(caseCount): \(answer)")
}22.07.23 업데이트 - 코드 개선
// MARK: - 4796번(그리디)
var caseCount: Int = 0
while true {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (L, P, V) = (input[0], input[1], input[2])
if L == 0 {
break
}
caseCount += 1
let answer: Int = (V / P) * L + min(L, V % P)
print("Case \(caseCount): \(answer)")
}백준 Swift 15686번
문제 유형 : 조합, 완전탐색
난이도 : 골드5
골드5 문제지만 어렵지 않은 문제다.
[풀이 방법]
각 입력에 맞게 board 세팅한다. 인덱스 0일 때를 의미 없는 걸로 채워주면 편하다. (난 -1로 채웠다.)
치킨집(2)들을 배열에 저장하고, M개를 선택하는 경우를 조합으로 구한다.
전체 치킨조합(chickenCombi)을 돌면서, 집(1)일 때
그 치킨집(chickens)과 집(1) 사이의 chickenDistance를 구한다. 여러 chickenDistance가 나올텐데 그 중 min을 구한다.
마지막으로, 각 경우(chickens)의 치킨거리의 합(sum)을 저장하는 distances 중 최소값을 구해주면 된다.
// MARK: - 15686번(조합, 완전탐색)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var board: [[Int]] = Array(repeating: [], count: N + 1)
func combi(_ nums: [(Int, Int)], _ targetNum: Int) -> [[(y: Int, x: Int)]] {
var result: [[(Int, Int)]] = []
func combination(_ index: Int, _ nowCombi: [(Int, Int)]) {
if nowCombi.count == targetNum {
result.append(nowCombi)
return
}
for i in index..<nums.count {
combination(i + 1, nowCombi + [nums[i]])
}
}
combination(0, [])
return result
}
for i in 1...N {
board[i] = [-1] + readLine()!.split(separator: " ").map{Int(String($0))!} // 0: 빈 칸, 1: 집, 2: 치킨집
}
var chickenCoords: [(Int, Int)] = [] // 치킨집들의 좌표 저장.
for y in 1...N {
for x in 1...N {
if board[y][x] == 2 { // 치킨집일 때,
chickenCoords.append((y, x))
}
}
}
//print(chickenCoords)
let chickenCombi = combi(chickenCoords, M) // 치킨집들 중, M개를 선택하는 경우의 좌표 모음.
//print(chickenCombi)
var distances: [Int] = [] // 치킨거리 모음.
for chickens in chickenCombi {
var sum: Int = 0
for y in 1...N {
for x in 1...N {
if board[y][x] == 1 { // 집일 때,
var chickenDistance: Int = Int.max
for chicken in chickens {
let distanceY: Int = abs(y - chicken.y)
let distanceX: Int = abs(x - chicken.x)
chickenDistance = min(chickenDistance, distanceY + distanceX)
}
sum += chickenDistance
}
}
}
distances.append(sum)
}
print(distances.min()!)백준 Swift 1389번
문제 유형 : BFS
난이도 : 실버1
일정이 바빠서 오랜만에 문제를 풀었는데, 못 풀겠었다. 3시간정도 고민해도 결국 못 풀었다가, 다음날(지금)에 다시 풀어서 해결했다.
기존의 풀던 감으로는 쉽게 풀었을 내용인데... 보자마자 어떤 문제인지도 파악 했는데... 풀이방법도 생각 되는데 구현이 잘 안됐다.
역시 꾸준함이 중요한 것 같다. 바쁜 시간이지만 짬을 더 내서라도 풀도록 노력해야겠다.
[풀이 방법]
1. 인접행렬을 구한다.
2. 1...N을 돌면서, y에서 (자기 자신을 제외한) destination에 도달하는 데 까지 걸리는 최단거리를 구하면 된다. 즉, BFS다.
2-1. y와 count를 큐에 저장한다.
2-2. 다음 지점(k)과 연결되어 있고, 미방문일 시 큐에 넣는다.
2-3. 만약 다음 지점(k)이 destination이면 return한다.
3. 각 인덱스들 중, 가장 작은 케빈 베이컨의 수의 인덱스 값을 구하면 된다.
// MARK: - 1389번(BFS)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, M) = (input[0], input[1])
var board: [[Int]] = Array(repeating: Array(repeating: 0, count: N + 1), count: N + 1) // 0인덱스는 자리채우기 용.
var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: N + 1), count: N + 1) // 0인덱스는 자리채우기 용.
for _ in 0..<M {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (A, B) = (input[0], input[1])
board[A][B] = 1
board[B][A] = 1
}
func visitedArrayInit() { // 방문배열 초기화 필요.
visited = Array(repeating: Array(repeating: false, count: N + 1), count: N + 1) // 0인덱스는 자리채우기 용.
for i in 1...N {
visited[i][i] = true
}
}
func bfs(_ y: Int, _ destination: Int) -> Int {
var q: [(Int, Int)] = [(y, 0)] // (y, count)
while !q.isEmpty {
let (y, count) = q.removeFirst()
if y == destination { // 목적지 도착이면,
return count
}
for k in 1...N {
if board[y][k] == 1 && !visited[y][k] {
visited[y][k] = true
// if k == destination { // 목적지 도착이면,
// return count + 1
// }
q.append((k, count + 1))
}
}
}
return -1
}
var answerIndex: Int = 1
var minValue: Int = Int.max
for start in 1...N {
var sum: Int = 0
for destination in 1...N {
if start != destination { // 자기자신은 제외.
sum += bfs(start, destination)
visitedArrayInit() // 방문배열 초기화.
}
}
if sum < minValue { // 더 작은 케빈 베이컨의 수(sum)가 등장 시,
minValue = sum
answerIndex = start
}
}
print(answerIndex)백준 Swift 1915번
문제 유형 : DP
난이도 : 골드4
전에 풀어본 것 같은 기억은 나는데, 결국 못 풀었다. (https://developer-p.tistory.com/205)
다행인 건... 어떤 문제의 유형인지는 바로 알았다는 점?
[풀이 방법]
1. 0행과 0열을 우선 저장한다. dp의 점화식이 적용되지 않는 부분이기 때문이다.
2. dp = (y, x)칸을 우하단으로 하는 정사각형의 (최대) 한 변의 길이다.
2-1. 1...n행, 1...m열까지 돌면서, dp = min(↑, ←, ↖) + 1 을 구한다.
2-2. maxValue * maxValue를 구해주면 답이다. (이차원배열에서 flatMap을 쓰면 쉽게 일차원배열로 변경할 수 있다.)
// MARK: - 1915번(DP)
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (input[0], input[1])
var arr: [[Int]] = Array(repeating: [], count: n)
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: m), count: n)
for y in 0..<n {
let input = readLine()!.map{Int(String($0))!}
arr[y] = input
}
for y in 0..<n {
dp[y][0] = arr[y][0]
}
for x in 0..<m {
dp[0][x] = arr[0][x]
}
for y in 1..<n {
for x in 1..<m {
if arr[y][x] == 0 { // 0일 땐, 사각형 X.
dp[y][x] = 0
}
else { // 1일 때,
dp[y][x] = min(dp[y - 1][x], dp[y][x - 1], dp[y - 1][x - 1]) + 1 // min(↑, ←, ↖) + 1
}
}
}
let maxValue: Int = dp.flatMap{$0}.max()!
print(maxValue * maxValue)백준 Swift 17136번
문제 유형 : 백트래킹
난이도 : 골드2
백준 1915번을 활용하면 될 것 같다고 생각하고 고민했는데, 사실 풀이방법과 전혀 상관 없었다...
백트래킹 문제는 처음 풀어본 것 같다. 쭉 풀던 DP문제를 마무리 하고 나선, 백트래킹 문제들을 풀어봐야겠다.
[풀이 방법]
0. board를 10*10칸으로 세팅하고, 각 종류별 사용 갯수를 저장할 paper배열을 선언한다.
1. backtracking(0, 0)을 시작으로,
1-1. 최종 목적지(y == 10)에 도달하면, min answer를 저장한다.
1-2. 열의 끝(x == 10)에 도달하면, 다음 행으로 이동한다. (backtracking(y + 1, 0))
1-3. board[y][x]가 0이라면, 다음 열로 이동한다. (backtracking(y, x + 1))
1-4. board[y][x]가 1이라면, 색종이 size를 1부터 5까지 돌면서,
2. 가능한 경우라면(isPossible) 색종이를 붙이고(mark() - board값을 0으로 저장) 다음 열로 이동한다. (backtracking(y, x + 1))
3. 또한, 안 돼서 돌아올 경우 색종이를 떼어주는(mark() - board값을 1로 되돌림) 원상복구를 해줘야 한다.
4-1. answer가 여전히 25라면 불가능한 경우이기 때문에 -1을 출력하고
4-2. 아니라면 answer를 출력하면 된다.
코드에 주석처리된 print문을 출력해본다면 이해가 좀 더 쉬울 것이다.
코드에 자세한 설명이 써 있고, 아래 이미지는 도움이 안된다.
// MARK: - 17136번(백트래킹)
var board: [[Int]] = Array(repeating: [], count: 10)
for i in 0..<10 {
board[i] = readLine()!.split(separator: " ").map{Int(String($0))!}
}
var paper: [Int] = Array(repeating: 0, count: 5 + 1) // 종류별 사용한 색종이의 수.
var answer: Int = 25 // 최대 : 5장 다 사용 * 5종류
func isPossible(_ coordY: Int, _ coordX: Int, _ paperSize: Int) -> Bool { // 좌측상단(y, x)의 색종이를 덮을 수 있는지.
if paper[paperSize] == 5 { // 해당 종류의 색종이를 다 썼다면,
return false
}
if (coordY + paperSize > 10) || (coordX + paperSize > 10) { // 좌표값 넘어가면,
return false
}
for y in coordY..<coordY + paperSize {
for x in coordX..<coordX + paperSize {
if board[y][x] == 0 { // 0이 있어서 못 덮는 상황이라면,
return false
}
}
}
return true // 여기까지 온 거라면, 덮을 수 있다는 뜻이기 때문에 true리턴.
}
func mark(_ coordY: Int, _ coordX: Int, _ paperSize: Int, _ value: Int) { // 색종이 덮는 함수. (혹은 떼어냄)
for y in coordY..<coordY + paperSize {
for x in coordX..<coordX + paperSize {
board[y][x] = value
}
}
if value == 0 { // 색종이를 덮음.
paper[paperSize] += 1 // 색종이 사용 횟수 증가.
}
else if value == 1 { // 색종이를 떼어냄.
paper[paperSize] -= 1 // 색종이 사용 횟수 감소.
}
}
func backtracking(_ y: Int, _ x: Int) {
if y == 10 { // 최종 도달.
answer = min(answer, paper.reduce(0, +))
// print(paper, answer)
return
}
if x == 10 { // 열의 끝에 도달.
backtracking(y + 1, 0) // 다음 행으로 넘어감.
return
}
if board[y][x] == 0 { // 못 덮는 곳이면,
backtracking(y, x + 1) // 다음 열로 넘어감.
return
}
for size in 1...5 {
if isPossible(y, x, size) { // (y, x)에 size의 색종이를 덮을 수 있다면,
mark(y, x, size, 0) // (y, x)에 size의 색종이를 0으로 덮음.
// print("before: \(y), \(x), \(size)")
backtracking(y, x + 1) // 다음 열로 이동.
mark(y, x, size, 1) // 원상복구. (y, x)에 다시 기존값으로 되돌려놓음.
// print("after: \(y), \(x), \(size)")
}
// else {
// print("불가능: \(y), \(x), \(size)")
// }
}
}
backtracking(0, 0)
print(answer == 25 ? -1 : answer)
최근댓글