say repository

#11053
import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
d = [0]*n

for i in range(n):
    for j in range(i):
        if a[j] < a[i] and d[j] > d[i]:
            d[i] = d[j]
    d[i] += 1
print(max(d))

풀이

A = {10, 20, 10, 30, 20, 50} 로 경우의 수를 나눠서 구해보면 된다.

반복문을 돌면서, 자기 자신보다 작은 수열 중 가장 길이가 긴 수열의 크기 +1

 if a[i]>a[j]  -> 자기 자신보다 작은 수열

and d[j] > d[i] -> 가장 길이가 긴 수열의 크기

#2156
import sys
n = int(sys.stdin.readline())
arr = [0]*10000 #포도주
for i in range(n):
    arr[i] = int(sys.stdin.readline())

#dp테이블
#dp[i] = 0부터 i번째 포도주까지 최대로 마신 양
dp = [0] * 10000
dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[0]+arr[2], arr[1]+arr[2], dp[1])

for i in range(3,n):
    dp[i] = max(dp[i-2]+arr[i], arr[i-1]+arr[i]+dp[i-3], dp[i-1])
print(max(dp))

풀이

다이나믹 프로그래밍이다.

dp[i] 는 처음부터 i번째까지 최대한 마신 포도주의 양이다.

dp[0] 부터 계산하면 점화식이 나오고 계산한다.

그 중 가장 큰 값을 출력하면 된다.

출처 : 백준

import sys
import heapq
n = int(sys.stdin.readline())
left_heap = [] #최대힙
right_heap = [] #최소힙
for _ in range(n):
    num = int(sys.stdin.readline())
    if len(left_heap) == len(right_heap):
        heapq.heappush(left_heap,-num)
    else:
        heapq.heappush(right_heap,num)

    if len(left_heap)>=1 and len(right_heap)>=1 and -left_heap[0] > right_heap[0]:
        #중간값이 중간값이 아니면
        l_value = -heapq.heappop(left_heap)
        r_value = heapq.heappop(right_heap)

        heapq.heappush(left_heap,-r_value)
        heapq.heappush(right_heap,l_value)
    print(-left_heap[0])

풀이

우선순위 큐를 사용해서 풀어야겠다는 생각까지는 했지만 시간초과가 났다.

다른 사람의 풀이들을 찾아보고 공부했다.

최대힙, 최소힙 모두 사용해야한다.

최대힙 : 중간 값 보다 작은 값들을 삽입한다. (내림차순 정렬)

최소힙 : 중간값보다 큰 값들을 삽입한다. (오름차순 정렬)

이 두가지만 생각하고 풀면 최대힙의 첫번째 원소값이 결국 배열의 중간값이 된다.

최대힙을 left_heap

최소힙을 right_heap으로 뒀다.

1) left_heap에 먼저 삽입

2) 다음, right_heap에 삽입 

3) 둘 다 원소가 있고  중간 값보다 더 큰 값이 left_heap[0]에 있을때.... 

len(left_heap) >=1 and len(right_heap)>=1 and -left_heap[0] > right_heap[0]: 

-left_heap[0] , right_heap[0] 이 값을 서로 부호와 원소를 바꿔준다.

right_heap에 있는 모든 수는 left_heap에 있는 수보다는 커야한다. (중간값이 left_heap[0]에 있으니까!!!! )

4) 중간값 출력 left_heap[0]

import sys
n,c = map(int,sys.stdin.readline().split())
house = []
for _ in range(n):
    house.append(int(sys.stdin.readline()))
#집 오름차순 정렬
house.sort()
start = 1
end = house[-1]-house[0] #집 좌표 차이 최댓값
result = 0
while start<=end:
    mid = (start+end) // 2
    #처음 집부터 공유기 설치
    now = house[0]
    cnt = 1

    for i in range(1,len(house)):
        if house[i] >= now + mid:
            #공유기 설치
            cnt+=1
            now = house[i]
    #공유기 개수가 c가 되어야 한다.
    if cnt >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1
print(result)

풀이

집 좌표가 10억이 넘어서 이분탐색으로 풀이해야 시간 초과가 나지 않는다.

집 좌표 차이가 중요하므로 오름차순으로 정렬하고 탐색을 시작한다.

start = 1 , end = 마지막 원소 - 첫번째 원소  ( 하면 가장 큰 차이의 좌표 차가 나온다.)

이분 탐색을 진행한다.

1. 설치된 공유기 수가 c보다 작으면  - 공유기를 더 설치해야 한다. end = mid-1
2. 설치된 공유기 수가 c보다 크거나 같다면 - 공유기를 덜 설치해야한다. start = mid+1

출처 : 백준

import sys
import heapq
n = int(sys.stdin.readline())
q = []
for i in range(n):
    x = int(sys.stdin.readline())
    if x == 0:
        #배열에서 가장 작은 값 출력 없으면 0
        if len(q)==0:
            print(0)
        else:
            print(heapq.heappop(q)[1])
    else:
        #배열에 x값 넣기
        heapq.heappush(q,(abs(x),x))

풀이

우선순위 큐를 사용한다.

절댓값이 작은 수 먼저 출력, 절댓값이 같은 수가 여러 개면 값이 작은 수 출력. 

이를 봐서 (abs(x),x) 튜플 형태로 절댓값과 수를 함께 우선순위 큐에 삽입한다.

우선순위 큐는 디폴트로 튜플의 첫 번째 값인 절댓값 기준으로 정렬된다.

import sys
input = sys.stdin.readline
n = int(input())
money = list(map(int,input().split()))
m = int(input())

start,end = 0,max(money)

while start<=end:
    mid = (start+end)//2 #상한액
    num = 0
    for i in money:
        # 상한액보다 요청 금액이 크면 상한액 배정
        if i >= mid:
            num += mid
        else: #아니면 요청 금액 배정
            num += i
    # 배정금액이 총 예산보다 작으면
    if num <= m:
        start = mid + 1
    else:
        end = mid -1
print(end)

풀이

특정 정수 상한액을 정하고 계산해야한다는 부분에서 이분 탐색을 해야 한다고 결론지었다.

start = 0, end = max(요청 금액)

mid = (start+end)//2

start<=end 가 될 때까지 이분 탐색을 반복하자.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int,input().split()) #간선, 노드
start = int(input()) #시작노드
#각 노드에 연결되어 있는 노드에 대한 정보 리스트
graph = [[] for _ in range(n+1)]
distance = [INF]*(n+1)
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))  #노드 a에서 노드 b로 가는 비용이 c라는 의미

#다익스트라
def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q:
        #우선순위 큐에서 가장 최단 거리가 짧은 노드 꺼내기
        dist,node = heapq.heappop(q)
        #현재 노드가 이미 처리된 노드면 무시
        if distance[node] < dist:
            continue
        #현재 노드와 연결된 다른 인접한 노드들 확인
        for i in graph[node]:
            #현재 노드를 거쳐서 다른 노드로 이동하는 거리
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
dijkstra(start)

#모든 노드로 가는 최단거리 출력
for i in range(1,n+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

풀이

최단경로 다익스트라 알고리즘이다.

다익스트라 알고리즘은 그리디 알고리즘에 속한다.

우선순위 큐를 사용해 출발 노드의 인근 노드의 최소 비용을 구해 최단 거리로 이동한다.

python에서의 우선순위 큐는 heapq 라이브러리를 사용해 구현한다.

heapq는 최소힙이 디폴트다.