1.4일차 복습
최대공약수 : 유클리드 호재법
동치 역원 구하기 : 확장 유클리드 호제법(?)
소수구하기 : 나눠서 구한다(제곱근 지우기), 에라토스테네스의 체
오일러 피 함수 : 1~N-1까지
경우의 수 : 순열, 조합(조합은 동적 계획법으로 해결)
2. 다리놓기 1010
[문제]
1.도시를 동서로 나누는 큰 일직선 모양의 강이 흐르고 있다. 동서를 잇는 적합한 곳(사이트)에 다리를 짓고자 한다.
2.서쪽에는 N개의 사이트, 동쪽에는 M개의 사이트가 있다.(N<=M)
3.한 사이트에는 한 개의 다리만 연결 가능하며, 서쪽 사이트 개수만큼 다리를 지을 수 있는 경우의 수를 구하여라.
=>결국 오른쪽 M개의 점 중에서 N개를 선택하면, 순서대로 왼쪽에 연결된다고 생각할 수 있다.
[풀이]
지난번에 조합을 한 번 쭉 정리한 적이 있다. 하지만 암기하지는 않았었다. 그래서 기억이 나지 않는다.
정리한 노트를 보고 암기를 오늘 제대로 해야겠다.
암기하기 전에 예상되는 풀이 방법으로는,
-일반식을 새롭게 세웠었다.
-일반식을 새로 가져오는 것 외에는, 라이브러리를 사용하는 방법과, 메모이제이션 방법이 있었던 것 같다.
[정답코드]
def comb(n,k):
if k > n:
return 0
if k==0 or n==k:
return 1
#k가 n/2보다 큰 경우, nCk=nC(n-k)와 같음. 더 작은 수로 바꿔주는 과정
if k > n/2 :
k = n-k
result=1
for r in range(k): #r-1까지 돌 것임
result = result * (n-r) // (r+1)
return result
c=int(input())
for _ in range(c):
r, n = map(int, input().split())
print(comb(n,r))
[팁]
가장 큰 수인 M도 한 번 찍어봐야한다. overflow 방지를 위해서!
최대 크기가 10만으로 주어지면, nlogn 알고리즘을 사용하면 된다.
3. 순열의 순서 1722(골드5)
[문제]
1.임의의 순열(N!)은 정렬할 수 있다. 예를 들어 N=3인 경우, 6가지 경우의 수가 있다. 6가지 경우의 수를 나열하면 앞에서부터 작은 것이 순서상 앞선다.
2.N이 주어지면 , 두 가지 소문제 중 하나를 풀어야한다.
-문제 번호 1) K를 입력받고, N!에서의 K번째 순열을 구한다.
-문제 번호 2) 임의의 순열 N개를 입력받고, 이 순열이 몇 번째 순열인지를 출력하기.
4.사전 1256(골드2)
[문제]
-사전에 수록되어있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져있다. 다른 문자는 없고, 알파벳 순서대로 수록되어있다.
-규완이는 사전을 완성했고, 동호는 사전을 완성하지 못했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에 문자열 하나만 찾을 수 있다.
-N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.
-입력 : 첫째 줄에 세 정수 N,M,K가 주어진다.
-출력 : 규완이의 사전에서 K 번째 문자열을 출력한다. 사전에 등록된 문자열 개수가 K보다 작으면 -1을 출력한다.
[풀이]
-경우의 수만 따져가며, 앞에서부터 문자열을 채우는 것이 핵심이다.
-n,m개의 문자로 구성할 수 있는 문자열의 수는 math.comb(n+m,n)이다. a의 자리를 결정하면, 나머지를 z로 채우기만 하면 된다.
-n,m에 대해 (n-1)개의 a와, m개의 z로 만들 수 있는 문자열의 수인 math.comb(n+m-1,n-1)보다 k의 값이 크다면, 맨 앞
유독 이해가 안되는 문제...
from math import comb as c
a,b,i=map(int,input().split())
s=["z"]*(a+b)
if c(a+b,a)<i:
print(-1)
else:
ans=""
#과정을 반복하여 n,m 둘 중 하나가 0이되거나 k의 값이 0이될 때까지 반복하며 문자열을 채워나가고, 남은 문자가 있다면 그 개수만큼 뒤에 붙여준다.
while i and (a and b):
if i > c(a+b-1,a-1): #n-1개의 a와 m개의 z로 만들 수 있는 수 c(a+b-1,a-1)보다 k가 크면, 맨 앞 문자는 a이므로
ans+="z"
i-=c(a+b-1,a-1)
b-=1
else:
ans+="a"
a-=1
print(ans+"a"*a+"z"*b)
사전 문제랑 순열의 순서 문제 이해가 잘 안됨. 다시 봐야함 ...
직접 시간 들여서 풀어봐야하는 듯.
5. 6549 히스토그램에서 가장 큰 직사각형
[풀이]
위의 블로그에 설명이 상세하게 적혀있어서, 참고하며 공부를 해보려고 한다.
1) 분할 정복 풀이 : 중앙값을 기준으로, 양쪽으로 넓혀가며 최댓값을 찾는 작업.
처음 중간값인 8에서 시작하고, 왼쪽과 오른쪽 중 더 높이가 높은쪽으로 확장한다. 그리고 이때의 넓이값도 적어둔다.
또 해당 직사각형과 맞닿아있는 히스토그램 중 더 높은 쪽으로 확장한다. 확장하고나서 넓이를 갱신해준다.
최종적으로 분할 기준을 포함하는 최댓값, 왼쪽 범위의 최댓값, 오른쪽 범위의 최댓값을 모두 구하고, 이 셋을 비교하여 가장 큰 값을 최댓값으로 잡아준다.
어려웠지만 코드 이해 안되는 부분은 손으로 쓰고, 직접 값 넣어서 생각하니 이해가 되었다. 까먹기 전에 복습 혹은 영상을 찍어두면 도움이 될 것 같다.
import sys
input = sys.stdin.readline
res=[]
def divide_and_conquer(histogram, start, end):
#end=start 같으면, 복잡한 과정 거칠 것 없이 그냥 histogram[end] 또는 histogram[start]다.
if end == start:
return histogram[end]
#만약 end와 start가 바로 한 칸 차이면(붙어 있으면)
elif end - start == 1:
#게다가 end보다, start가 더 높이가 높을 경우
if histogram[end] < histogram[start]:
#복잡한 과정 할 것 없이,end값에 두 배를 한 것과, start 값 중 더 큰 값 비교
return max(2*histogram[end], histogram[start])
else:
#start 값에 두 배를 한 것과, end 값 중 더 큰 값 비교
return max(2*histogram[start], histogram[end])
mid = ( start + end ) //2
left_area = divide_and_conquer(histogram, start, mid)
right_area = divide_and_conquer(histogram, mid+1, end)
left=mid-1
right=mid+1
#mid_area : 기존 넓이를 기록할 변수 초기화
mid_area = histogram[mid]
#now_height : 현재 높이를 기록할 변수 초기화. 시작은 중간값
now_height = histogram[mid]
while start <= left and right <= end:
#왼쪽과 오른쪽 중 오른쪽 히스토그램 높이가 더 높으면
if histogram[left] < histogram[right]:
#'오른쪽 히스토그램 높이' 보다, '현재 높이'가 더 높으므로
if histogram[right] < now_height:
#'현재 높이'를 더 낮은 '오른쪽 히스토그램 높이'로 설정한다.
now_height = histogram[right]
#그리고 현재까지의 넓이(mid_area)와, 새롭게 지정된 높이(now_height)에 대한 넓이를 비교하여
#더 높은 것을 새로운 mid_area로 지정한다.
mid_area = max(mid_area, now_height * (right-left))
#그리고 오른쪽으로 한 칸 범위를 높인다.
right +=1
#왼쪽과 오른쪽 중 왼쪽 히스토그램 높이가 더 높으면
else:
if histogram[left] < now_height:
now_height = histogram[left]
mid_area = max(mid_area, now_height*(right - left))
left -= 1
#right는 범위를 벗어났고, 조건이 없어졌다. 왼쪽으로 확장할 공간만 남은 상황.
while start <= left:
if histogram[left] < now_height:
now_height = histogram[left]
mid_area = max(mid_area, now_height * ( right - left ))
left -=1
while right <= end:
if histogram[right] < now_height:
now_height = histogram[right]
mid_area = max(mid_area, now_height * ( right - left))
right+=1
return max(left_area, right_area, mid_area)
res=[]
while True:
#직사각형의 수, 직사각형의 높이들 주어짐 ex) 7 2 1 4 5 1 3 3
histogram = list(map(int, input().split()))
n = histogram[0]
#입력 마지막 시에 종료 조건
if n ==0:
break
#1부터 넘겨주어, 0번째인 값은 해당되지 않도록 함.
res.append(divide_and_conquer(histogram, 1, n))
for i in res:
print(i)
6. 가장 긴 증가하는 부분 수열 11053
[문제]
가장 긴 증가하는 부분 수열의 길이를 구하는 문제.
예를 들어 [10, 20, 10, 30, 20, 50]이 주어지면,
[10, 20, 10, 30, 20, 50]
[팁]
-최대수가 1,000으로 주어지면, n^2으로 해결할 수 있다.
-최장증가부분수열(LIS)
-앞에서부터 하나씩 확인한다.
-나보다 더 앞에 작은게 있어야 붙을 수 있음.
-원리를 계산해봐도 n^2 알고리즘이라는 것을 파악할 수 있음.
[풀이]
dp[i] = A[i]를 마지막 원소로 가지는 부분 수열의 최대 길이.
=> A[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는,
A[i]가 추가되기 전 증가부분수열의 마지막 값이, A[i]보다 작은 값이어야한다.
A[i]를 마지막 값으로 가지는 '가장 긴' 증가부분수열의 길이는,
A[i]가 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다.
n=int(input())
arr = list(map(int, input().split()))
#i가 0일 때 증가하는 최대 부분 수열의 길이는 1이기 때문에, 테이블을 우선 전부 1로 초기화해줌
d = [1]*n
for i in range(1, n): #1부터 n-1번 인덱스까지의 모든 i에 대하여
for j in range(i): #i보다 작은 j (0부터 i-1까지 = i보다 작은 것 모두)
if arr[j] < arr[i]: #j의 원소가 i의 원소보다 작은 값이 존재하면!, 즉, 부분적으로 증가한다면
d[i] = max(d[i], d[j]+1) #i에서의 최적의 해를 갱신해준다.
print(max(d))
문제 원리는 이해가 됐는데, 코드 이해가 덜 되었다. 따로 이해 필요하다. 유튜브에 강의가 존재하므로 확인해봐야겠다.
뭐야 나무위키에 엄청 상세하게 정리가 잘되어있다. 공부해보자.
최장 증가 부분 수열
최장 증가 부분 수열 문제는 동적 계획법 으로 풀 수 있는 유명한 알고리즘 문제이다. 정의 어떤 임의의 수열이 주
namu.wiki
7. 가장 긴 증가하는 부분 수열2
이 문제 풀이는 총 세 가지가 존재한다.
1)동적계획법(N^2) = 가장 긴 증가하는 부분 수열1
2)인덱스 트리로 계산 가능 : 이분 탐색보다 코드가 조금 복잡하다.
3)근데 이분탐색이 더 빠르게 코드 짜짐.(강사님 자료에서 설명해주셨던 것. 근데 내용 이해 필요)
1 5
2 3
앞에 다음과 같은 예시가 있다. 5뒤에 붙을 수 있는 애는 3뒤에도 붙을 수 있기 때문에, 당연히 2 3을 선택하면 된다.
'코딩테스트 준비' 카테고리의 다른 글
| 삼성SDS 알고리즘 특강 4일차 : 정수론 (0) | 2024.08.01 |
|---|---|
| 2024 하반기 삼성SDS 알고리즘 특강 2일차 (0) | 2024.07.30 |