전체 글
-
백준 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 ..
-
백준 14891 톱니바퀴Algorithm/BOJ 2021. 5. 13. 00:37
출처: www.acmicpc.net/problem/14891 분류: 시뮬레이션 접근방식 주어진 규칙에 따라 톱니바퀴를 회전시킨 후 결과를 계산하는 문제였습니다. 톱니바퀴를 회전시킨다는 건 톱니바퀴를 바라보는 관점만 바꿔주면 됩니다. 즉 가리키는 인덱스만 바꿔주면 회전과 같은 효과를 얻을 수 있겠죠. 시계방향으로 톱니바퀴의 극이 주어지는데 12시 방향을 0으로 생각하면, 양쪽에 맞물려서 확인해야 하는 지점은, 톱니의 왼쪽은 6, 오른쪽은 2가 됩니다. 따라서 시계방향으로 회전시키려면 톱니의 왼쪽 오른쪽을 -1 해주면되고 반시계방향으로 회전시키려면 톱니의 왼쪽 오른쪽을 +1 해주면 됩니다. 회전이니까 나머지 연산을 잘 사용해주면 손쉽게 구현해줄 수 있습니다. if dir == 1 { // 반시계 pole[s..
-
백준 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) ..