수학과의 개발자 도전기

- 문제 : https://www.acmicpc.net/problem/2631

정답 풀이 

주어진 배열을 오름차순 정렬하기 위해 움직여야하는 최소 원소의 개수를 출력하는 문제

다이나믹 프로그래밍으로 주어진 배열에서 len(배열) - len(가장 긴 증가하는 부분수열)를 구하면 된다. 

가장 긴 증가하는 부분 수열의 원소들은 그대로 두고, 속하지 않는 원소들만 움직이면 최소한으로 원소를 움직일 수 있기 때문이다. 

풀이 과정

1. dp는 i번째 원소가 속하는 증가하는 부분수열의 최대 길이를 저장한다. 부분 수열에는 원소 개수가 최소 1개는 있으므로 1로 배열을 초기화한다. 

2. 주어진 원소를 순회하면서 arr[i](i번째 원소)와 arr[j] 원소([1, i - 1])에 대해 arr[i] > arr[j]인 경우에 대해 연산을 진행한다. 

    2-1. arr[i]> arr[j] 이므로 arr[i]는 이전의 arr[j]가 포함된 증가하는 부분수열에 포함될 수 있다. 그런데 이때 arr[i]가 다른 부분 수열에 속해있을 수 있으므로 dp[i]와 dp[j] + 1 중 최댓값을 dp[i]에 저장한다. 

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

3. 이렇게 구한 dp의 값 중 최댓값이 가장 긴 부분수열의 길이이므로 이 값을 n에서 뺀다. 

n - max(dp)

n = int(input())

arr = [0]
for _ in range(n):
    arr.append(int(input()))
    
dp = [1] * (n + 1) # 원소가 하나인 부분 수열 있을 수 있기 때문
for i in range(1, n + 1):
    for j in range(1, i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

            
# 배열 길이 - 가장 긴 증가하는 부분 수열 길이
print(n - max(dp))

Reference

https://velog.io/@soobin519/Python-%EB%B0%B1%EC%A4%80-2631-%EC%A4%84%EC%84%B8%EC%9A%B0%EA%B8%B0

- 문제 : https://www.acmicpc.net/problem/1940

정답 풀이 - 딕셔너리

배열에 주어진 수들 중에 두 원소의 합이 m인 경우의 수를 출력하는 문제다.

투 포인터 문제라고는 하는데, 투 포인터로는 어떻게 풀어야할지 생각이 안나서 딕셔너리로 {숫자 : 개수} 형태로 풀었다. 배열의 수와 m은 고정된 수이기 때문에 나머지 다른 값이 arr에 존재하는 경우만 세면 된다고 생각해서 그렇게 어렵지는 않았지만, 케이스 생각하느라 약간 헤맸다.

풀이 과정

1. 주어진 배열에 대해서 숫자의 개수를 numbers 딕셔너리{숫자 : 개수}에 저장한다. (Counter 라이브러리를 사용해도 된다)

2. arr[i] + target = m 이 되는 target(target = m - arr[i])의 존재여부에 따라 numbers[key]의 value를 하나씩 뺀다(중복 케이스 를 피하기 위함). 

이때 arr[i] == target인 경우와 arr[i] != target인 경우로 나누어서 진행해야 한다. 

    2-1. arr[i] == target 일 때, numbers[arr[i]] >= 2 이어야 하기 때문에 이것도 체크해줘야 한다. 왜냐하면 중복 케이스 제거를 위해 numbers[arr[i]]의 값을 하나씩 줄일텐데 이 경우에는 같은 숫자가 2개이므로 2를 감소시켜야 하기 때문이다. 

if arr[i] == target and numbers[target] >= 2:

    2-2. arr[i] != target 일 때, 먼저 target이 numbers 키에 존재해야하고 그 다음에 중복 케이스 제거를 위해 value를 -1 할 텐데, 이게 음수가 되면 안되기 때문에 numbers[target] > 0 이어야 한다. 

if arr[i] != target and target in numbers and numbers[target] > 0:

3. 2-1과 2-2에 해당하는 경우가 정답 케이스이므로, 각 케이스마다 answer += 1을 한다.

4. 그동안 센 정답 케이스인 answer를 출력한다.

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

answer = 0
arr = sorted(list(map(int, input().split())))
numbers = {}
for i in range(n):
    if arr[i] in numbers:
        numbers[arr[i]] += 1
    else:
        numbers[arr[i]] = 1
    
for i in range(n):
    target = m - arr[i]
    if arr[i] == target and numbers[target] >= 2:
        numbers[target] -= 1
        numbers[arr[i]] -= 1
        answer += 1
    if arr[i] != target and target in numbers and numbers[target] > 0:
        numbers[target] -= 1
        numbers[arr[i]] -= 1
        answer += 1
  
print(answer)

정답 풀이 - 투 포인터 

투 포인터 문제이니 해당 풀이도 찾았는데, 로직이 이진 탐색과 비슷하다.

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
nums = list(map(int,input().split()))

nums.sort()
left, right = 0, len(nums) - 1
count = 0

while left < right:
    sum_num = nums[left] + nums[right]
    if sum_num < m:
        left += 1
    elif sum_num > m:
        right -= 1
    else:
        count += 1
        left += 1
        right -= 1

print(count)

Reference

투 포인터 풀이 블로그 : https://jminie.tistory.com/108

- 문제 : https://www.acmicpc.net/problem/12869

정답 풀이

주어진 각 scv의 체력을 각각 감소 시키는데 0, 0, 0을 만드는데 최소한의 횟수를 구하는 문제다. 

어떻게 풀어야할지 잘 몰랐는데 블로그를 참고하니 3차 행렬을 이용하면 된다고 한다. 

1. dp[i][j][k]는 각 scv의 체력이 i, j, k일 때의 공격 받은 횟수를 의미한다.

2. 삼중 for문으로 배열을 순회하며 모든 경우의 수([1, 3, 9]의 permutation = 3!)를 고려해 공격한다. 공격하면 인덱스가 줄어든다.

3. 아예 처음인 체력(dp[][][] == 0)이거나 현재 있는 체력 값보다 이전 체력값 + 1이 더 작은 경우에 업데이트 한다.

if dp[ni][nj][nk] == 0 or dp[ni][nj][nk] > dp[i][j][k] + 1:

4. dp[0][0][0]은 모든 체력이 0, 0, 0일 때의 최소 공격 수 이므로, 출력한다. 이때 초기화하느라 1을 추가했으므로 이를 빼주고 출력해줘야 한다.

n = int(input())
scv = list(map(int, input().split())) + [0, 0] # 3개 미만이 들어왔을 때 개수 맞춰주기 위함

# dp[i][j][k] 값은 각 scv 체력이 i, j, k 일 때 공격 받은 횟수를 의미한다
dp = [[[0] * 61 for _ in range(61)] for _ in range(61)] 
dp[scv[0]][scv[1]][scv[2]] = 1 # 1로 초기화, 마지막에 1을 빼줘야 한다

case = [[1, 3, 9], [1, 9, 3], [3, 1, 9], [3, 9, 1], [9, 1, 3], [9, 3, 1]]
for i in range(60, -1, -1):
    for j in range(60, -1, -1):
        for k in range(60, -1, -1):
            if dp[i][j][k] > 0:
                for c in case:
                    ni = max(i - c[0], 0)
                    nj = max(j - c[1], 0)
                    nk = max(k - c[2], 0)
                    
                    # 처음 도착한 경우 or 더 적은 횟수로 도착하는 경우에만 업데이트
                    if dp[ni][nj][nk] == 0 or dp[ni][nj][nk] > dp[i][j][k] + 1:
                        dp[ni][nj][nk] = dp[i][j][k] + 1
                        
print(dp[0][0][0] - 1)

Reference

https://cme10575.tistory.com/169

- 문제 : https://www.acmicpc.net/problem/21921

정답 풀이 

길이가 x인 구간의 원소합을 누적합으로 푸는 문제이다. (이중 반복문으로 풀면 시간복잡도가 올라갈 것 같다)

그런데 여기서 주의해야할 점이 2가지 있다. 

1. 누적합 계산식

일단 주어진 배열을 누적해서 더한 값을 num_sum이라는 배열에 저장한 뒤 반복문 돌면서 num_sum[i + x -1] - num_sum[i - 1] 계산식으로 각 구간의 합 중 최댓값을 answer에 저장하면된다. 

num_sum[i + x -1] - num_sum[i - 1]

여기서 헤맸던 부분이 위 계산식이다. i를 포함하고 길이가 x가 되려면 오른쪽 끝 인덱스는 i + x - 1이 되는 것 까지는 알았는데, 시작점이 i가 아니다. 누적합이라 i는 0인덱스부터 i인덱스까지의 합이므로 num_sum[i]를 빼는 것이 아니라, i 이전인 i - 1 값을 빼줘야 한다. 왜 그래야 하는지는 아래의 그림으로 쉽게 설명이 가능하다. 그래서 위의 계산식이 나온다.

2. 위 계산식으로는 엔드케이스(0부터 x - 1 까지)를 포함하지 못한다

누적합의 원리를 토대로 계산식은 구했지만 위 계산식으로는 i의 범위가 [1, n - x + 1]이 된다. 이렇게 진행하면 사실상 1부터 x 길이의 구간합을 구하는 것이라 0부터 x - 1까지의 누적합 계산을 하지 못한다. 그래서 num_sum과 arr 가장 왼쪽에 0을 추가해 엔드케이스까지도 포함해 계산할 수 있게 했다. 

arr = [0] + list(map(int, input().split()))

num_sum = [0] * (n + 1)
num_sum[1] = arr[1]
for i in range(2, n + 1):
    num_sum[i] = num_sum[i - 1] + arr[i]

n, x = map(int, input().split())
arr = [0] + list(map(int, input().split()))

num_sum = [0] * (n + 1)
num_sum[1] = arr[1]
for i in range(2, n + 1):
    num_sum[i] = num_sum[i - 1] + arr[i]


answer = 0
for i in range(n - x + 1):
    answer = max(answer, num_sum[i + x] - num_sum[i])


if answer == 0:
    print("SAD")
else:  
    count = 0
    for i in range(n - x + 1):
        result = num_sum[i + x] - num_sum[i]
        if result == answer:
            count += 1

    print(answer)
    print(count)