728x90 트리14 [python] 백준 14426 접두사 찾기 https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 문제 해결 하나씩 비교를 하면 시간복잡도가 매우 크다. 따라서 정렬을 한 후에 사전식 배열 비교를 한다. S에 포함되어있는 문자열과 검사해야하는 문자열을 비교해서 포함하면 정답+1과 다음 검사해야하는 문자열을 비교를 한다. 만약 포함여부에 해당하지 않고 S에 포함되어있는 문자열의 사전식 배열이 더 뒤이면 검사해야.. 2024. 3. 10. [python] 백준 3584 가장 가까운 공통 조상 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 해결 LCA (Low Common Ancestor)알고리즘 최소 공통 조상을 찾는 알고리즘은 트리문제에서 자주나오는 문제이다. 무조건 공통 조상은 있으므로 각 노드에서 루트로 올라가는 길을 정리하여 루트부터 다시 내려가면서 서로 갈라지는 지점을 찾으면 된다. 갈라지기 전에 가장 가까운 공통 조상이다! CODE import sys input .. 2023. 11. 13. [python] 백준 2533 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 문제 해결 트리를 이용해야하는데 어떻게 이용해야할지 고민을 많이 했다. 부모-자식 중에서 적어도 한 명은 얼리 어답터여야한다. 따라서 dp를 이용해서 부모가 얼리 어답터일 때(dp[parent][1])일 때와 부모가 얼리 어답터가 아닐 때 (dp[parent][0])를 구분을 해서 알고리즘을 풀어나가면 되겠다라는 생각을 한다. dp[i][j]는 i번째 노드가 j상태일때 i번째 밑에 있는 노드.. 2023. 9. 27. [python] 백준 14267 회사 문화 1 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제 해결 노드 하나를 잡고 그것을 루트(root)로 하는 서브트리의 모든 노드에 일정한 점수를 더하는 문제 점수를 더해줄 때 DFS를 쓰면 편하다는 것은 너무 쉽게 알 수 있다. 하지만 노드 하나씩 잡고 서브트리의 모든 노드에 일정한 점수를 더하는 것은 시간복잡도면에서 비효율적이며 시간초과가 나게 되었다. 루트로 잡을 노드에 모두 점수를 주입시키고 1번이 사장이라는 것(트리의 루트)라는 것을 .. 2023. 9. 26. 이전 1 2 3 4 다음 728x90
