Programming/Algorithm
-
[백준] 1699번 제곱수의 합 (by Python)Programming/Algorithm 2021. 2. 28. 17:19
문제 비슷한 문제인 1, 2, 3 더하기가 있지만 이 문제는 1, 2, 3이 아니라 n과 같거나 작은 모든 제곱수를 다 고려해야한다는 점에서 시간복잡도가 더 높은 문제이다. 그래서 Pypy3 환경에서만 성공할 수 있었다는 아쉬움이 있지만 이 문제에서 요구한 사고력은 내 풀이로도 충분하다고 생각해 더 이상의 최적화를 시도하진 않았다. 풀이 from math import sqrt n = int(input()) sq_num = [i ** 2 for i in range(1, int(sqrt(n) + 1))] dp = [1 if i in sq_num else i for i in range(n + 1)] for i in range(2, n + 1): for j in range(1, int(sqrt(i)) + 1):..
-
[백준] 14002번 가장 긴 증가하는 부분 수열 4 (by Python)Programming/Algorithm 2021. 2. 21. 21:52
문제 이 문제의 원형인 11053번에서 꽤나 애를 먹어서 어떻게 꼬아놨을까 조금 긴장했지만 생각외로 쉽게 풀렸던 문제. 경로를 기억해두는 장치만 해두면 되는 문제였다. 풀이 n = int(input()) arr = list(map(int, input().split())) dp = [[1, i] for i in range(n)] for i in range(n): for j in range(i): if arr[i] > arr[j] and dp[i][0] < (dp[j][0] + 1): dp[i] = [dp[j][0] + 1, j] temp = dp.index(max(dp)) route = [temp] while dp[temp][1] != temp: route.insert(0, dp[temp][1]) temp..
-
[백준] 11053번 가장 긴 증가하는 부분 수열 (by Python)Programming/Algorithm 2021. 2. 21. 21:22
문제 내가 생각했던 것은 bottom-up 방식으로 for loop으로 0번째부터 i번째까지의 LIS(Longest Increasing Subsequence) 값을 저장해둔다는 것. 그렇지만 점화식을 세우는 것이 쉽지 않았는데, 이전 원소들의 정보를 충분히 활용할 수 없었기 때문이었다. 그래서 이코테 책을 보다가 알게 된 점화식은 내 기존 생각에 한 가지를 덧붙인 것이었는데, i번째 원소를 사용한다는 제약조건을 추가하는 것이다. 그렇게 마지막 원소까지 반복문을 수행한 후 max값을 찾으면 LIS의 길이를 구할 수 있다. 점화식을 생각할 때 정보가 충분하지 않은 것 같다면 정답으로 이어질 수 있으면서 고려할 범위를 좁혀줄 수 있는 제약조건을 주라는 것이 내가 이 문제에서 얻은 팁이다. 풀이 n = int(..
-
[백준] 1932번 정수 삼각형 (by Python)Programming/Algorithm 2021. 2. 21. 18:32
문제 점화식을 찾는 것은 사실 무척 쉬웠지만 인덱스를 헷갈려 시간을 낭비했다. 언제나 느끼지만 문제를 잘 푸는 것은 논리력뿐만 아니라 실수를 하지 않는 것도 포함되는 것 같다. 풀이 import sys input = sys.stdin.readline n = int(input()) arr = [] dp = [[0] * (i + 1) for i in range(n)] for _ in range(n): arr.append(list(map(int, input().strip().split()))) dp[0][0] = arr[0][0] for i in range(1, n): for j in range(i + 1): if j == 0: dp[i][j] = dp[i - 1][0] + arr[i][j] elif j ==..
-
[백준] 2156번 포도주 시식 (by Python)Programming/Algorithm 2021. 2. 16. 13:41
문제 짜고 보니 몇 줄 안됐지만 하루종일 머리 싸매다가 다른 분의 해설을 보고 나서야 해답을 찾은 문제. 풀이 import sys input = sys.stdin.readline n = int(input()) arr = [] ans = [0 for _ in range(n)] for _ in range(n): arr.append(int(input())) ans[0] = arr[0] if n > 1: ans[1] = arr[0] + arr[1] if n > 2: ans[2] = max(arr[0] + arr[1], arr[1] + arr[2], arr[0] + arr[2]) for i in range(3, n): ans[i] = max(ans[i - 1], ans[i - 2] + arr[i], ans[i -..
-
[백준] 9465번 스티커 (by Python)Programming/Algorithm 2021. 2. 14. 23:16
문제 제법 Dynamic Programming에 익숙해졌다고 생각했는데 점화식을 떠올리기가 힘들었던 문제. 메모이제이션 방법을 떠올렸지만 점화식의 형태를 구상하기가 힘들었다. 수열로 따졌을 때 새로 추가되는 column의 값들에 따라서 최댓값도 달라지기 때문에 그랬던 것 같다. 이 문제의 breakthrough는 크게 다음 2가지였던 것 같다. ① 새로운 값이 어떤 값이냐에 따라서 답이 달라진다면 다 대입해볼 것! ② 메모이제이션으로 해당 값까지의 최적 경로에 대한 축적을 한다는 것을 기억하고 무엇을 축적해야할지 생각할 것! 풀이 t = int(input()) for _ in range(t): n = int(input()) arr = [] ans = [[0] * n for _ in range(2)] fo..
-
[백준] 3055번 탈출 (by Python)Programming/Algorithm 2021. 2. 11. 02:12
문제 BFS 문제에서 길을 찾아가는 주체뿐만 아니라 갈 수 없는 길까지 큐를 이용해서 업데이트해주어야 하는 문제. 생각이 부족한 탓에 시간 초과 + 디버깅의 헬파티로 힘든 시간을 보냈다... 시간 초과로 문제를 원망하고 파이썬을 원망했지만 프로그래머로서 올바른 자세는 내 머리를 원망해보자는 생각.... 풀이 from collections import deque import sys input = sys.stdin.readline r, c = map(int, input().split()) forest = [list(input().strip()) for _ in range(r)] steps = [(1, 0), (0, 1), (-1, 0), (0, -1)] answer = 0 flag = True q = deq..
-
[백준] 13549번 숨바꼭질 3 (by Python)Programming/Algorithm 2021. 2. 10. 20:16
문제 2*X로 순간이동할 때만 0초가 걸린다는 점이 골머리를 앓게 만드는 문제. 그리고 시간을 더 줄이려면 앞으로 가는 수단은 +1과 *2 2가지가 있지만 뒤로 가는 수단은 -1 하나밖에 없다는 점을 이용해야 한다. 풀이 from collections import deque n, k = map(int, input().split()) if n >= k: print(n - k) else: q = deque([n]) visited = [False] * 100001 next_q = deque() answer = 0 flag = True while flag: if not q: q = next_q next_q = deque() answer += 1 temp = q.popleft() visited[temp] = Tr..