Swift
-
백준 16637 괄호 추가하기Algorithm/BOJ 2021. 3. 29. 12:03
출처: www.acmicpc.net/problem/16637 분류: 완전탐색 접근방식 크게 두 부분을 이해하면 문제를 해결할 수 있습니다. 1. 괄호치기 2. 연산하기 0. 전처리 먼저 저는 괄호가 쳐질 연산자를 선택하는 방법을 이용할 것이기 때문에 전처리 작업에서 숫자와 연산자를 각각 배열에 분리해서 담아줬습니다. for char in readLine()! { if char.isNumber { numbers.append(Int(String(char))!) } else { operators.append(char) } } 1. 괄호치기 "괄호가 중복되지 않는다" , "괄호 안의 연산자는 1개" 라는 조건을 이용해서 해결했습니다. 위 조건을 생각해보면 괄호 안의 연산자는 오직 1개뿐이므로 연산자 중에서 괄호..
-
백준 17471 게리맨더링Algorithm/BOJ 2021. 3. 28. 21:02
출처: www.acmicpc.net/problem/17471 분류: 완전탐색 접근방식 n이 최대 10밖에 안 되기 때문에 완전탐색으로 해결할 수 있었습니다. 각 구역을 0, 1 중 하나가 되는 조합을 뽑아서 해당 조합이 조건을 만족하는지 확인하는 방식으로 해결했습니다. 풀이를 떠올리는 건 어렵지 않았는데 구현에서 꽤나 시간을 잡아먹었네요.. 때문에 하나씩 차근차근 살펴보면서 정리해보겠습니다. 먼저 각 구역의 인구, 인접 구역, 파티(정당), 최소 차이 를 담을 변수들이 필요했습니다. 구역의 최대 인구가 100이기 때문에 모든 구역의 인구가 100이여도 차이는 1000을 넘지 않습니다. 초기값은 그냥 여유롭게 10000으로 잡아줬습니다. var population: [Int] = [0] var adjace..
-
백준 17136 색종이 붙이기Algorithm/BOJ 2021. 3. 28. 19:14
출처: www.acmicpc.net/problem/17136 분류: 완전탐색 접근방식 가능한 색종이를 열심히 붙이면 되는 문제였습니다. 처음엔 크기가 5x5인 색종이부터 먼저 붙여나가는 방식으로 접근했는데 이렇게 되면 틀리더라구요.. 반례가 있나봅니다. 따라서 백트래킹으로 모든 경우를 찾아주는 방식으로 접근해야 합니다!! 그리고 이것도 단순히 크기가 1인 색종이부터 확인해나가면 모두 1인 칸일 경우에는 엄청난 연산이 필요하게됩니다. 크기 5부터 접근해서 찾고, 이미 찾은 최소 케이스보다 많이 사용하게되면 그 이상은 무의미하니 거기서 중단해주면 시간을 단축시킬 수 있습니다. 나머지는 단순 구현이라 코드를 보시면 어렵지않게 이해가 되실 것 같습니다 :) 해결방법 func solution() { typeali..
-
백준 1038 감소하는 수Algorithm/BOJ 2021. 3. 28. 16:47
출처: www.acmicpc.net/problem/1038 분류: 완전탐색 접근방식 n번째 감소하는 수를 찾는 문제였습니다. 한 자리 수는 모두 감소하는 수이며, 작은 수부터 찾아줘야 합니다. 감소하는 수는 이런 식으로 진행됩니다. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, 41, 42, 43, 50, ... ] 규칙을 생각해보면 마지막 수는 마지막 앞자리 수보다 작아야 하니 앞자리 수가 4라면 마지막에 올 수 있는 수는 0, 1, 2, 3 이 됩니다. 그리고 마지막 자리를 제외한 수도 무조건 감소하는 수가 되어야 합니다. 감소하는 수 54 다음에 540, 541, 542, 543 이 올 수 있지만 44는 감소하는 수가 아니기 때문에 440,..
-
백준 2263 트리의 순회Algorithm/BOJ 2021. 3. 26. 16:19
출처: www.acmicpc.net/problem/2263 분류: 트리 접근방식 트리 순회 방법의 특성을 잘 이용해 해결했어야 하는 문제였습니다. 기억해야 할 특징은 다음과 같습니다. 1. post-order는 왼쪽 - 오른쪽 - 루트 순으로 탐색하므로 배열의 마지막은 루트노드가 됩니다. 2. in-order 는 root를 기준으로 왼쪽은 left, 오른쪽은 right 서브트리로 분리됩니다. post-order를 통해 root 노드를 찾았다면, in-order의 시작부터 root 까지가 왼쪽, 오른쪽으로 분리되고, 이를 통해 왼쪽, 오른쪽에 몇 개의 노드가 존재하는지 알 수 있습니다. 다시 in-order는 왼쪽 - 오른쪽 - 루트가 순서대로 배치되어 있기 때문에 개수를 통해 in-order에서 어디까지..
-
백준 5639 이진 검색 트리Algorithm/BOJ 2021. 3. 26. 14:19
출처: www.acmicpc.net/problem/5639 분류: 트리 접근방식 pre-order 결과가 들어오면 이 트리의 post-order 검색의 결과를 출력하는 문제였습니다. pre-order의 결과를 놓고 보면 첫 번째가 root, root+1 부터 처음으로 root보다 큰 값이 나오는 위치까지가 Left 그 다음이 Right 트리가 됩니다. 우리가 원하는 결과인 post-order는 왼쪽부터 탐색하기 때문에 루트를 타겟으로 이분탐색으로 UpperBounds를 찾아서 왼쪽 -> 오른쪽 -> 루트 를 반복적으로 돌려주면 원하는 결과를 얻을 수 있습니다. 처음엔 입력 받을 때마다 루트부터 위치를 찾아 트리를 만들어 나가는 방식으로 접근했었는데 이렇게 하니까 시간초과가 났습니다. c++로는 이런 식으..
-
백준 1068 트리Algorithm/BOJ 2021. 3. 25. 16:49
출처: www.acmicpc.net/problem/1068 분류: 트리 접근방식 전형적인 트리 문제였습니다. 주어진 대로 부모자식을 쭉 연결한 다음 dfs나 bfs 방식으로 탐색하다가 삭제해야 할 노드를 만나면 건너뛰는 방식으로 하면 해당 요구조건에 맞게 빠르게 해결할 수도 있으나 (많은 분들이 그렇게 푸신 것 같습니다.) 저는 실제 트리에 가깝게 해결해보고 싶어서 실제로 해당 노드와 그 자식 노드들을 제거해주는 방식으로 해결해봤습니다. 처음에는 Node, Tree 클래스를 각각 만들어서 처리해서 풀었다가 별도의 Tree 클래스 없이 루트노드만 가지고 해결하도록 개선해봤는데요, n만큼 임시 배열에 노드를 만들어두고 -1을 만나면 treeNode의 변수로 저장해두고 연결과 제거를 모두 끝내고 나면 임시 배..
-
백준 14503 로봇 청소기Algorithm/BOJ 2021. 3. 19. 14:04
출처: www.acmicpc.net/problem/14503 분류: 시뮬레이션 접근방식 현재 방향을 생각하면서 청소기를 돌려주면 되는 문제였습니다. 저는 현재 로봇 청소기의 위치와 현재 방향을 전역변수로 두고 둘을 조작해주면서 계산했습니다. 방향을 enum 타입으로 정의했고 청소기는 계속 왼쪽 방향으로 회전하기 때문에 각 방향에서 왼쪽으로 회전하는 함수를 만들었습니다. enum Direction: Int { case up = 0, right, down , left mutating func turnLeft() { switch self { case .up: self = .left case .left: self = .down case .down: self = .right case .right: self = ...