백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 1520번: 내리막 길 (Python)

접근 DFS와 DP를 동시에 이용하면 쉽게 풀 수 있는 문제였다. visited라고 이름붙인 함수를 -1로 초기화하고, 이동 시 0으로 다시 설정해준다. 과정을 진행하면서 visited에 저장된 값이 0이면 목적지에 도달하지 못하므로 0을 return 해준다. 1 이상의 값이면 이전에 그만큼 방문 경로가 있으므로 해당 값을 반환해서 더해준다. -1 이면 방문하지 않은 경로이므로 dfs 수행 코드 import sys sys.setrecursionlimit(10**6) n, m = map(int, sys.stdin.readline().split()) height = [] for _ in range(n): height.append(list(map(int, sys.stdin.readline().split()))..

2021. 4. 8. 00:13
코딩/백준 (Python)

백준 11049번: 행렬 곱셈 순서 (Python, PyPy3)

접근 이전에 풀었던 DP 문제와 유사하게 풀었다. 하지만 Knuth's Optimization은 적용하지 못해 PyPy3으로만 풀 수 있었다. 2021.04.07 - [코딩/백준 (Python)] - 백준 11066번: 파일 합치기 (Python, PyPy3) 백준 11066번: 파일 합치기 (Python, PyPy3) 접근 굉장히 어려운 dp문제였다. 풀이 방법을 생각해내는데에도 많은 시간을 썼고, 최적화를 위해 추가적인 방법을 찾는 과정에서 다른 문제 풀이를 보고 이해하는데도 시간이 많이 걸렸다. 결 ca.ramel.be dp[i][j]에 i번째부터 j번째까지의 행렬을 곱한 최소 결과를 저장하면 dp[0][n]의 값(첫 행렬부터 마지막까지 행렬까지 곱한 결과의 최소값)은 dp[0][0] + dp[1]..

2021. 4. 7. 22:53
코딩/백준 (Python)

백준 11066번: 파일 합치기 (Python, PyPy3)

접근 굉장히 어려운 dp문제였다. 풀이 방법을 생각해내는데에도 많은 시간을 썼고, 최적화를 위해 추가적인 방법을 찾는 과정에서 다른 문제 풀이를 보고 이해하는데도 시간이 많이 걸렸다. 결론적으로 말하자면 dp[i][j]에 i번째부터 j번째 챕터를 합치는 최소 비용을 저장하게 된다. 그렇다면 dp[0][n]의 값(0번 챕터부터 n번 챕터까지 합치는 최소 비용)은 dp[0][0] + dp[1][m] dp[0][1] + dp[2][m] ... dp[0][n - 2] + dp[n - 1][m] dp[0][n - 1] + dp[n][m] 값 중 하나일 것이다. 이러한 방법으로 코드1의 식을 얻었지만 Python으로는 시간 초과, PyPy3으로 풀었을 때 간신히 시간안에 들어올 수 있었다. 아무래도 3중 for문을..

2021. 4. 7. 01:06
코딩/백준 (Python)

백준 1655번: 가운데를 말해요 (Python)

접근 기존의 힙 트리 알고리즘을 이용하여 푸는 문제였다. 최대 힙과 최소 힙 두가지 모두 써야하기 때문에 기존에 작성했던 최대 힙, 최소 힙 함수를 사용하지 않고 heapq 라이브러리를 불러와서 문제를 해결해보았다. 최대 힙 문제 2021.04.05 - [코딩/백준 (Python)] - 백준 11279번: 최대 힙 (Python) 백준 11279번: 최대 힙 (Python) 접근 힙 트리(heap tree)란 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리이다. 힙에는 가장 큰 값을 구하기 위한 최대 힙과, 가장 작은 값을 구하기 위한 최소 힙이 ca.ramel.be 최소 힙 문제 2021.04.05 - [코딩/백준 (Python)] - 백준 1927번: 최소 힙 (Pyth..

2021. 4. 6. 00:29
코딩/백준 (Python)

백준 11286번: 절댓값 힙 (Python)

접근 절댓값이 작은 기준이므로 이전 문제인 최소 힙에 추가적으로 절댓값이 같을 경우 실제 값이 더 작은 쪽이 힙 트리 상에서 더 위에 위치할 수 있는 조건을 추가해주면 된다. 2021.04.05 - [코딩/백준 (Python)] - 백준 1927번: 최소 힙 (Python) 백준 1927번: 최소 힙 (Python) 접근 이전 문제인 최대 힙과 동일한 문제였다. 이전 글에 힙에 대한 설명 참고하면 되겠다. 2021.04.05 - [코딩/백준 (Python)] - 백준 11279번: 최대 힙 (Python) 백준 11279번: 최대 힙 (Python) 접근 힙 트리(.. ca.ramel.be 코드 import sys def heapappend(heap, num): heap.append(num) i = le..

2021. 4. 5. 23:36
코딩/백준 (Python)

백준 1927번: 최소 힙 (Python)

접근 이전 문제인 최대 힙과 동일한 문제였다. 이전 글에 힙에 대한 설명 참고하면 되겠다. 2021.04.05 - [코딩/백준 (Python)] - 백준 11279번: 최대 힙 (Python) 백준 11279번: 최대 힙 (Python) 접근 힙 트리(heap tree)란 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리이다. 힙에는 가장 큰 값을 구하기 위한 최대 힙과, 가장 작은 값을 구하기 위한 최소 힙이 ca.ramel.be 코드 import sys def heapappend(heap, num): heap.append(num) i = len(heap) - 1 while i > 1: if heap[i] < heap[i // 2]: tmp = heap[i] heap[i] ..

2021. 4. 5. 23:16
반응형