Tags

118 pages

Space Complexity

[Algorithm] cpp-python 백준 9244번: 핀볼 - 스위프 라인

선분이 서로 교차하지 않는 핀볼 보드에서 x=x0로 공을 떨어뜨릴 때, 선분을 만난 뒤에는 더 낮은 끝점으로 흘러 다시 수직 낙하합니다. 스위프 라인과 활성 집합으로 각 선분 하단에서 바로 아래 선분을 연결해 흐름 그래프를 만든 뒤, 시작 x에서 최상단 선분부터 따라 내려가 O(N log N)으로 최종 x좌표를 구합니다. 정수 기하 비교로 오차 없이 안전하게 구현합니다.
[Algorithm] cpp-python 백준 9244번: 핀볼 - 스위프 라인

[Algorithm] C++ 백준 18438 번 : LCS 5

백준 18438 LCS 5는 최대 7000 길이의 두 문자열에 대해 LCS의 길이와 실제 수열을 모두 출력해야 하는 문제입니다. 4MB 메모리 제한 때문에 전형적인 2차원 DP 테이블을 저장할 수 없으므로, O(nm) 시간에 O(min(n,m)) 메모리만 사용하는 Hirschberg 알고리즘으로 안전하게 복원합니다. 전방·후방 1차원 DP, 분할 지점 선택, 경계 처리와 빠른 입출력까지 반영한 C++ 구현과 복잡도 분석을 제공합니다.
[Algorithm] C++ 백준 18438 번 : LCS 5