algorithm
-
백준 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) [2019 카카오블라인드] 길 찾기 게임Algorithm/Programmers 2021. 4. 21. 16:50
출처: programmers.co.kr/learn/courses/30/lessons/42892 분류: Tree 접근방식 주어진 노드 정보를 가지고 이진트리를 구성한 후 전위순회, 후위순회 결과를 반환하면 되는 문제였습니다. 노드 정보는 [Int]로 x, y 값이 주어지는데, 같은 레벨의 노드는 모두 y값이 같고, y값이 클수록 상위 레벨의 노드입니다. 따라서 y값을 기준으로 sort해주고 차례대로 이진트리를 구성해주면 됩니다. 저는 순회할 때 인덱스를 반환해야 하므로, 노드에 index 값을 가지고 있도록 했습니다. x,y 정보도 그냥 배열 그대로 들고있도록 해줬어요. class Tree { var value: [Int] var index: Int var leftChild: Tree? var rightC..
-
백준 11049 행렬 곱셈 순서Algorithm/BOJ 2021. 4. 21. 14:08
출처: www.acmicpc.net/problem/11049 분류: DP 접근방식 전체 순서를 유지하면서 특정 연산을 해야할 때 연산 순서를 어떻게 해야 최소가 될까? 에 관한 문제였습니다. 11066 파일합치기 와 유사한 문제였다는 생각이 드네요. 핵심 아이디어는 X ~ Y까지 연산의 최소값을 DP에 계속 저장해나가는데, X ~ Y까지 연산의 최솟값은 (X~K) + (K~Y) 연산들 중 최소를 찾아나가는 것입니다. 문제의 예시를 가지고 생각해보겠습니다. 각 행렬이 배열에 들어있다고 생각하면, (5x3) - 0 (3x2) - 1 (2x6) - 2 0 ~ 1 까지의 최소값은 dp[0][1], 0 ~ 2 까지의 최소값은 dp[0][2] 에 담는 것입니다. 0 ~ 2 까지의 최솟값은 ( [0][1] 을 먼저 ..
-
백준 17070 파이프 옮기기 1Algorithm/BOJ 2021. 4. 20. 12:38
출처: www.acmicpc.net/problem/17070 분류: DP, 백트래킹 접근방식 주어진 요구사항 대로 파이프의 이동 가능 위치를 잘 계산하고 나면 백트래킹으로 도착한 경우의 수를 세주면 되는 문제였습니다. 파이프의 끝 점에서 출발한 경로는 역시 다시 방문해줄 필요가 없으므로 방향을 고려한 3차원 배열에 이를 기록해서 방문 횟수를 줄여줬습니다. 조금 귀찮긴 하지만 크게 어렵지는 않아서 풀이를 보시면 이해가 되실거에요 :) 해결방법 let n = Int(readLine()!)! var map = [[Int]]() for _ in 0.. Direction { if pipe.0.r == pipe.1.r, abs(pipe.0.c - pipe.1.c) == 1 { return .horizontal } ..