개요 6주차 스터디는 정렬 관련 6문제였다. A번 9237 문제 요약 묘목을 심는데 1일, 자라는데 T_i일이 걸린다. 묘목을 모두 심어서 다 자라게 하는 최소 일수 구하기 설명 정렬해서 오래 걸리는 것부터 심으면 된다. B번 18310 문제 요약 일직선 위에 집들의 위치가 주어질 때, 안테나를 설치해 집들과의 거리의 총합을 최소화하려...
DMLab 알고리즘 스터디 5주차
개요 5주차 스터디는 누적합 관련 6문제였다. A번 13900 문제 요약 N개의 정수 중, 모든 서로 다른 위치의 수의 곱들의 합을 구하는 문제 설명 모든 수들의 합을 미리 구해 놓고, (모든 수의 합 - A[i]) * A[i]를 모든 i에 대해 해주면 된다. B번 14465 문제 요약 직선 위에 신호등이 1간격으로 쭉 있었는데, 그 ...
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 이다. (조금 생각해보면 트리의 성질에 의해 당연하다는 것을 알 수 있다.) 예시...