글쓰기
동료 학습에 기여하기가 쉽지 않다. 어제와 그저께를 CS:APP에 많은 시간을 할애했지만, 뚜렷한 성과가 없었다. 어디서부터 어디까지 모르는지 감도 안 잡힌다. 코어타임 때 동료들에게 알려줄 내용이 없다는게 무력하다. 차라리 일찌감치 포기하고 못 푼 알고리즘 문제라도 많이 풀었다면 마음은 한결 나았을 듯 하다. "밤을 새서 CS 교육자료를 만들어볼까" 고민도 많이 했다. 그러나 알고리즘 진도를 따라잡기 위해선 현재 '문제 양치기'가 최우선이라 이러지도, 저러지도 못 하고 있다.
동료학습에 어떻게 기여할 수 있을까? 나와 팀을 위한 선택이 어떤 것이 옳은 것인지 모르겠다. 힘들어하는 동료들을 위해 2일을 투자해서 CS 교육자료를 만드느냐, 혹은 못 푼 알고리즘 진도를 따라잡느냐.
To be or not to be.
알고리즘 문제 풀이
1931 회의실 배정
-
개요
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.
각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.
단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
회의의 시작시간과 끝나는 시간이 같을 수도 있다.
이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. -
입력
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14 -
출력
4
-
추상화
- 회의의 시작과 끝을 담을 이중 리스트를 작성합니다.
- 회의의 끝나는 시간순으로 정렬합니다.
- 첫 회의 시간에 끝 시간보다 크거나 같은 회의 시간의 시작(값)을 찾아 그 회의의 끝 시간으로 다시 갱신합니다.
-
구체화
이중 리스트를 작성하기 위해 빈 배열을 n*2로 선언합니다. 그리고 시작 시간과 끝 시간을 s,e로 나누어 담습니다.
회의를 끝 시간을 기준으로 정렬합니다. 그 후 첫 회의의 끝 시간부터 반복문을 통해 차례대로 끝 시간을 갱신합니다. -
코드
import sys
n = int(sys.stdin.readline())
# 회의의 시작, 끝 시간을 담을 이중 리스트
meet = [[0] * 2 for _ in range(n)] # 시작과 끝을 담기 위해 리스트 요소당 2개씩 선언
for i in range(n):
s, e = map(int, sys.stdin.readline().split())
meet[i][0] = s
meet[i][1] = e
# 요소의 1번째와 0번째를 위치를 바꾼 뒤 내림차순으로 끝나는 시간을 중심으로 정렬한다.
meet.sort(key = lambda x : (x[1], x[0]))
cnt = 1
end = meet[0][1]
# 끝나는 시간과 회의 시간의 시간을 갱신하며 카운트해준다.
for i in range(1, n): # 회의의 끝나는 시간을 탐색하기
if meet[i][0] >= end: # i번째 회의의 시작 시간이 앞의 회의 시간과 같거나 늦는 경우
cnt += 1
end = meet[i][1]
print(cnt)9251 LCS (Longest Common Subsequence)
LCS 알고리즘에 대해 잘 정리해주신 블로그 링크 첨부합니다. LCS 알고리즘이란?
- 개요
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
- 입력
ACAYKP
CAPCAK
- 출력
4
- 추상화
두 문자열을 입력받고 이중 리스트를 작성해서 문자가 겹치는 경우를 전의 값에 더하는 식으로 저장해줍니다.
- 구체화
LCS라는 이중 리스트를 만들어주고, 이중 for 문으로 완전 탐색하면 점화식을 구현합니다.
1. 두 글자가 같지 않다면, 이전의 값을 저장해야 하므로 현재의 요소 왼쪽과 바로 위의 요소를 비교하여 더 큰 값을 저장합니다.
2. 두 글자가 같다면 이전 문자와 연속하는 것이므로 현재 위치의 ↖쪽에 있는 값에 1을 더하여 저장합니다
- 코드
import sys
input = sys.stdin.readline
A = " " + input().strip()
B = " " + input().strip()
cnt = 0
LCS = [[0 for _ in range(len(B))] for _ in range(len(A))]
for i in range(1, len(A)):
for j in range(1, len(B)):
if A[i] == B[j]:
LCS[i][j] = LCS[i - 1][j - 1] + 1
if LCS[i][j] > cnt:
cnt = LCS[i][j]
else:
LCS[i][j] = 0
print(cnt)11053 가장 긴 증가하는 부분 수열
-
개요
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은
A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. -
입력
6
10 20 10 30 20 50 -
출력
4
-
추상화
값을 입력받아 리스트에 저장합니다.
리스트의 값을 비교하여 올린 카운트 값을 DP에 갱신합니다. -
구체화
DP를 활용해 2중 반복문을 만듭니다. 각 인덱스마다 현재(i)의 요소 값이 그 전까지(j)의 요소값보다 크다면, 부분 수열은 증가하는 것이므로 카운트 값을 올립니다. 카운트 값은 현재(i) 요소의 전(j) 값에 1을 더한 값과 현재 값 중 가장 큰 값을 저장합니다.
-
구현
import sys
input = sys.stdin.readline
n = int(input())
numbers = list(map(int, input().split()))
dp = [1] * n
for i in range(1, n):
for j in range(i):
if numbers[i] > numbers[j]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))