내일이 시험이기 때문에 DP와 그리디 알고리즘을 더욱 많이 학습했습니다.
10번 11047 동전 0
https://www.acmicpc.net/problem/11047
문제는 주어진 K원을 만들때 동전의 개수를 최소한으로 출력하고 싶다. 그럴려면 K원 한도내에서 제일 큰 동전을 출력해야한다.
import sys
input = sys.stdin.readline
# 그리디 알고리즘
def coin_counter(N, K, coin):
count = 0
for i in range(N-1, -1, -1): # range는 stop값 직전까지 반복하여 0까지 반복
count = count + K // coin[i] # 몫이 결국 동전의 갯수
K = K % coin[i] # 남은 가격 만큼 재계산
return count
# 입력단
N, K = map(int, input().split()) # N: 동전의 종류, K: 만들 가격
coin = []
for i in range(N):
coin.append(int(input().strip()))
print(coin_counter(N, K, coin))생각보다 DP보다 그리디의 코드가 더 간단하다. 그러나 생각하기 힘든건 마찬가지이다.
12:00 ~13:20
식사를 마치고 취침을 하고 왔다. 너무 피곤하다…
13:20 ~
벨로그 간단하게 정리하고, 그리디 하 문제를 좀 더 풀어보겠다.
11번 1541 잃어버린 괄호
https://www.acmicpc.net/problem/1541
주어진 입력에 대해 적절한 괄호로 최솟값을 만드는 것이다. 이러한 최솟값을 구하려면 -바로 다음에 괄호를 치면 된다. 그래야 빼지는 수가 커지니까.
첫번째 시도로 기호별로 나누어서 -나오면 괄호 붙이고, 맨마지막에 닫는 괄호 붙여서 계산하려 했다.
import re
n = input()
n = re.findall(r'\d+|[+-]', n) # 숫자, 기호별로 분해
# (\d: 하나이상의 숫자, |: 또는, re.findeall(): 정규표현식에 맞는 모든 항목을 순서대로 리스트로 추출)
i = 0
while i < len(n):
if n[i] == '-':
n.insert(i + 1, '(') # - 다음 위치에 ( 삽입
i += 1 # 새로 들어간 '(' 건너뛰기
i += 1
else:
n.append(')')
print(n)# 위의 내 의도를 살려서 재작성한 코드이다. 코드가 길다.
import re
n = input()
tokens = re.findall(r'\d+|[+-]', n)
result = 0
temp = 0
minus_found = False
i = 0
while i < len(tokens):
token = tokens[i]
if token == '+':
i += 1
continue
elif token == '-':
minus_found = True
i += 1
continue
num = int(token)
if not minus_found:
result += num
else:
# 뺄셈 이후엔 모든 수를 한꺼번에 빼기
temp += num
# 다음 기호가 '+'이면 계속 더함
if i + 1 >= len(tokens) or tokens[i + 1] == '-':
result -= temp
temp = 0
i += 1
print(result)좀 더 간편하게 푸는 방법을 찾았다. -를 기준으로 앞에 내용끼리 더하고 뒤에 내용 더해서 빼는 방식이다.
# 수식 입력 받기
expr = input()
# '-'를 기준으로 나누기 → 가장 중요한 핵심!
parts = expr.split('-')
# 첫 번째 덩어리는 괄호 없이 그냥 더함
first = sum(map(int, parts[0].split('+')))
# 두 번째 이후 덩어리는 +로 나눈 뒤 모두 더해서 한꺼번에 뺌
rest = 0
for part in parts[1:]:
rest += sum(map(int, part.split('+')))
# 결과 출력: 첫 덩어리에서 나머지를 한 번에 빼기
print(first - rest)내 방식으로 풀어보려다 무리가 있었다. 그래서 - 기준으로 나누어서 계산하는 방식으로 수정했다.
자력으로 풀어볼려고 했는데, 생각보다 잘 풀리지 않았다. GPT의 도움을 받아 더 쉬운 방법인 -기호 기준으로 split하여 푸는 방식으로 해결하였다. -앞의 부분은 그냥 더하고, - 이후에는 + 기호마다 나눈 다음 더해서 이 둘을 한번에 뺏다.
16:30 ~ 18:00
다시 컴퓨터 시스템을 공부하겠다. 노션에 정리하기 보다 눈으로 읽어보며 이해하겠다.
운동을 먼저 진행했다.
18:00 ~ 19:30
식사 후 샤워
19:30 ~
컴퓨터 시스템 3.6 제어문을 읽어보고 있다. 다 못읽었다.
일단 코어타임을 위해 그리디 알고리즘 중문제 한개를 풀어보겠다.
[회의 내용]
블로그, 이진 폐쇄법? → 확인 완료
21:00 ~ 23:30
마지막 코어 타임을 진행했습니다.
일단, 시간이 부족한 관계로 컴퓨터 시스템보다 알고리즘 중 문제를 다 풀어보겠다.
내일 와서는 하 문제 한 개씩 다시 풀어보겠다.(외우기)
12번 1931 회의실 배정
https://www.acmicpc.net/problem/1931
여러개의 회의의 시작시간과 끝나는 시각이 있는데, 이러한 회의의 수가 제일 많은 경우의 수를 출력하면된다. 푸는 아이디어가 도저히 생각나지 않아서 GPT를 참고했다. 종료 시간 기준으로 오름차순 정리하지만, 종료시간이 같으면 시작 시간 기준으로 정렬합니다. 가장 먼저 종료되는 회의를 기준으로 선택합니다. 선택한 회의 종료 시간 이후에 시작하는 회의 중 가장 빨리 끝나는 회의를 선택하는 과정을 반복합니다. 수가 가장 크면 회의의 최대개수입니다.
import sys
input = sys.stdin.readline
# 회의수
N = int(input().strip())
meeting=[]
# 회의 시작, 종료 시각 저장
for _ in range(N):
start, end = map(int, input().split())
meeting.append((start, end))
# 회의 정렬: 종료 시간을 기준으로 오름차순, 종료 시간이 같으면 시작 시간을 기준으로 오름차순
def meeting_sort_key(m):
return (m[1], m[0]) # 종료 시간 → 시작 시간 순으로 재정렬
meeting.sort(key = meeting_sort_key)
# 선택한 회의의 수
count = 0
# 마지막으로 선택한 회의의 종료 시간
last_end_time = 0
# 정렬된 회의들을 순회하며 회의 선택
for start, end in meeting:
# 현재 회의의 시작 시간이 마지막 선택한 회의의 종료 시간 이후라면 선택
if start >= last_end_time:
last_end_time = end # 마지막 회의 시간 갱신
count += 1 # 회의 수 1 추가
# 최대 선택 가능한 회의의 수 출력
print(count)회의수를 구하기 위해 머리로는 답을 아는데, 코드로 풀려면 어떻게 해야되는지 고민을 많이 했습니다. 그런데 생각보다 간단히 끝나는 시각 기준으로 다음 회의를 전개하여 최대수를 구한다는 사실이 특이했습니다.
13번 1946 신입사원
https://www.acmicpc.net/problem/1946
이 문제의 주의 점은 입력된 인풋이 등수이다. 문제 이해하는데 한참 걸렸다. 서류와 면접 둘 다에서 등수가 밀리면 뽑지 않는다. 푸는 방식은 이러하다.
-
서류 등수 기준으로 오름차순 정렬하여 성적이 좋은 순으로 나열
-
확인하여 현재까지 확인한 지원자들 중 면접 등수가 가장 높은 등수 기록
-
지원자 확인시, 해당 지원자의 면접 등수가 현재까지의 최고 면접 등수보다 높으면
-
해당 지원자는 선발 대상이고, 최고 등수로 갱신.
import sys
input = sys.stdin.readline
# 테스트 케이스의 수 입력
T = int(input().strip())
# 각 테스트 케이스에 대한 처리
for _ in range(T):
# 지원자 수 입력
N = int(input().strip())
apply = []
# 각 지원자의 서류 등수와 면접 등수 입력
for _ in range(N):
doc, interview = map(int, input().split())
apply.append((doc, interview))
# 서류 등수를 기준으로 오름차순 정렬(1부터)
apply.sort()
# 선발된 지원자 수 초기화
selected_count = 0
# 면접 등수의 최소값을 무한대로 초기화(비교를 위함)
min_interview = float('inf')
# 정렬된 지원자 리스트를 순회하며 선발 여부 결정
for doc, interview in apply:
# 현재 지원자의 면접 등수가 이전까지의 최소 면접 등수보다 높다면 선발
if interview < min_interview:
selected_count += 1
min_interview = interview # 최소 면접 등수 업데이트
# 결과 출력
print(selected_count)문제가 이해되지 않아서 시간을 좀 쏟았다. 밑에 라인의 for문이 완벽히 이해되진 않지만(이게 어떻게 서류, 면접 순위를 고려하는지...) 시간 부족 관계로 다음 문제로 넘어가 보겠다.
6번 11049 행렬 곱셈 순서
https://www.acmicpc.net/problem/11049
추후 추가 예정
7번 11053 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11049
해당문제를 DP로 풀려면, 초깃값0으로 둔다. 배열중 제일 작은값 잡은 다음에 그다음 큰 수 카운팅하면서 순회돌고, 그 중에서 가장 큰 수를 출력하면되지 않을까 싶다.
n = int(input())
A = list(map(int, input().split()))
# dp[i]: A[i]까지 고려했을 때 가장 긴 증가하는 부분 수열의 길이
dp = [1] * n # 처음에는 모두 1로 초기화 (자기 자신만 있는 경우)
# 각 i에 대해 이전 j들을 확인하며 dp 갱신
for i in range(n):
for j in range(i):
if A[j] < A[i]: # A[j] < A[i]일 때만 증가 수열이 가능함
dp[i] = max(dp[i], dp[j] + 1) # 기존 dp[i]와 dp[j]+1 중 큰 값으로 갱신
print(max(dp))내가 생각하는 것과 살짝 다른 방식이다. 배열에 초기값을 1로 초기화하고 직전값보다 현재값이 크면 최댓값에 +1을 한다. 만약에, 작으면 그대로 1일 것이다. 중간에 어떤 값이 나와도 값을 비교해서 가장 큰값을 유지하기 때문에 가장 긴 증가하는 부분 수열의 길이를 출력한다.
