파이썬 알고리즘 및 자료구조 기초 문제 풀이
시간 복잡도 비교 문제
AList = [1, 2, 3], BSet = {1, 2, 3}일 때 다음 질문에 답하시오:
값 4를 찾을 때, 리스트와 집합 중 어느 쪽의 최악 시간 복잡도가 더 큰가?
값 4를 삽입할 때, 리스트와 집합 중 어느 쪽의 최악 시간 복잡도가 더 큰가?
답변:
검색 연산의 경우, 리스트와 집합 모두 O(n)의 시간 복잡도를 가진다.
삽입 연산의 경우, 리스트는 O(n), 집합은 평 ...
5월 25일 12:42에 게시됨
NOI 2025 연습 문제 풀이 기록 (제5회)
라운드 #77 - 20250521
A. 직렬 연결 (link)
문제 요약
각 정점에 두 가중치 \(a_i, b_i\)를 가진 트리가 주어진다. 단순 경로가 "좋은 경로"가 되려면 경로상의 \(b\) 합계와 경로상의 최소 \(a\) 값의 곱이 상수 \(V\) 이상이어야 한다. 모든 좋은 경로 중 \(\sum b\)의 최솟값을 구한다.
핵심 아이디어
정점 분할을 적용하면 조건은 \((B_u+B_v)\min(A_u,A_v) \ge V\) ...
5월 24일 02:35에 게시됨
C++ 템플릿 기반 이중 원형 연결 리스트 구현
이중 원형 연결 리스트의 노드 클래스 설계
이중 연결 리스트의 핵심은 각 노드가 이전 노드와 다음 노드를 모두 가리키는 포인터를 가진다는 점입니다. 템플릿을 활용하여 다양한 데이터 타입을 지원하도록 구현합니다.
template<typename T>
class DNode {
public:
T data;
DNode* next;
DNode* prev;
DNode() : data(T()), next(nullptr), p ...
5월 21일 08:11에 게시됨