geminanolja 님의 블로그

https://www.acmicpc.net/problem/2470   주어진 용액들 중 두 개의 용액을 혼합했을 때, 혼합 용액의 특성값이 0에 가장 가까운 경우를 찾고, 해당 두 용액의 특성값을 출력하는 프로그램을 작성.  첫 줄: 용액의 개수 NNN (2≤N≤100,0002 \leq N \leq 100,0002≤N≤100,000).둘째 줄: NNN개의 용액 특성값 (−1,000,000,000≤x≤1,000,000,000-1,000,000,000 \leq x \leq 1,000,000,000−1,000,000,000≤x≤1,000,000,000)이 공백으로 구분되어 주어짐.  #include #include #include #include using namespace std;int main(){ int..

cote/Intermediate 2025. 1. 19. 23:31

기본 아이디어현재 상태에서 **가장 좋은 선택(최적의 선택)** 선택이 선택이 이후 문제에 영향을 미칠지 고민하지 않고, 현재 문제만 고려이렇게 탐욕적인 선택을 반복하면 전체 문제를 해결할 수 있음그리디 알고리즘의 특징탐욕적 선택 속성 (Greedy Choice Property):현재의 탐욕적 선택이 나중에 영향을 미치지 않고, 전체 문제의 최적 해를 보장합니다.부분 최적해 (Optimal Substructure):부분 문제의 최적해가 전체 문제의 최적해로 이어질 수 있어야 합니다.중요: 그리디 알고리즘은 모든 문제에 적합하지는 않음적용 가능한 문제의 조건탐욕적 선택 속성:각 단계에서의 최적의 선택이 전체 문제의 최적해를 보장해야 함최적 부분 구조:문제를 부분 문제로 나누었을 때, 각 부분 문제의 최적해..

자료구조&알고리즘/C++ 2025. 1. 19. 20:48

벨만-포드 알고리즘은 그래프에서 **최단 경로(Shortest Path)**를 구하기 위한 알고리즘으로, 특히 음수 가중치 간선을 포함한 그래프에서도 작동합니다.이 알고리즘은 단순하면서도 강력하며, 음수 사이클(negative weight cycle)을 감지할 수도 있습니다.알고리즘의 특징음수 가중치 허용:다익스트라 알고리즘은 음수 가중치 간선이 있는 그래프에서는 사용할 수 없지만, 벨만-포드 알고리즘은 음수 가중치를 포함한 그래프에서도 작동합니다.음수 사이클 탐지:음수 사이클이 존재하는 경우, 무한히 작은 경로를 만들 수 있기 때문에 최단 경로를 계산할 수 없습니다.벨만-포드 알고리즘은 음수 사이클의 존재 여부를 확인할 수 있습니다.시간 복잡도:O(V×E)O(V \times E)O(V×E), 여기서 V..

자료구조&알고리즘/C++ 2025. 1. 13. 19:00