전체 글
-
백준 14719 빗물Algorithm/BOJ 2021. 5. 2. 14:13
출처: www.acmicpc.net/problem/14719 분류: 구현, 시뮬레이션 접근방식 고이는 빗물의 양을 구하는 문제였습니다. 고이는 빗물은 자신의 양쪽에 자신보다 더 큰 빗물이 있어야 합니다. 저는 처음에 스택으로 접근을 했는데요. 스택에 인덱스와 높이를 넣어주는데, 스택의 탑보다 더 작은 블록을 만나면 추가하고 같으면 새로운 블록으로 갈아치워줍니다. 더 큰 블록을 만나면 탑의 왼쪽과 새로 만난 블록 중 더 작은 높이를 비교하고 스택의 탑에 있는 인덱스와 지금 블록을 비교해서 둘 중 더 작은 높이와 탑의 높이를 빼서, 빗물을 채워주는 방식을 사용했었습니다. 가로 방향으로 칸칸히 채워나가는 방식을 생각했었습니다. 하지만 이렇게 하면, 왼쪽이나 오른쪽 끝이 비어있을 때 문제가 됩니다. 이를 별도로..
-
백준 1922 네트워크 연결Algorithm/BOJ 2021. 4. 30. 17:04
출처: www.acmicpc.net/problem/1922 분류: kruskal 접근방식 최소 비용으로 모든 간선을 연결할 수 있는 경우를 찾는 크루스칼 알고리즘을 연습해볼 수 있는 문제였습니다. 별다른 트릭은 없어서 크루스칼 알고리즘을 이해하고 있다면 쉽게 해결할 수 있습니다. 간선을 정렬하고 사이클이 생기지 않도록 합쳐주면서 간선의 개수를 노드-1개까지 선택해주면 됩니다. 사이클은 union-find 알고리즘으로 확인할 수 있습니다. 해결방법 let n = Int(readLine()!)! var graph = [[Int]](repeating: [Int](repeating: 10001, count: n+1), count: n+1) var unionTable = [Int]() for i in 0...n ..
-
백준 1981 후위 표기식Algorithm/BOJ 2021. 4. 26. 23:46
출처: www.acmicpc.net/problem/1918 분류: 스택 접근방식 말 그대로 후위표기식 변환에 관한 문제였습니다. 설명은 따로 포스팅으로 대체하겠습니다 :) 해결방법 var str = readLine()! var result = "" var oper = "" for char in str { if char == "(" { oper.append("(") } else if char == ")" { while let opr = oper.popLast() { guard opr != "(" else { break } result.append(opr) } } else if char == "*" || char == "/" { guard !oper.isEmpty else { oper.append(char)..
-
후위표기식 변환Algorithm/Theory 2021. 4. 26. 23:43
안녕하세요 :) 오늘은 사람들이 일반적으로 사용하는 중위표기식(infix)을 후위표기식(postfix)으로 변환하는 방법에 대해 알아보겠습니다. 후위표기식? 먼저 중위표기식과 후위표기식에 대해 알아볼까요? 사람들이 계산할 때 사용하는 수식을 중위표기식이라고 하는데, 3*5와 같이 피연산자 사이에 연산자를 두는 방법이에요. 이와달리 연산자를 피연산자 뒤에 놓는 방법을 후위표기식이라고 합니다. 위의 중위표기식을 후위표기식 35* 로 바꿀 수 있어요. 후위표기식을 사용하면 연산자 우선순위에 따라 사람이 머리 속에서 왔다갔다 하는 계산 대신 왼쪽부터 순서대로 계산할 수 있어서 컴퓨터에게 시킬 수식으로 적합하다고 합니다. 연산자는 기본적으로 사용하는 사칙연산(+, -, /, *)을 포함해 괄호, %, == 등 말..
-
백준 2493 탑Algorithm/BOJ 2021. 4. 22. 16:58
출처: www.acmicpc.net/problem/2493 분류: Stack 접근방식 인덱스와 탑의 높이를 스택에 담아두고, 현재 빌딩의 높이가 인덱스의 탑보다 크면 스택에 담겨있는 인덱스에 현재 빌딩의 인덱스를 저장해두는 방식으로 해결했습니다. 해결방법 let n = Int(readLine()!)! let building = readLine()!.split(separator: " ").map { Int(String($0))! } var received = [Int](repeating: 0, count: n) var stack = [(idx: Int, top: Int)]() for (idx, top) in building.enumerated().reversed() { while !stack.isEmpty..
-
백준 1958 LCS 3Algorithm/BOJ 2021. 4. 22. 12:30
출처: www.acmicpc.net/problem/1958 분류: LCS, 문자열, DP 접근방식 이번엔 3개 문자열의 LCS를 구하는 문제였습니다. 기존 LCS와 원리는 동일하고 이를 3차원 배열로 확장시키면 되는 문제였습니다. func lcs(_ strA: [Character], _ strB: [Character], strC: [Character]) -> Int { var table = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 0, count: strC.count+1), count: strB.count+1), count: strA.count+1) for a in 1...strA.count { for b in 1...strB.count { f..
-
Programmers Lv3) [2020 카카오 인턴십] 보석쇼핑Algorithm/Programmers 2021. 4. 21. 17:31
출처: programmers.co.kr/learn/courses/30/lessons/67258 분류: Lv3, 카카오 인턴십, 투 포인터 접근방식 투 포인터 방식으로 해결했습니다. 먼저 전체 보석 종류의 개수를 구해놓고 포인터를 움직이면서 모든 보석이 들어있는 경우를 체크해주는 방식입니다. 저는 처음에 조금 비효율적으로 접근했는데요, 보석의 개수를 체크해주면서 현재 시작 포인터의 보석이 여러 개라면 현재 보석을 더 들고 있을 필요가 없으니 포인터를 옮겨주는 방식을 사용했습니다. 전체 과정을 좀 더 설명드리면, 저는 시작 포인터가 끝에 도달할 때까지 반복문을 돌려주면서 먼저 보석이 모두 들어있는지 체크해서 최선이라면 결과를 바꿔주고 끝 포인터를 움직이면서 보석에 담아줍니다. 그리고 현재 시작 포인터의 보석..
-
Programmers Lv3) [2020 카카오 인턴십] 경주로 건설Algorithm/Programmers 2021. 4. 21. 17:16
출처: programmers.co.kr/learn/courses/30/lessons/67259 분류: Lv3, BFS 접근방식 BFS 방식으로 해결했습니다. 조금 확장된 개념이 들어가는데, 단순히 방문 체크에 더해서 비용과 방향까지 기록해주면서 탐색해나가면 됩니다. 방향까지 체크해주는 이유는 같은 가격이여도 어떤 방향에서 오는지에 따라 달라질 수 있기 때문입니다. 현제 체크되어 있는 방향의 비용보다 더 작다면 다시 방문해주는 방식이 되겠습니다. 저는 enum으로 방향을 정의해주고 (그냥 Int나 bool 변수 등으로 정의해도 상관없을 것 같습니다.) Point 를 하나 정의해서 가지고 있도록 해줬습니다. enum Direction: Int { case horizontal = 0, vertical } ty..