Swift
-
백준 17609 회문Algorithm/BOJ 2021. 5. 3. 11:07
출처: www.acmicpc.net/problem/17609 분류: 투포인터 접근방식 하나를 제거해서 펠린드롬이 될 수 있는 유사 펠린드롬인지까지 확인해야 하는 문제였습니다. 처음에 반례를 생각 못하고 잘못 접근해서 틀렸었는데요, 양쪽 끝(s, e)에서부터 확인하다가 문자가 다를 때, s+1 문자와 e 문자가 같은지, 아니라면 s문자와 e-1 문자가 같은지 확인하고 둘다 아니라면 2를 출력하게 했었는데요, 여기의 반례는 baaba 가 됩니다. s = 0, e = 4 에서 다를 때 s+1와 e 번째 문자는 둘다 a 로 같은데 이때는 유사회문도 될 수 없습니다. 하지만 맨 뒤의 문자 a를 지워서 s == e-1 로 확인하면 유사회문이 되는 걸 확인할 수 있습니다. 따라서 (s+1, e) 와 (s, e-1) ..
-
백준 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..