싄나게 백준 문제 풀기🧠
수학
20. #2869 달팽이는 올라가고 싶다
import math #수학 관련 함수를 사용할수 있다 (사인,코사인,제곱근 등 )
a,b,v= map(int,input().split())
day= math.ceil((v-a)/(a-b))+1 #ceil함수는 소수 올림 내릴려면 floor
print(day)- #1978 소수찾기-어려움..
a= int(input())#주어진N개
num = list(map(int, input().split()))
sosu = 0
for i in num:
error = 0
if i >1:
for _ in range(2, i):
if i % _ ==0:
error += 1
if error == 0:
sosu += 1
print(a)import math
#함수지정
def primenumber(x):
if x <= 1: #1은 포함 안시킴
return False
for i in range(2, int(math.sqrt(x)+1)): #제곱근을 구해
if x %i == 0:#제곱근 나뉘면 안댐
return False
return True
a= int(input())
num=list(map(int,input().split())) #수를 받고
count =0 #숫자 카운트
for i in range(a):
if primenumber(num[i]) == True: #소수면 true
count += 1 #더함
print(count)
- #9020 골드바흐의 추측 //시간초과....
import math
#소수인 숫자를 찾는 함수
def primenumber(x):
if x==1:
return False
for i in range(2,int(math.sqrt(x)+1) ):
if x%i ==0:
return False
return True
#골드 파티션을 찾는 함수?
def goldnum(x): #우리가 찾을수
result=[]
for i in range(2, x//2+1): #2부터 x/2까지
if primenumber(i) and primenumber(x-i): #i+(i-1) = x
if not result:
result.append(i)
result.append(x-i)
else:
if result[1]-result[0]> x-2*i:
result[0]=i
result[1]= x-i
return result
t= int(input())
for i in range(t):
n= int(input())
ans= goldnum(n)
print(*ans)- #1065 한수
def hansu(num):
hansu_cnt =0
for i in range(1, num+1):
num_list= list(map(int,str(i)))
if i <100:
hansu_cnt += 1
elif num_list[0]-num_list[1] == num_list[1]-num_list[2]:
hansu_cnt +=1
return hansu_cnt
num=int(input())
print(hansu(num))- #2628 종이자르기
#종이자르기
#두수를 입력
#가로세로 지정
#자르는 횟수, 세로가 1 가로가 0 세로는 r
#빼서 최대 길이 구하기
#저장
# row[1]-row[0]
r,c = map(int,input().split())
row= [0,r]
column=[0,c]
for i in range(int(input())):
r_or_c,linenumber = map(int,input().split())
if r_or_c == 1:
row.append(linenumber)
else:
column.append(linenumber)
row.sort()
column.sort()
subtracted_r=[]
subtracted_c=[]
for i in range(len(row)-1):
subtracted_r.append(row[i+1]-row[i])
for i in range(len(column)-1):
subtracted_c.append(column[i+1]-column[i])
print(max(subtracted_c)* max (subtracted_r))
- #10827 팩토리얼
#양의 정수 n의 팩토리얼 구하기
def factorial(n: int) -> int:
if n>0:
return n*factorial(n-1)
else:
return 1
if __name__ == '__main__':
n= int(input())
print(f'{factorial(n)}')- #17478 재귀함수가 뭔가요?(자기 자신을 호출하는 함수)
math.gcd(a,b) 는 a,b,의 최대 공약수를 반환
def says(i,n) :
print("____"*i +'"재귀함수가 뭔가요?"')
if i==n:
print("____"*i + '"재귀함수는 자기 자신을 호출하는 함수라네"')
else:
print("____"*i + '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
print("____"*i + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.")
print("____"*i + '그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
says(i+1, n)
print("____"*i + "라고 답변하였지.")
if __name__ == '__main__':
n= int(input())
print(f'어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.')
says(0,n)- #5568 카드놓기
import itertools
n= int(input())
k= int(input())
card=[input().rstrip() for _ in range(n)]
res= set() #정렬
for per in itertools.permutations(card, k):#순열
res.add(''.join(per)) #딱히 필요 없는듯
print(len(res)) #개수 - #1914 하노이탑
#하노이탑
#원반 no개를 x기둥에서 y기둥으로 옮김
def move(n: int, x: int ,y:int) -> None:
if n>1:
move(n-1, x,6-x-y )
print(f'{x} {y}')
if n>1:
move(n-1,6-x-y,y)
n= int(input())
print (2**n-1)
if n<=20:
move(n,1,3)- #9663 no_queen
//백트래킹
사용 알고리즘: dfs, 백트래킹
퀸은 가로, 세로, 대각선 8방향으로 원하는 만큼 움직일 수 있음
dfs와 백트래킹 개념을 사용하여 퀸을 놓을 수 있는 모든 경우에 대해 브루트포스 탐색
이때 N*N의 체스판에 N개의 퀸을 놓으려고 하는 경우, 같은 줄에는 두 개의 퀸이 있을 수 없으므로, 결국 한 줄에는 무조건 하나의 퀸만 존재할 수 있다.
따라서 재귀 종료 조건은 두가지이다
어느 줄이라도 퀸을 놓을 수 없는 줄이 존재하면 바로 종료
마지막 줄에 다다르면 종료
또한 퀸을 놓을 수 없는 칸을 체크할 때, 8개의 모든 방향에 대해서 체크할 필요 없이 아래쪽, 왼쪽 아래 대각선, 오른쪽 아래 대각선의 3 방향만 체크해주면 된다.
오른쪽, 왼쪽 가로방향을 체크해주지 않는 이유는 어차피 한 줄에 하나의 퀸만 들어가도록 코드를 작성하였기때문이다.
n = int(input())
result = 0
# 퀸을 놓은 후 그 이후의 줄에 대해서만 불가능한 칸 체크
def visit(x, y, in_visited):
tmp_visited = [visi[:] for visi in in_visited]
for i in range(1, n-x):
tmp_visited[x+i][y] = True # 아래 방향 체크
if 0 <= y-i < n:
tmp_visited[x+i][y-i] = True # 왼쪽 아래 대각선 체크
if 0 <= y+i < n:
tmp_visited[x+i][y+i] = True # 오른쪽 아래 대각선 체크
return tmp_visited
def recursion(q, _visited): # q번째 줄에 퀸을 둘 수 있는 경우들을 확인하는 재귀함수
global result
# 한 줄에 퀸이 하나씩 들어가야 함
# 한 줄 전체가 불가능한 경우 아예 n개의 퀸을 모두 놓을 수 없으므로 재귀 종료
for idx in range(q, n):
if sum(_visited[idx]) == n:
return 0
# 마지막 줄에 도달한 경우 가능한 모든 경우를 세고 재귀 종료
if q == (n-1):
result += n - sum(_visited[q])
return 0
for i in range(n):
if not _visited[q][i]: # 퀸을 둘 수 있는 경우
tmp = visit(q, i, _visited) # 퀸을 뒀을 때 불가능한 칸들 체크
recursion(q+1, tmp) # 그 다음 줄에 대해 재귀 호출
# 재귀호출 종료 후 퀸을 둘 수 있는 다른 경우에 대해 체크
visited = [[False for _ in range(n)] for _ in range(n)]
recursion(0, visited) # 0번째 줄부터 탐색 시작
print(result)
- #1074 z
코드를 입력하세요정렬
내부정렬- 정렬할 모든 데이터를 하나의 배열에 저장 할 수 있능 경우
외부정렬- 데이터가 많을때
- #2750 수 정렬하기
x= int(input()) #주어질 수의 개수
num_list =[] #숫자들의 리스트를 만든다
for i in range(x): #x만큼 반복해서 num_list만듬
num_list.append(int(input()))
num_list1= sorted(num_list) #sorted로 정렬
for i in range(len(num_list)):
print(num_list1[i]) #하나씩 출력- #2751 수 정렬하기 2
import sys
x= int(input())
#주어질 수의 개수
num_list =[] #숫자들의 리스트를 만든다
for i in range(x): #x만큼 반복해서 num_list만듬
num_list.append(int(sys.stdin.readline())) #여러줄을 입력받을때 시간을 줄일수 있다.
num_list1= sorted(num_list) #sorted로 정렬
for i in range(len(num_list)):
print(num_list1[i]) #하나씩 출력- #10989 수 정렬하기 3
1/메모리초과/
from typing import MutableSequence
def bubble_sort(a: MutableSequence) -> None:
n= len(a)
for i in range(n-1):
for j in range(n-1,i,-1):
if a[j-1]> a[j]:
a[j-1], a[j]= a[j],a[j-1]
if __name__=='__main__':
num=int(input())
x=[None]*num
for i in range(num):
x[i]=int(input())
bubble_sort(x)
for i in range(num):
print(f'{x[i]}')
# #계수정렬 사용
# import sys
# input= sys.stdin.readline
# num= int(input())
# arr = [0]*10001 #입력받을수있는 만개 배열
# for i in range(num):
# a= int(input())
# arr[a-1] +=1 #입력받을때마다 +1해줌 담음
# for i in range(10001):
# if arr[i] != 0 : #0이아니라면 해당숫자 출력
# for j in range(arr[i]): #자동정렬된다?
# print(i+1)- #1181 단어 정렬
import sys
n= int(input())
#주어질 수의 개수
str_list =[] #글자들의 리스트를 만든다
for i in range(n): #x만큼 반복해서 str_list만듬
str_list.append(str(sys.stdin.readline().rstrip()))
#여러줄을 입력받을때 시간을 줄일수 있다. rstrip사용해서 뒤에를 제거
str_list= list(set(str_list))#set이 중복을 제거
str_list.sort()#sort를 사용해서 사전순으로 정렬해줌
str_list.sort(key=len) #길이순으로 정렬 len이 길이 key는 어떤 함수로 정렬할지
for i in str_list: # 배열의 요소를 하나하나 출력하기
print(i) #하나씩 출력완전 탐색
35. #2309 일곱 난쟁이
import sys
from itertools import combinations
n= 9
num=[int(input()) for _ in range (n)]
for i in combinations(num,7): #9개중에 7개 조합을 뽑아서
if sum(i) == 100: #더한것이 100이면
answer = list(i) #list에 추가
answer.sort()#뽑은 list 정렬
print(*answer , sep='\n') # *와 '\n'을 사용하면 아래로 출력
- #2798 블랙잭
from itertools import combinations
n,m= map(int,input().split())
num= list(map(int,input().split()))
result_num=0
for cards in combinations(num,3):
temp_sum= sum(cards)
if result_num< temp_sum<= m:
result_num = temp_sum
print (result_num)- #10819 차이를 최대로
맨뒤 꺼내기..
import sys
from itertools import permutations
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
cases = list(permutations(a))
print(cases)
answer = 0
for cases in cases:
check = 0
for i in range(n-1):
check += abs(cases[i] - cases[i+1])
answer = max(check,answer)
print(answer)- #10971 외판원 순회2
//이해를 하나도 못했네...
#숫자가 n부터 주어지며 0부터 n-1까지 정수가 담긴 리스트를 하나 만들어준다
#그 리스트를 permutation 함수를 이용하여 경우의 수를 계산해주고, for문을 이용해 어떤 경로가 작은지 비교
#for문 값이 0이 아니면 data에 있는 값을 ans에 더해주고 마지막에는 도착점에서 출발점까지 거리도 0이 아닐경우에 더해서
#총경로 이동 값을 return해준다
import sys
from itertools import permutations
input= sys.stdin.readline
n= int(input())
data= [list(map(int,input().split())) for _ in range(n)]
n_num =[i for i in range(n)]
def function(List):
ans=0
for i in range(n-1):
if data[List[i]][List[i+1]] != 0:
ans += data [List[i]][List[i+1]]
else:
return False
if data[List[-1]][List[0]] == 0:
return False
else:
ans += data[List[-1]][List[0]]
return ans
ans = 987654321
for List in permutations(n_num):
result = function(List)
if result != False:
if ans > result:
ans= result
print(ans)- #14888 연산자 끼워넣기
<알게된거>
1.set은 중복을 없애준다
2.sys.stdin.readline() 여러줄 입력할때 시간을 줄여준다
3.sorted 는 정렬
4.rstrip 뒤에꺼 없앰
5.append( ) 맨끝에 추가
6.itertools를 사용
7.abs(x) 절대값
8. 모르겠다 그냥
멋진 개발자가 될거야 :)