CodingNoye 블로그
취소

DMLab 알고리즘 스터디 4주차

개요 4주차 스터디는 자료구조 관련 6문제였다. A번 1417 문제 요약 N명의 후보들의 득표수들이 주어지고, 1번 후보가 당선되게 하기 위해서 유권자를 몇명이나 매수해야 하는지를 구하는 문제 설명 Max PQ에 1번을 제외한 후보의 득표수를 넣고, 가장 큰 득표수가 1번의 득표수보다 작아질 때까지, 1표를 옮기고 PQ에 집어넣기를 반복하면...

LCA (Lowest Common Ancestor) 알고리즘

소개 LCA란 트리에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘이다. 그렇다면 LCA가 필요한 이유는 무엇일까? 바로 설명하자면 트리에서 최단 경로를 LCA로 구하기 때문이다. 트리에서 두 노드 u, v의 최단 경로는 u->LCA + LCA->v 이다. (조금 생각해보면 트리의 성질에 의해 당연하다는 것을 알 수 있다.) 예시...