백준
-
백준 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 ..
-
백준 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 ..