2025.03.23
TIL(TODAY I LEARN)
-
WEEK02 :
이분 탐색, 분할 정복, 스택, 큐, 우선순위 큐, Linked List, 해시 테이블 -
알고리즘을 통해 개념을 익혀보자
-
2주차 문제들은 확실히 이전 주보다 어렵다.
-
개념자체는 그렇게 어렵지 않은 느낌인데 그냥 문제에 적용할 아이디어가 쉽게 떠오르지 않는다.
-
문제로 결정문제로 바꾼다던지, 추가적인 개념들을 더 알아야 문제해결의 실마리가 보이는 느낌
두뇌를 새롭게 리프레쉬 하자.
6549 - 히스토그램에서 가장 큰 직사각형 - 플래티넘5
문제 링크 - https://www.acmicpc.net/problem/6549
내 코드
import sys
input = sys.stdin.readline
while True:
#입력 받기
h = list(map(int,input().split()))
n, H = h[0] , h[1:] # 리스트 길이, 높이 리스트
if n == 0:
break
# 문제 해결
# 완전 탐색 (시간 초과)
# max_extent = 0
# for h in range(1,max(H)+1):
# cnt = 0
# for j in H:
# if j >= h:
# cnt += 1
# else:
# extent = cnt * h
# cnt = 0
# max_extent = max(max_extent,extent)
# if cnt > 0:
# extent = cnt * h
# max_extent = max(max_extent,extent)
# print(max_extent)
# 분할정복
def merge(l,r,l_extent,r_extent):
global max_extent
# 합쳤을 때 넓이 =
#l의 가장 우측 인덱스부터 + r의 가장 좌측 인덱스부터
#합쳐서 넓이 구하기
m_extent = 0
h = min(l[len(l)-1],r[0]) # 가운데 초기 높이
m_extent = h*2
pl = len(l)-1
pr = 0
while pl > 0 or pr < len(r) -1 :
if pr < len(r)-1 and (pl == 0 or r[pr + 1] >= l[pl - 1]):
pr += 1
h = min(h,r[pr])
elif pl > 0:
pl -= 1
h = min(h,l[pl])
else:
break
width = (len(l) - pl) + pr + 1
area = h * width
m_extent = max(area, m_extent)
#리스트 합쳐서 반환
merge_list = l + r
# 좌,우,합침 리스트 중 가장 큰 넓이 반환
merge_extent = max(l_extent,r_extent,m_extent)
return merge_list, merge_extent
def sol(u_list):
if len(u_list) <= 1:
extent = u_list[0] * 1
return u_list, extent
mid = len(u_list) // 2
left = u_list[:mid]
right = u_list[mid:]
left_li, left_extent = sol(left)
right_li, right_extent = sol(right)
return merge(left_li,right_li, left_extent, right_extent)
x,y = sol(H)
print(y)다른 코드(스택)
import sys
input = sys.stdin.readline
while True:
#입력 받기
h = list(map(int,input().split()))
n, H = h[0] , h[1:] # 리스트 길이, 높이 리스트
H.append(0) #마지막 값 pop을 위해 0 삽입
if n == 0:
break
max_area = 0
stk = []
for i in range(len(H)):
while stk and H[stk[-1]] > H[i]:
top = stk.pop()
height = H[top]
width = i if not stk else i - stk[-1] - 1
max_area = max(max_area,height * width)
stk.append(i)
print(max_area)
- 스택에 대한 이해가 모자람.
- 어떻게 구현을 해야할지 막막함
- 인덱스처리가 미숙
문제 분류
8983 - 사냥꾼 - 골드4
문제 링크 - https://www.acmicpc.net/problem/11053
내 코드
import sys
from bisect import bisect_left
input = sys.stdin.readline
M,N,L = map(int,input().split())
Mx = list(map(int,input().split()))
Mx.sort()
animals = []
for _ in range(N):
x,y = map(int,input().split())
animals.append([x,y,False]) # 좌표, 사살 여부
# 60점짜리 코드
# for i in range(M):
# for j in range(N):
# if abs(Mx[i]-animals[j][0]) + animals[j][1] <= L and animals[j][2] == False:
# animals[j][2] = True
# cnt = 0
# for i in range(N):
# if animals[i][2] == True:
# cnt += 1
# print(cnt)
for i in range(N): #동물을 기준으로 사대에서 이진탐색. 가까운 사대가 못죽이면 못죽여
x, y = animals[i][0], animals[i][1]
if y > L:
continue
closed_Mx = bisect_left(Mx,x) #가장 가까운 사대의 x좌표
if closed_Mx < M and (abs(Mx[closed_Mx] - x) + y) <= L: # 우측 사대 or 동물/사대 같은 위치
animals[i][2] = True
elif closed_Mx > 0 and (abs(Mx[closed_Mx - 1] - x) + y) <= L: # 좌측 사대
animals[i][2] = True
cnt = 0
for i in range(N):
if animals[i][2] == True:
cnt += 1
print(cnt)
- 동물을 기준으로 잡고 동물에 대한 이분정렬을 시도
- 가장 가까운 동물을 못잡으면 다른 동물도 못잡음!
- 동물을 중복으로 잡지 못함 한번 죽으면 끝
문제 분류
매개변수 탐색 문제가 너무 어렵다.
어떤걸 이진탐색으로 해야하는가. 결정문제로 바꾸는 그 아이디어 떠올리기가 안된다.
^_^