5주차 스터디

[jjsyeon]

B형 시험 대비

1. 링크드 리스트 (추천): No. 3 [Pro] 승강제리그
2. 그래프 최적화 - 유니온 파인드: No. 11 [Pro] 호텔방문
3. 세그먼트 트리: No. 5 [Pro] 성적조회

[juhye87]

발표자 : 정연
문제 : No. 3 [pro] 승강제리그
질문 : 시간복잡도 얼마?

대답 : 계산은 안해봤는데 treeset 써서 맨 앞이랑 맨 뒤 삽입 삭제 조회 빠르고, 중간 값 찾는 것도 remove로 해서 빨랐을 것으로 추정한다.

• 용모님 설명 : 세그먼트 트리로 풀 수 있다

🚀 세그먼트 트리를 활용한 K번째 작은 값 찾기

🔹 개요
배열에서 K번째 작은 값을 빠르게 찾는 문제
세그먼트 트리 + 이분 탐색을 활용하여 해결

🔹 접근 방법
좌표 압축: 값의 범위를 [1, 10,000]로 변환하여 등장 횟수를 저장
세그먼트 트리 구축: 각 값의 등장 횟수를 저장하고, 구간 합을 O(log N)에 계산
K번째 값 찾기: 이분 탐색(O(log N)) + 세그먼트 트리(O(log N)) 활용
업데이트 연산 (O(log N)): 값 추가/삭제 시 세그먼트 트리 갱신

🔹 시간 복잡도
K번째 값 찾기: O(log^2 N)
업데이트/구간 합 연산: O(log N)

✅ 동적 배열에서도 K번째 작은 값 탐색 가능! 🚀

[juhye87]

발표자 : 예림
문제 : No. 3 [pro] 승강제리그
질문 : treeset 돌리는 게 터지면 list로 바꿔서 한다고 했는데 list로 바꾸면 시간복잡도가 어떻게 되나?

답변 : list로 바꾸는 것도 탐색 후에 넣는 거라 오래 걸리는 걸로 알고 있다.

질문 : 그럼 그냥 iterator로 하는 게 더 좋은 거 아닌가?

답변 : 그런 것 같다

• 정연님 : 정렬된 리스트를 treeset으로 바꾸는 건 nlogn이다

• 권민님 이분탐색으로 한 거 풀이함

[juhye87]

발표자 : 은성
문제 : No. 5 [pro] 성적조회

[juhye87]

B형 시험 : 오프라인 다이나믹 커넥티비티 알고리즘
아니면 유니온파인드 최적화 잘해야됨

[juhye87]

발표자 : 권민
문제 : No.11 [pro] 호텔방문
질문 : 핵심이 arraylist 관리하는 거랑 다익스트라 두 개?

답변 : 맞다

추가 질문 : 다익스트라 시간복잡도

답변 : (N + m ) logn
N: 노드 개수
M: 간선 개수

우선순위 큐에 넣을 때 log n 뺄 때 log n