Algorithm
-
[백준] 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..
-
[백준] 5014번 스타트링크 (by Python)Programming/Algorithm 2021. 2. 7. 18:04
문제 변수가 많았지만, 문제를 제대로 이해하기만 한다면 간단하게 BFS로 해결할 수 있는 문제이다. 개인적으로 각 변수를 필요한 자리에 놓는 과정이 즐거웠던 문제이다. 풀이 from collections import deque INF = int(1e9) f, s, g, u, d = map(int, input().split()) distance = [INF] * (f + 1) distance[s] = 0 q = deque([s]) while True: if not q: print('use the stairs') break temp = q.popleft() if temp == g: print(distance[temp]) break else: if 0 < (temp + u)
-
[백준] 1700번 멀티탭 스케줄링 (by Python)Programming/Algorithm 2021. 2. 7. 17:55
문제 보자마자 운영체제가 생각났던 문제. 실제 운영체제에서는 이렇게 앞으로 어떤 프로세스들이 들어올지 모르기에 최적의 알고리즘을 수행할 수는 없지만, 만약 안다면 이런 식으로 알고리즘을 운영할 수 있다고 배운 것이 어렴풋이 기억이 났다. 앞으로 사용하지 않을 것을 최우선으로 빼고, 가장 나중에 사용할 것은 차선으로 빼는 것. 풀이 from copy import deepcopy n, k = map(int, input().split()) arr = list(map(int, input().split())) now = [] answer = 0 temp = -1 for idx, item in enumerate(arr): if item not in now: if len(now) < n: now.append(item..
-
[백준] 14226번 이모티콘 (by Python)Programming/Algorithm 2021. 2. 7. 00:48
문제 처음에는 떠오르는대로 BFS로 풀었지만 코드를 짜는 와중에도 뭔가 문제를 다 파악하지 못한 풀이라는 생각이 들었고, 아니나 다를까 나보다 시간을 90% 정도 절약한 분들은 Dynamic Programming을 통해 푸신 분들이었다. 간결한 코드에 끌려 원리를 고민해봤지만 수학적인 증명은 스스로 해내지 못했다. 고민해보았고, 앞으로도 더 고민해보겠지만 지금은 더 다양한 테스트 케이스에서 해당 원리가 적용된다는 확신이 없으므로 이런 유형의 문제를 만났을 때는 확실한 풀이를 먼저 시도해볼 것 같다. 좀 느릴지라도, 스스로 납득되는 코드를 짜고 싶다. 첫 번째 풀이 (by BFS) from collections import deque s = int(input()) q = deque() next_q = de..
-
[백준] 1707번 이분 그래프 (by Python)Programming/Algorithm 2021. 2. 6. 00:39
문제 처음에 이분 그래프의 정확한 의미를 모르겠어서 조금 헤맸지만 결국 핵심은 각 노드가 인접한 노드들과 다른 색깔을 가지고 있으면서, 총 2가지 색깔로 다 표현할 수 있는 그래프 라고 생각하면 될 것 같다. 이전의 연결 요소의 개수를 찾는 문제에서 BFS 방법보다 DFS 방법이 더 시간이 낮게 나오는 것을 확인하고 DFS로 들이댔지만 풀고 나니 BFS로 푸는 것이 더 나은 문제였다는 생각이 들어 BFS로도 풀어봤다. 그리고 DFS로 풀려면 sys.setrecursionlimit()을 일단 크게 줘야겠다는 교훈을 얻게 된 문제! 첫 번째 풀이 (by DFS) import sys input = sys.stdin.readline sys.setrecursionlimit(100000) k = int(input(..