Swift
-
백준 2250 트리의 높이와 너비Algorithm/BOJ 2021. 6. 4. 14:26
출처: https://www.acmicpc.net/problem/2250 분류: 트리, 중위순회 접근방식 너비가 가장 큰 높이를 구해야하는 문제였습니다. 문제의 그림이 힌트를 주고 있는데요, 가장 왼쪽 노드부터 x가 하나씩 증가하고 있습니다. 중위 순회를 하면 "왼쪽 -> 루트 -> 오른쪽" 순서로 방문하기 때문에 이 순서가 곧 x가 1인 노드부터 차례대로 방문하는 순서입니다. 이 부분까지 이해가 됐다면 구현만 해주면 되는데요! 저는 그냥 중위순회에서 다 처리해버렸습니다. 전역적으로 사용하는 x값을 가지고 다니면서 노드에 넣었으면 1 증가시키는 방식으로 x를 처리했구요 해당 레벨의 최대, 최소 x값을 넣는 배열을 전역적으로 만들어 놓고 최대 최소를 업데이트 시켜줬습니다. func markWhileInOr..
-
백준 1094 막대기 (비트 개수 세기)Algorithm/BOJ 2021. 6. 3. 15:31
출처: https://www.acmicpc.net/problem/1094 분류: 비트마스킹 접근방식 주어진 문제의 조건을 맹목적으로 따라서 풀 수도 있지만, 조건을 해보면 결국은 주어진 x를 몇 개의 2의 배수를 사용해 만들 수 있느냐 하는 문제입니다. 다시 생각해보면 "x를 이진수로 만들었을 때 1이 몇 개냐" 라는 말과 같은 말이라는 걸 알 수 있습니다 :) 따라서 이진수에서 1이 몇 개인지 세는 방법을 알아보겠습니다. 2로 나누기 우선 비트 연산을 하지 않는다면 주어진 수를 x로 나눠가면서 셀 수가 있겠네요. 중학생(?)때 배우는 10진수를 2진수로 바꿀 때 나눠가면서 나머지를 세는 바로 그 방식입니다. while x > 0 { bitCount += x % 2 x /= 2 } >> 1 2로 나누는 ..
-
백준 2056 작업Algorithm/BOJ 2021. 6. 3. 13:32
출처: https://www.acmicpc.net/problem/2056 분류: 위상정렬 접근방식 나보다 먼저 수행되어야 할 작업이 필요한 위상정렬에 관한 문제였습니다 :) 각 작업을 Node로 정의해서 나보다 먼저 수행되어야 할 작업들을 진입차수, inDegree 내가 끝나길 기다리고 있는 작업들을 nextTasks로 가지고 있도록 만들었습니다. 내가 수행하는 데 걸리는 시간을 workingTime 그리고 자신이 끝나는 시간 endTime을 가지고 있도록 했습니다. (우선 초기값은 workingTime이고 내가 기다리던 작업이 끝날 때마다 업데이트 시킵니다.) inDegree가 0인 작업들은 바로 시작이 가능하므로 큐에 담아서 실행시키고, 작업이 끝나면 기다리던 노드로 가서 inDegree를 줄이고 n..
-
백준 2169 로봇 조종하기Algorithm/BOJ 2021. 6. 2. 15:30
출처: https://www.acmicpc.net/problem/2169 분류: DP 접근방식 백트래킹 문제 같이 보이지만, n, m이 최대 1000이기 때문에 백트래킹으로 접근하면 시간초과가 납니다. 백트래킹에 복잡도를 생각해봤는데, 한 번 이동마다 최대 3가지 경로로 가지가 쳐지고 위로 이동은 없으니 거꾸로 경우를 줄여 2가지로 잡아도 2^1000 하면 시간초과를 면치 못한다고 생각이 드는데요, 제대로 판단한건지는 잘 모르겠네요... 정확히 아시는 분은 답글 부탁드립니다 🙇🏻♂️ 이 문제는 DP로 접근해서 해결할 수 있는데요, 위로 이동하는 경우는 없으니 맨 윗줄은 1, 1지점부터 오른쪽으로 이동하는 경우가 최선의 경우입니다. for col in 1..
-
백준 7579 앱Algorithm/BOJ 2021. 6. 2. 13:37
출처: https://www.acmicpc.net/problem/7579 분류: DP 접근방식 어떤 걸 기준으로 DP를 만들건지 어려웠던 문제였습니다... 결국 다른 블로그의 풀이를 참고하여 해결했습니다. 비용으로 확보할 수 있는 최대 메모리를 만들어가는 방식으로 해결했습니다. 점화식은 아래와 같습니다. DP[cost] = max( DP[cost] , DP[cost - inActiveCost[app] + activeMemory[app] ) 여기서 DP[cost]는 cost를 사용하여 확보할 수 있는 최대 메모리인데요, DP[ cost - inActiveCost[app] ] 은 app을 아직 제거하기 전의 비용으로 확보할 수 있는 최대 메모리로 여기에 지금 앱을 제거해서 얻을 수 있는 비용을 더해주면 이게..
-
백준 5557 1학년Algorithm/BOJ 2021. 6. 2. 11:01
출처: https://www.acmicpc.net/problem/5557 분류: DP 접근방식 만들 수 있는 가능한 연산의 경우의 수를 구하는 문제였습니다! 중간 중에 나올 수 있는 수는 0 ~ 20 밖에 없기 때문에 0~20까지 배열을 만들어두고 개수를 카운트 해주는 방식으로 해결했습니다. 이전 연산의 개수에 계산한 결과가 그대로 다음 연산으로 넘어가는데, 이때 이전 결과는 남아있으면 안되기 때문에 배열을 2개 두고 돌려가며 사용했습니다. 말이 조금 어려운데.. 가령 어떻게 어떻게 해서 중간에 연산 결과가 8이 된 경우가 3개 있다고 생각하고 다음의 숫자는 3이라고 생각해보겠습니다. 그러면 +, - 연산을 사용해 8과 3으로 만들 수 있는 결과는 8 + 3 = 11 8 - 3 = 5 이렇게 두 가지가 ..
-
백준 1013 ContactAlgorithm/BOJ 2021. 5. 23. 18:56
출처: https://www.acmicpc.net/problem/1013 분류: 문자열, 오토마타, 정규식 접근방식 처음에 일일이 경우의 수를 따라가면서 해주려고 했는데 너무 복잡해서 다른 분들은 어떻게 똑똑하게 푸셨는지 열심히 참고했습니다... 결국 각 단계를 State로 하는 오토마타를 그려서 해결했습니다! 6번 다음에 1로 보내야 할지 6에서 반복을 돌려야 할지 문제였는데 7이라는 새로운 state로 넘겨서 새로운 분기를 만들어주는 방식이 있네요!! 2번에서 0이 나왔을 때 1로 넘겨주는 것도 주의해야 합니다 :) 참고 https://maivve.tistory.com/208 해결방법 let n = Int(readLine()!)! func isValidPattern(_ pattern: String) ..
-
백준 13397 구간 나누기 2Algorithm/BOJ 2021. 5. 21. 08:10
출처: https://www.acmicpc.net/problem/13397 분류: 이분탐색 접근방식 이분탐색으로 m개 이하의 구간으로 나눠서 만들 수 있는지 확인하면서 최소값을 갱신해나가는 방법으로 해결할 수 있었습니다. 배열의 값이 1...10000 값이기 때문에 음수는 나올 수 없으니 right를 배열의 합, left를 0으로 두고 이분탐색을 돌렸습니다. var left = 0, right = numbers.reduce(0, +) var minSegmentMax = right while left Bool { var low = numbers[0], high = numbers[0] var count = 1 for num in numbers { if num < low { low = num } if num ..