포스팅
-
백준 알고리즘 풀이 모음 14590, 2469, 1107 (Feat Python)알고리즘 2023.11.22 15:58
백준 14590번 KUBC League (Small) N명의 정회원들이 리그에 참여하여 N(N-1)/2번의 경기를 진행하고, 1번 선수가 자신이 이긴 사람과 해당 사람이 이긴 사람들의 꼬리를 무는 선수 나열을 통해 얻을 수 있는 최대 길이 L을 출력하는 문제입니다. 문제 조건 2 (1번 선수에게 진 선수에게 진 선수)가 이긴 선수 -> ... 방향으로 탐색하여 최대 길이를 구합니다. DFS를 통해 최대 길이를 구합니다. 2. 최적화 방법 각 선수마다 위처럼 자신에게 진 선수를 나열했을 때의 최대 길이를 가지고 있을 것이고 이는 변하지 않습니다. -> 캐싱을 통해 어떤 선수가 이미 자신에게 진 선수들을 나열해 최대 길이를 가지고 있을 경우 이를 바로 활용하여 더 탐색하지 않고도 최대 길이를 반환할 수 있도..
-
백준 25515번 트리 노드 합의 최대값알고리즘 2023.04.03 10:34
문제 설명 이번 문제는 트리가 주어지고 노드마다 하나의 정수가 적혀있을 때, 루트 노드에서 시작해 이웃한 노드를 방문하여 방문한 노드에 적혀있는 정수 합의 최대값을 출력하는 문제입니다. 문제 풀이 아이디어 각 노드에서 연결된 서브 트리에서의 최대값 찾기 루트 노드로부터 트리의 형태가 주어졌으므로, 루트노드와 연결된 각 서브트리에서 노드의 정수값을 더했을 때의 최대값을 구해줍니다. 한 노드에서 자신의 자식으로부터 얻어진 정수의 최대값을 알면 해당 서브트리에서 정수 합의 최대값을 구할 수 있습니다. 그러므로, 각 노드마다 자식으로부터 얻어진 정수합의 최대값과 자신의 정수값과의 합이 최대가되도록 해줍니다. 풀이 서브트리 정수합의 최대값 구하기 재귀를 이용하여 각 노드의 자식 노드를 탐색합니다. 각 노드가 le..