수학과의 개발자 도전기

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

이 문제는 케이스 분류 + 누적합으로 푸는 문제다. 먼저 누적합을 구하는 원리를 알아야 하는데, 아래 그림을 참고하면 된다. 여기서 sum_arr[i] 는 0 ~ i 인덱스까지의 합을 의미한다. 

특정 구간의 누적합 구하기

정답 풀이

누적합

원소의 합을 빠르게 구해야하므로 기존 배열의 값의 누적합을 sum_arr 이름의 배열에 저장한다.

케이스 분류

벌집 1개와 벌 2마리를 1차원 배열에 위치시킨 뒤 벌 2개가 벌집에 가는 길에 있는 원소의 최대 합을 누적합으로 구한다. 이 경우에는 벌벌꿀, 꿀벌벌, 벌꿀벌 총 3가지 케이스를 나누어서 진행하면된다. 모든 케이스는 ABC 형식인데, A는 0 인덱스, C는 (n - 1) 인덱스에 있고, B의 위치만 i로 for문으로 변경시키면서 최댓값을 구하는 로직이다. 

1. 벌벌꿀

이 경우에는 벌 하나가 0 인덱스, 벌집이 (n - 1) 인덱스에 있고, 벌이 for 문으로 i 인덱스(1 ~ n - 1)에 있다. 벌은 벌이 있는 곳을 지나갈 수 없으므로 움직일 수 있는 범위는 [1, n - 1]이다. 

0 인덱스의 벌을 bee1, i 인덱스의 벌을 bee2라고 하자.

- bee1은 [1, i - 1], [i + 1, n - 1]까지의 원소 합(bee2가 있는 i 번째는 빼야 한다) -> sum_arr[n - 1] - sum_arr[0] - arr[i] 

- bee2는  bee2는 [i + 1, n - 1]까지의 원소 합 -> sum_arr[n - 1] - sum_arr[i]

2. 꿀벌벌

이 경우에는 벌집이 0 인덱스, 벌 하나가 (n -1) 인덱스에 있고, 벌이 for 문으로 i 인덱스(1 ~ n - 2)에 있다. 벌은 벌이 있는 곳을 지나갈 수 없으므로 움직일 수 있는 범위는 [0, n - 2]이다. 

(n - 1) 인덱스의 벌을 bee1, i 인덱스의 벌을 bee2라고 하자.

- bee1은 [0, i - 1], [i + 1, n - 2]까지의 원소 합(bee2가 있는 i 번째는 빼야 한다) -> sum_arr[n - 2]  - arr[i] 

- bee2는  [0, i - 1]까지의 원소 합 -> sum_arr[i -1]

3. 벌꿀벌

이 경우에는 벌이 0 인덱스와 (n - 1) 인덱스에 있고, 벌집이 for 문으로 i 인덱스(1 ~ n - 2)에 있다. 

0 인덱스의 벌을 bee1, (n - 1) 인덱스의 벌을 bee2라고 하자.

- bee1은 [1, i]까지의 원소 합 -> sum_arr[i]  - arr[0] 

- bee2는  [i, n - 2]까지의 원소 합 -> sum_arr[n - 2] - sum_arr[i - 1]

각 케이스에서의 bee1 + bee2 최댓값을 구하고, 그 중에서의 최댓값을 answer에 저장한 뒤 출력하면 된다.

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

answer = 0
sum_arr = [0] * n
sum_arr[0] = arr[0]
for i in range(1, n):
    sum_arr[i] = arr[i] + sum_arr[i - 1]
    
# 벌벌꿀
for i in range(1, n):
    bee1 = sum_arr[n - 1] - sum_arr[0] - arr[i]
    bee2 = sum_arr[n - 1] - sum_arr[i]
    answer = max(answer, bee1 + bee2)
  
# 꿀벌벌
for i in range(1, n - 1):
    bee1 = sum_arr[-2] - arr[i]
    bee2 = sum_arr[i - 1]
    answer = max(answer, bee1 + bee2)

# 벌꿀벌
for i in range(1, n - 1):
    bee1 = sum_arr[i] - sum_arr[0]
    bee2 = sum_arr[n - 2] - sum_arr[i - 1]
    answer = max(answer, bee1 + bee2)
    
    
print(answer)

Reference

https://velog.io/@a87380/21758%EB%B2%88-%EA%BF%80-%EB%94%B0%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

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

부분수열이 꼭 기존의 배열 순서를 유지해야한다고 생각해서 헤맸던 문제다.

- 부분수열은 굳이 순서 유지될 필요 없다.

- 길이가 i(1 ~ n)인 배열을 combinations으로 임의로 뽑는다.

- sum(arr)한 값이 s와 같을 때 answer += 1을 해주면 된다.

정답 풀이 

from itertools import combinations

# 부분수열은 주어진 배열에서 순서 상관없이 뽑는 것이다?
# 굳이 원래 배열 순서대로 연속될 필요 없음
n, s = map(int, input().split())
arr = list(map(int, input().split()))

answer = 0
for length in range(1, n + 1):
    for each in combinations(arr, length):
        if sum(each) == s:
            answer += 1
            
print(answer)

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

정답 풀이

이 문제는 다음과 같은 과정으로 진행된다.

• 주어진 배열의 원소들 중 한 번에 2개의 원소씩 짝지어 값을 더한다. 이때 각 값의 합이 최소가 되도록 해야한다 -> (그리디)
• 두 숫자의 합이 최소가 되기 위해서는, 원소를 오름차순 정렬한 후 양쪽에 있는 값을 더하면 된다. [i번째] 원소 +  [n - 1 -i ]번째 원소
• 이 때 반복문 범위는 인덱스 0부터 절반까지 진행한다. 절반에서 원소가 정해지면 반대편은 자동으로 정해지기 때문이다. 값 중복하지 않기 위함도 있다. 
• 배열 원소 개수가 홀수인 경우에는 두 개씩 묶고 하나의 원소가 남기 때문에 아래와 같이 추가 연산이 필요하다.
  • 모든 원소가 짝지어지고 하나의 원소가 남는데, 그 원소가 가장 큰 숫자이면 된다. 배열을 오름차순 정렬했으므로 가장 오른쪽 값만   result에 넣는다.

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

result = []
if n % 2 == 1:
    result.append(arr.pop())

m = len(arr)
for i in range(m // 2):
    result.append(arr[i] + arr[m - 1 - i])
    
    
print(max(result))

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

딕셔너리에서 이중 정렬하는 거를 맨날 까먹어서 기록한다. 이젠 까먹지 말자!!

sorted(num_dic.items(), key = lambda x : (-x[1][0], x[1][1]))

정답 풀이

arr = {숫자 : [횟수, 인덱스]} -> 횟수 내림차순, 횟수 같으면 인덱스 오름차순

n, c = map(int, input().split())
numbers = list(map(int, input().split()))

num_dic = {}
for i in range(n):
    number = numbers[i]
    if number in num_dic.keys():
        num_dic[number][0] += 1
    else:
        num_dic[number] = [1, i]
        
result = sorted(num_dic.items(), key = lambda x : (-x[1][0], x[1][1]))

answer = ''
for num, arr in result:
    for i in range(arr[0]):
        answer += str(num) + ' '
        
print(answer)