algorithm
-
백준 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 = ...
-
백준 17135 캐슬디펜스Algorithm/BOJ 2021. 3. 18. 14:14
출처: www.acmicpc.net/problem/17135 분류: 시뮬레이션 접근방식 구현도 구현인데 생각을 좀 잘못해서 몇 번의 시행착오를 겪었습니다. 문제를 잘 읽지 않으면 틀릴 수 있는 주의해야 할 점들이 몇 가지 있었던 문제 같습니다. 저는 문제를 보고 크게 3가지의 구현 단계로 나눠야겠다고 생각했습니다. 1. 궁수 3명 뽑기 2. 현 위치에서 제거 가능한 적 찾기 3. 궁수 전진 각 부분이 잘 구현되면 흐름에 따라 답을 찾는 건 어렵지 않게 할 수 있습니다. 저는 우선 주어진 맵 밑에 궁수가 배치될 행 (n행) 을 하나 추가했는데요, 여기에 궁수를 두고 나머지 적을 모두 밑으로 내리는 건 에너지 소모가 굉장히 큰 일이라서, 저는 여기서부터 출발해 궁수가 한 칸씩 위로 올라가면서 적을 죽이는 방..
-
백준 17142 연구소 3Algorithm/BOJ 2021. 3. 17. 16:09
출처: www.acmicpc.net/problem/17142 분류: 완전탐색, BFS, DFS 접근방식 조합과 BFS를 사용해 해결할 수는 문제였습니다. 바이러스가 활성화될 수 있는 지역과 최대 활성화시킬 수 있는 바이러스의 수가 주어졌을 때, 활성화 바이러스의 조합을 뽑아 BFS를 돌려 최단 거리를 계산합니다. 활성화 바이러스의 조합은 순서 상관없이 뽑는 경우의 수이기 때문에 순열이 아닌 조합으로 처리해줘야 합니다! var selected = [Point]() func selectVirus(curr: Int) { if selected.count == nm[1] { let time = infectTime(selected) if time != -1 { if minimumTime == -1 { minimum..
-
백준 10819 차이를 최대로Algorithm/BOJ 2021. 3. 16. 13:20
출처: www.acmicpc.net/problem/10819 분류: 완전탐색, 순열 접근방식 n이 최대 8밖에 되지 않아 가능한 배열 조합을 모두 구해서 주어진 식대로 계수의 최댓값을 계산했습니다. 주어진 예제에서는 [8, 15, 1, 20, 4, 10] 경우에 가장 큰 최댓값이 나오는데 어떤 경우에 최대가 나오는 특별한 규칙이 있는건지는 잘 모르겠습니다.. ㅠㅠ 순열을 오랜만에 해서 처음에는 배열을 만들어가고 해당 수를 넣었는지 체크하는 bool 배열을 만들고... 굉장히 비효율적으로 풀었었네요 ㅠㅠ 덕분에 오랜만에 순열을 다시 복습해볼 수 있어서 좋았네요 :) 전통적인 순열은 스왑을 통해 백트래킹 방식으로 구할 수 있습니다. 앞에서부터 해당 자리에 들어갈 수를 채워넣어가는 방식으로 바꿀 자리의 인덱스..
-
백준 16236 아기상어Algorithm/BOJ 2021. 3. 10. 18:08
출처: www.acmicpc.net/problem/16236 분류: BFS 접근방식 상어가 먹이를 찾을 수 없을 때가지 최단거리의 먹이를 찾아 bfs를 돌려주면 되는 문제였습니다. 기술적으로 크게 어려운 것은 없었으나... 익숙하지 않다면 구현에서 좀 애를 먹을 수 있을 것 같네요..! (후 힘들었습니다..) 같은 거리의 먹이들이 여러 개라면 요구사항대로 정렬을 해줘야 합니다! row 우선, 그다음 col로 ..! feeds.sorted(by: { $0.r == $1.r ? $0.c < $1.c : $0.r < $1.r}) 큐에서 DoubleStackQueue를 사용했는데 그냥 배열로 해서 removeFirst해도 통과가 가능한 것 같습니다. 해결방법 struct DoubleStackQueue { pri..