본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[python] 백준 14267 회사 문화 1 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제 해결 노드 하나를 잡고 그것을 루트(root)로 하는 서브트리의 모든 노드에 일정한 점수를 더하는 문제 점수를 더해줄 때 DFS를 쓰면 편하다는 것은 너무 쉽게 알 수 있다. 하지만 노드 하나씩 잡고 서브트리의 모든 노드에 일정한 점수를 더하는 것은 시간복잡도면에서 비효율적이며 시간초과가 나게 되었다. 루트로 잡을 노드에 모두 점수를 주입시키고 1번이 사장이라는 것(트리의 루트)라는 것을 .. 2023. 9. 26.
[python] 백준 20955 민서의 응급 수술 https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 문제 해결 먼저 분리되어 있는 그룹이 몇개인지 알아야 한다. 그것을 유니온-파인드를 통해 알 수 있다. 만약 시냅스로 연결된 두 뉴런의 번호 u,v를 받았을 때 이미 같은 그룹에 있으면 더 연결 될 필요가 없으므로 잘라내는데에 연산을 한 번 쓰게 된다. 만약 다른 그룹이면 유니온-파인드를 통해 서로 연결 시킨다. 그룹이 다른 개수 + 이미 연결되어 연결 될 필요가 없는 개수를 합친다음 하나의 중.. 2023. 9. 25.
[python] 백준 22856 트리 순회 https://www.acmicpc.net/problem/22856 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 문제 해결 트리의 간선 지나간 횟수를 셀 수 있는가 문제 전체 이동하고 왕복했을 때 지나간 간선 개수 - 오른쪽으로만 이동했을 때 끝까지 간 편도 간선 개수 DFS를 이용해 간선의 개수를 세는 것이 편하다. 자식 노드는 최대 두 개이다. (1개 일 때는 오른쪽 노드를 -1로 정의) CODE import sys input = sys.stdin.readline sys.setrecursionlimit.. 2023. 9. 24.
[python] 백준 7795 먹을 것인가 먹힐 것인가 https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제 해결 모든 원소를 1대1로 비교해서 계산하는 것은 너무 비효율적이라는 생각이 든다. 정렬을 이용해서 A와 B를 오름차순으로 정렬하고, $i \in {0,1,2,3, . . .n-1} $ $j \in {0,1,2,3, .. m-1}$ 인 임의의 $i, j$에 대해서 A[i] > B[j]이면 A[i+1] > B[j]임을 생각을 하면 좋다. 만약.. 2023. 9. 14.
728x90