1920번,10989번, 12865번

1. 수 찾기

링크 - https://www.acmicpc.net/problem/1920

코드

import sys
input = sys.stdin.readline


n = int(input())
arr = list(map(int,input().split()))
arr.sort()

m = int(input())
question = list(map(int,input().split()))

for q in question:
    start=0
    end=n-1
    flag=False
    while start<=end:
        mid = (start+end)//2
        if arr[mid]==q:
            print(1)
            flag=True
            break
        if arr[mid]>q:
            end = mid-1
        else:
            start=mid+1
    if flag==False:
        print(0)

처음에는 in함수를 이용해서 풀었는데 시간초과가 나서 이분탐색 방법으로 풀었다.

2. 수 정렬하기3

링크 - https://www.acmicpc.net/problem/10989

코드

import sys
input = sys.stdin.readline

n = int(input())
arr=[0]*(10001)
for i in range(n):
    arr[int(input())]+=1
    

for i in range(10001):
    if arr[i]!=0:
        for j in range(arr[i]):
            print(i)

1. 단순히 append(), sort()함수를 이용했을 때,메모리 초과가 났었다.
   빈 리스트를 생성하고 append()함수를 사용하면 메모리 재할당이 이루어지기 때문에, 메모리 초과가 생기는 것이었다.

2. 10001개의 공간을 미리 할당하고 0부터 n-1번째 까지 값을 넣어준 후 sort()함수를 사용했다. -> 메모리 초과
   n이 작은 수여도 sort()함수를 사용하면 10000개의 공간의 리스트를 정렬해주어야 하는 것이었다.

3. 입력받은 숫자의 개수를 count해주는 방식을 사용->성공
   정렬을 따로 하지 않아도 배열의 인덱스를 활용하여 정렬을 한 효과를 주었다.

3. 평범한 배낭

링크 - https://www.acmicpc.net/problem/12865

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

laguage = [[0,0]]
dp = [[0]*(k+1) for _ in range(n+1)]

for i in range(n):
    laguage.append(list(map(int, input().split())))

for i in range(1, n+1):
    for j in range(1, k+1):
        w = laguage[i][0]
        v = laguage[i][1]

        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)

print(dp[n][k])

dp 알고리즘 중 가장 대표적인 냅색 알고리즘이다.
w=[6,4,3,5]
v=[13,8,6,12] 이고 k=7일 때,
그리디를 사용하면 w=6,v=13을 출력하지만
가장 큰 value값은 w=4+3,v=8+6이다.

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)

i번째 짐을 포함하는 것이 더 큰지, 아니면 이전의 값을 그대로 가져오는 것이 더 큰지를 비교하는 점화식이다.

흠.. 내일부터는 책에 있는 문제 풀어야 겠다..