3.예를들어, N=17일 때, 한 자릿수에서 사용할 수 있는 수는 0, 1, 2, ..., 17가지이다.
[입력]
1.첫 줄에는 A진법, B진법이 공백을 구분하여 주어진다. (2<=A,B<=30 이하의 자연수)
2.입력의 두 번째 줄에는 A진법으로 나타낸 숫자의 자리수의 개수 m(1<=m<=25)이 주어진다.
3.세 번째 줄에는 A진법을 이루고 있는 숫자 m개가 공백으로 구분되어 높은 자릿수부터 주어진다.
4.각 숫자는 0이상 A미만임이 보장되며, 0으로 시작되는 경우는 존재하지 않는다.
5.A진법 수를 10진법으로 변환하면, 양의 정수이며 2^20보다 작다.
[출력]
입력으로 주어진 A진법으로 나타낸 수를 B진법으로 변환하여 출력한다.
[예제 입력 1]
17 8
2
2 16
[예제 출력 1]
6 2
[문제 풀이]
1. a_nums를 10진수로 변환할 때, 각 자리를 변환하고 10진수로 합쳐야하는데, 다음과 같이 한 번에 처리하는 오류가 발생했다.
나는 아래 내 코드가 완벽하게, a_nums를 10진수로 바꿔준다고 생각했는데, 아닌가보다!
#a_nums에서 하나씩 꺼내서 x자리에 넣고, 그것은 A진수이니, 10진수로 바꿔주세요. 그리고 a_nums_10에 넣어주세요
a_nums_10=list(map(lambdax : int(x,A), a_nums))
문제에 주어져있었다. A진법을 이루고 있는 숫자 m개가 높은 자리수부터 주어진다는 것이므로 결국 하나의 숫자다.
위처럼 잘못 풀었던 첫 번째 코드
import sys
input=sys.stdin.readline
A, B = map(int,input().split())
m=int(input())
a_nums=input().split()
#1.10진수로 변환 시키는 과정 필요
###방법 : int(숫자,n진수)
#a_nums에서 하나씩 꺼내서 x자리에 넣고, 그것은 A진수이니, 10진수로 바꿔주세요. 그리고 a_nums_10에 넣어주세요
a_nums_10=list(map(lambda x : int(x,A), a_nums))
#2.10진수를 n진수로 변환시키는 함수 작성
def convert_to_base(num, base):
if num==0:
return 0
digits=[]
while num:
digits.append(int(num%base))
num=num//base
return ''.join(str(x) for x in digits[::-1])
#3.a_nums_10 차례대로 넣어서 반환
a_nums_b=list(map(lambda a : convert_to_base(a, B), a_nums_10))
print(*a_nums_b)
[정답코드]
import sys
input=sys.stdin.readline
A, B = map(int,input().split())
m=int(input())
a_nums = list(map(int, input().strip().split()))
#1.10진수로 변환 시키는 과정 필요
###방법 : int(숫자,n진수)
#a_nums에서 하나씩 꺼내서 x자리에 넣고, 그것은 A진수이니, 10진수로 바꿔주세요. 그리고 a_nums_10에 넣어주세요
# a_nums_10=list(map(lambda x : int(x,A), a_nums))
decimal_value=0
for num in a_nums:
decimal_value=decimal_value*A + num
#2.10진수를 n진수로 변환시키는 함수 작성
def convert_to_base(num, base):
if num==0:
return [0] #다른 return 값이 리스트이므로 [0]으로 통일
digits=[]
while num:
digits.append(int(num%base))
num=num//base
return digits[::-1]
#3.a_nums_10 차례대로 넣어서 반환
b_nums=convert_to_base(decimal_value, B)
print(' '.join(map(str,b_nums)))
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)
처음 중간값인 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))
문제 원리는 이해가 됐는데, 코드 이해가 덜 되었다. 따로 이해 필요하다. 유튜브에 강의가 존재하므로 확인해봐야겠다.
나는 그동안 python으로 알고리즘 공부를 해왔기 때문에, c++과 java만 가능한 수업이 다소 벅찼다. 그런데 대부분 c++로 알고리즘 공부를 한다고 하기도 해서, 이번주까지는 파이썬과 병행하고 다음주부터는 c++로 공부를 이어가보려고 한다.
1644 소수의 연속합
[문제정리]
-연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해보자.
-단, 같은 소수가 중복되어 사용되면 안된다.
[문제 푸는 방법]
아래의 두 가지 알고리즘을 적용해야한다.
1.에라토스테네스의 체 : 주어진 N까지의 소수를 미리 구한다.
2.투 포인터를 활용해, 연속된 소수의 합이 N이 되는지 확인하여 정답 구하기.
[1.에라토스테네스의체 코드 부분]
def sieve_of_eratosthenes(n):
is_prime=[True]*(n+1)
p=2
while(p*p<=n):
if is_prime[p]:
for i in range(p*p,n+1,p):
is_prime[i]=False
p+=1
return [p for p in range(2,n+1) if is_prime[p]]
n=int(input())
print(sieve_of_eratosthenes(n))
[2.투포인터 코드 부분]
result=0
start=0
end=0
while end<=len(prime_num):
temp=sum(prime_num[start:end])
if temp==n: #같으면 result 하나 카운트하고, end를 뒤로 한 칸 옮긴다.
result+=1
end+=1
elif temp<n: #합이 수 보다 작으면, end를 뒤로 한 칸 옮긴다.
end+=1
else: #합이 수보다 커지면, start를 뒤로 한 칸 옮긴다.
start+=1
[정답코드]
def sieve_of_eratosthenes(n):
is_prime=[True]*(n+1)
p=2
while(p*p<=n):
if is_prime[p]:
for i in range(p*p,n+1,p):
is_prime[i]=False
p+=1
return [p for p in range(2,n+1) if is_prime[p]]
n=int(input())
prime_num=sieve_of_eratosthenes(n)
result=start=end=0
while(end<=len(prime_num)):
temp=sum(prime_num[start:end])
if temp==n:
result+=1
end+=1
elif temp<n:
end+=1
else: #temp>n:
start+=1
print(result)
2960 에라토스테네스의 체
[문제]
에라토스네테스의체는, N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
1)2부터 N까지 모든 수를 적는다
2)지우지 않은 수 중 가장 작은 수를 선택하고, 이것을 P라 한다.
3)P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4)다 완료될 때까지 2번으로 돌아간다.
첫째 줄에 N K 형태로 주어졌을 때, N보다 작거나 같은 소수들 중 K번째 지우는 수를 구하는 프로그램을 작성하시오.
def sieve_of_eratosthenes(n):
delete_nums=[]
is_prime=[True]*(n+1)
p=2
while(p*p<=n):
if is_prime[p]:
delete_nums.append(p)
for i in range(p*p,n+1,p):
is_prime[i]=False
#지웠던 것을 또 지우는 과정이 발생한다. 따라서 중복되는 것은 추가하지 않게 하는 과정이 필요했다.
if i not in delete_nums:
delete_nums.append(i)
p+=1
#기존 코드는 전체를 우선 True로 만들어놓고, False 처리를 하여 자동으로 남겨지는 소수들이 카운트가 안됐다.
#그냥 남겨지는 애들도 추가하기 위해서 다음 코드를 넣었다.
for i in range(int(n**0.5)+1,len(is_prime)):
if is_prime[i]:
delete_nums.append(i)
return delete_nums
n,k=map(int,input().split())
delete_nums=sieve_of_eratosthenes(n)
print(delete_nums[k-1])
2725 보이는 점의 개수
[문제]
1.(0,0)에서 보이는 (x,y)의 개수를 구하려고 한다.(x,y>=0, 정수)
2.(0,0)에서 (x,y)가 보인다는 것은 (0,0)과 (x,y)를 연결하는 직선이 다른 점을 통과하지 않아야한다.
3.N이 주어졌을 때, 0<=x,y<=N 즉 (N,N)좌표평면에서 보이는 (x,y)좌표의 개수를 출력하시오.
4.단, (0,0)은 계산하지 않는다.
5.첫째 줄에 테스트케이스 개수C(1이상 1000이하)가 주어진다. 각 테스트케이스는 N(1이상 1000이하)로 주어지고, 한 줄에 하나씩 주어진다.
[시간초과코드]
def no_see_cnt(n):
slope=[]
#(0,0)~(n,n) 모든 경우의 수에 대하여
for i in range(n+1):#x좌표
for j in range(0,i+1):#y좌표
print(f'{i},{j}')
if i==0 and j==0:
slope.append(0)
print('slope에 0추가')
break
else:
temp=j/i
print(f'temp={temp}')
if temp not in slope:
print(f'temp={temp}를 추가합니다.')
slope.append(temp)
else: #temp in slope
print('이미 기울기가 있네요!')
pass
return len(slope)*2-1
#마지막에 0,0 은 포함하지 않지만 우리는 포함되어있으므로 -1 해줘야함.
C=int(input())
for _ in range(C):
N=int(input())
print(no_see_cnt(N))
시간을 무진장 초과하는 브루트포스 코드를 완성했다.
생각을 잘했기 때문에 스스로도 칭찬하지만, 기울기가 존재하면 범위 내에서 그 기울기인 애들을 미리 제거하는 방식을 취해야한다.
[정답코드]
DP와 최대공약수 개념 사용
def gcd(i, j):
if j == 0:
return i
return gcd(j, i % j)
dp = [0 for _ in range(1001)]
dp[1] = 3
for i in range(2, 1001):
cnt = 0
for j in range(1, i+1):
if i == j:
continue
if gcd(i, j) == 1:
cnt += 2
dp[i] = dp[i-1] + cnt
T = int(input())
for _ in range(T):
N = int(input())
print(dp[N])
(0,0)에서 보이지 않으려면 직선의 기울기가 달라야 한다.
이를 다르게 생각하면, (a,b)에서 a,b를 나누어 뜨리는 약수가 존재하는 경우, 둘이 서로소가 아닌 경우 볼 수 없는 자리다.
=> a,b가 서로소인 경우 볼 수 있는 자리다! 그리고 cnt+=2 인 이유는, 대칭으로 두 개씩 증가하기 때문이다!
4/2나 6/3은 약분하면 둘 다 기울기가 2로 똑같다. 따라서 분자와 분모의 최대공약수가 1인 값들을 찾아내면 된다.
좌표끼리 분수를 만들고 약분되면 그 좌표는 보일 수가 없다. 이전에 이미 같은 기울기가 나왔다는 뜻이기 때문이다. 따라서 분모와 분자의 최대공약수가 1일때만 더해나가면된다.