[코테 필수 알고리즘] 코테 4시간 전 벼락치기 ^.^

 
자주 나오는 항목이라고 한다.
옛날옛즉 구현했던거 위주로 정리해서 둬봄
 

• 이진 탐색
• 그리디
• 구현
• DFS/BFS
• 정렬
• 다이나믹 프로그래밍(DP)
• 최단 경로(다익스트라)
• 그래프 이론

 
 
[O(logN)] 이진탐색 : start, end, min를 사용
 
백준 예시문제: n.12015 가장 긴 증가하는 부분수열(gold2)

import Foundation
let n = Int(readLine()!)!
let array = readLine()!.split(separator: " ").map { Int($0)! }
var LIS = [array.first!]

for i in 1..<n {
    if LIS.last! < array[i] {
        LIS.append(array[i])
        continue
    }
    
    var start = 0
    var end = LIS.count
    
    while start <= end {
        let mid = (start + end) / 2
        
        if LIS[mid] < array[i] {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    LIS[start] = array[i]
}

print(LIS.count)

 
 
 
 
[O(nlogn)] 그리디: 최선 선택
 

절차

1. 선택 절차: 현재 상태에서 최적인 선택을 하는것. 선택은 바뀌지 않는다.
2. 적절성 검사: 선택 항목이 문제의 조건에 만족하는지 확인 만족하지 않으면 항목 제외
3. 해답: 모든 선택이 완료되면 최종선택이 문제의 조건을 만족하는지 확인

 
 
 
백준예시문제: n.11501 주식(silver2)

import Foundation

func solution() {
    let count = Int(readLine()!)!

    for _ in 0..<count {
        let day = Int(readLine()!)!
        var stock = readLine()!.split(separator: " ").map{ Int($0)! }
        var revenue = 0

        var maxNum = stock[stock.count-1]

        for i in stride(from: stock.count-1, through: 0, by: -1) {
            if maxNum < stock[i] {
                maxNum = stock[i]
            } else if stock[i] < maxNum {
                revenue += maxNum - stock[i]
            }
        }
        print(revenue)
    }
}

solution()

 
 
구현: 말 그대로 알아서 구현
 
DFS(우선깊이탐색)/BFS(너비우선탐색)
 
 
DFS
1. 방식: 깊이 우선 탐색은 그래프의 깊이를 우선적으로 탐색. 즉, 한 노드에서 시작해 갈 수 있는 가장 깊은 곳 까지 탐색하고, 더 이상 갈 곳이 없으면 다시 돌아와 다른 경로 탐색
2. 자료 구조 : 스택 사용
3. 특: 모든 경로 추적에 적합, 메모리사용량 적으며, 경로가 깊거나 연결리스트와 같은 구조일때 유용
 
BFS
1. 방식: 너비 우선 탐색은 그래프의 너비를 우선적으로 탐색. 즉, 한 노드에서 시작해 인접한 모든 노드를 먼저 탐색 후 다음 인접 노드를 탐색
2. 자료 구조: 큐 사용
3. 특: 최단 경로찾기에 적합, 루트 노드에서 목표 노드까지 거리가 짧을 때 유용
 
 
백준예시문제 : n.2667 단지번호 붙이기(silver1)
 
먼저 DFS로 풀었던 것

import Foundation

let n = Int(readLine()!)!
var graph: [[Int]] = []
var num: [Int] = []

for _ in 0..<n {
    let row = readLine()!.map { Int(String($0))! }
    graph.append(row)
}

let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]

var count = 0

func DFS(x: Int, y: Int) -> Bool {
    if x < 0 || x >= n || y < 0 || y >= n {
        return false
    }
    
    if graph[x][y] == 1 {
        count += 1
        graph[x][y] = 0
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            _ = DFS(x: nx, y: ny)
        }
        return true
    }
    return false
}

var result = 0

for i in 0..<n {
    for j in 0..<n {
        if DFS(x: i, y: j) {
            num.append(count)
            result += 1
            count = 0
        }
    }
}

num.sort()
print(result)
for count in num {
    print(count)
}

 
이것을 BFS로 변경하면 이렇게 됨

import Foundation

let n = Int(readLine()!)!
var graph: [[Int]] = []
var num: [Int] = []

for _ in 0..<n {
    let row = readLine()!.map { Int(String($0))! }
    graph.append(row)
}

let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]

func BFS(x: Int, y: Int) -> Int {
    var queue: [(Int, Int)] = [(x, y)]
    var count = 0
    graph[x][y] = 0
    
    while !queue.isEmpty {
        let (cx, cy) = queue.removeFirst()
        count += 1
        
        for i in 0..<4 {
            let nx = cx + dx[i]
            let ny = cy + dy[i]
            
            if nx >= 0 && nx < n && ny >= 0 && ny < n && graph[nx][ny] == 1 {
                graph[nx][ny] = 0
                queue.append((nx, ny))
            }
        }
    }
    
    return count
}

var result = 0

for i in 0..<n {
    for j in 0..<n {
        if graph[i][j] == 1 {
            let componentSize = BFS(x: i, y: j)
            num.append(componentSize)
            result += 1
        }
    }
}

num.sort()
print(result)
for count in num {
    print(count)
}

 
 
 
 
정렬은 아니까.,. pass
 
 
 
다이나믹 프로그래밍(DP)
 
1) Overlapping Subproblems(반복적인 동일 문제)
2) Optimal Substructure(최적 부분 구조)
 
백준예시문제: n.11053 가장 긴 증가하는 부분수열(silver2)

import Foundation
let n = Int(readLine()!)!
let inputArray = readLine()!.split(separator: " ").map { Int(String($0))! }
var dp: [Int] = []

for i in 0..<n {
    dp.append(1)
    for j in 0..<i+1 {
        if inputArray[j] < inputArray[i] {
            dp[i] = max(dp[i], dp[j]+1)
        }
    }
}

print(dp.max()!)

 
 
 
최단경로(다익스트라): 그리디 + 동적계획법으로, 두 노드를 잇는 최단 경로를 찾는것명확히 구현해본적없어서 빠르게 패스 ^.^
 
 
그래프 이론: DFS, BFS의 기반인듯?
 
 
내가.. 코테를 칠 줄 몰랐다.. 재미로라도 풀어봤어서 다행인 부분 ㅠ,ㅜ~





+ 누가 백준 실1 이하 해답 안보고 풀수있으면 웬만한 코테 통과한댔는데 실제로 그런것같기도! (어마무시 대기업 제외)

이거 보고있는 누군가, 화이팅하세요 ~,~!