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

백준 11438번: LCA 2 (Python, PyPy3)

접근 이번 문제는 최소공통조상을 구하는데 Sparse Table(희소 테이블)을 이용하는 문제였다. LCA 알고리즘 개념: 2021.06.27 - [코딩/백준 (Python)] - 백준 3584번: 가장 가까운 공통 조상 (Python) 백준 3584번: 가장 가까운 공통 조상 (Python) 접근 문제에 있는 설명과 같이 가장 가까운 공통 조상 (LCA, lowest common ancestor) 알고리즘을 이용하여 풀 수 있다. 주어진 트리들을 이용하여 부모를 구할 수 있도록 저장해준 후, 마지막으로 비교 ca.ramel.be 희소 테이블 기본 문제: 2021.06.27 - [코딩/백준 (Python)] - 백준 17435번: 합성함수와 쿼리 (Python) 백준 17435번: 합성함수와 쿼리 (Py..

2021. 6. 29. 23:39
코딩/백준 (Python)

백준 17435번: 합성함수와 쿼리 (Python)

접근 sparse table 을 이용하는 문제이다. sparse table 은 모든 계산값을 저장하는 것이 아니라 배로 늘어나는 연산의 값을 저장해줌으로써 문제가 주어졌을 때 그 계산을 편리하게 해줄 수 있는 표를 만드는 것이다. 문제의 예시에서 f(1) = 3 의 값을 가지고 f2(1) = f(f(1)) = f(3) = 5 의 값을 가지게 된다. f4(1) 의 경우, f2(f2(1)) 와 같이 이전 단계에 구했던 f2 의 값들을 이용하여 빠르게 구할 수 있고, 이와 같이 2의 제곱으로 늘어나는 값들을 저장해주게 된다. 이 표를 이용하여 쿼리에 주어진 fn(x) 의 값을 빠르게 구할 수 있다. 코드 import sys m = int(sys.stdin.readline()) f = [0] + list(map..

2021. 6. 27. 17:07
코딩/백준 (Python)

백준 3584번: 가장 가까운 공통 조상 (Python)

접근 문제에 있는 설명과 같이 가장 가까운 공통 조상 (LCA, lowest common ancestor) 알고리즘을 이용하여 풀 수 있다. 주어진 트리들을 이용하여 부모를 구할 수 있도록 저장해준 후, 마지막으로 비교해야 하는 a 와 b 에 대하여 그 부모들을 모두 리스트로 순서대로 저장한다. 두 리스트 모두 마지막 요소를 루트 노드로 가지고 있을 것이다. 그러면 루트 노드부터 시작하여 아래로 내려오면서 비교하여 같지 않은 노드가 나올 때까지 탐색하면, 바로 직전 노드가 가장 가까운 공통 조상이게 된다. LCA 알고리즘 개념 및 설명: LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor) ..

2021. 6. 27. 16:37
코딩/백준 (Python)

백준 1766번: 문제집 (Python)

접근 문제집을 풀 때 먼저 풀어야 하는 문제가 있다는 점에서 위상 정렬 알고리즘을 이용하고, 풀 수 있는 문제 중에서 가장 난이도가 쉬운 문제, 즉 가장 숫자가 작은 문제 먼저 푼다는 점을 추가적으로 고려해주면 풀 수 있다. 위상 정렬 알고리즘은 단계별 문제를 풀면서 앞선 문제들을 풀면서 익숙해질 수 있었다. 위상 정렬 기본 문제: 2021.06.20 - [코딩/백준 (Python)] - 백준 2252번: 줄 세우기 (Python) 백준 2252번: 줄 세우기 (Python) 접근 위상 정렬에 대한 공부를 하고 나서 풀었다. 위상 정렬은 사이클이 없고, 방향만 존재하는 그래프에서 정점들을 나열하는 방법이다. 학생들의 순서를 앞 학생에서 뒤 학생으로 연결된 한개 ca.ramel.be 추가적인 고려를 해주지..

2021. 6. 24. 22:55
코딩/백준 (Python)

백준 1005번: ACM Craft (Python)

접근 위상정렬에 DP를 더한 문제였는데 둘다 기본적인 수준으로만 섞여있어서 간단한 문제였다. 위상 정렬 기본 문제: 2021.06.20 - [코딩/백준 (Python)] - 백준 2252번: 줄 세우기 (Python) 백준 2252번: 줄 세우기 (Python) 접근 위상 정렬에 대한 공부를 하고 나서 풀었다. 위상 정렬은 사이클이 없고, 방향만 존재하는 그래프에서 정점들을 나열하는 방법이다. 학생들의 순서를 앞 학생에서 뒤 학생으로 연결된 한개 ca.ramel.be 기본적인 위상 정렬 알고리즘에 DP를 새로 작성해주되, DP[i] 는 i 를 완성하기까지 필요한 시간을 갱신하면서 저장해주면 된다. 코드 import sys from collections import deque t = int(sys.stdi..

2021. 6. 23. 22:23
코딩/백준 (Python)

백준 3665번: 최종 순위 (Python)

접근 위상 정렬 문제였고, 처음에 많이 헤메었지만 바뀐 순위들만 생각하는 것이 아니라 처음에 주어진 순위를 모두 어떤 처리를 해서 같이 계산해주어야 된다고 생각의 방향을 바꾸고 나서는 쉽게 해결이 되었다. 위상 정렬 기본 문제: 2021.06.20 - [코딩/백준 (Python)] - 백준 2252번: 줄 세우기 (Python) 백준 2252번: 줄 세우기 (Python) 접근 위상 정렬에 대한 공부를 하고 나서 풀었다. 위상 정렬은 사이클이 없고, 방향만 존재하는 그래프에서 정점들을 나열하는 방법이다. 학생들의 순서를 앞 학생에서 뒤 학생으로 연결된 한개 ca.ramel.be 1 2 3 4 5 다섯개의 팀이 각각 1 2 3 4 5 의 순위를 가지고 있을 때, 1 -> 2 2 -> 3 3 -> 4 4 -..

2021. 6. 22. 22:58
반응형