백준 | 9095 1, 2, 3 더하기 Swift - DP

다이나믹 프로그래밍이란? 다이나믹 프로그래밍, 동적 계획법이라고 불리는 알고리즘은 하나의 커다란 문제를 작은 문제들로 나누어 값을 구하는 방법이다. 점화식을 구하고 나면 쉽게 풀 수 있지만 이런 사고방식에는 연습이 필요하다. 이 문제에서는 1, 2, 3만을 이용해 숫자를 나타낼 때, 그 경우의 수를 구해야 한다. 작은 것부터 차례대로 생각해보자. n = 1 1 1개 n = 2 1+1 2 2개 n = 3 1+1+1 1+2 2+1 3 4개 n = 4 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 7개 n=1일 때는 1, n=2일 때는 2, n=3일 때는 4 그리고 n=4일 때는 7개의 경우의 수가 나온다. 이 때 n=4를 자세히 살펴보자. 1+3이라는 큰 틀을 구할 때, 오른쪽 피연산자..

• format_list_bulleted 공부하자!/알고리즘
• · 2023. 7. 18.
• textsms

백준 1021 파이썬 회전하는 큐

회전하는 큐 왼쪽으로 돌릴 때는 index가 0인 원소를 뒤에 넣고 앞을 삭제, 오른쪽으로 돌릴 때는 index가 -1인 원소를 앞에 넣고 뒤를 삭제하면 된다 import sys N, M = map(int, sys.stdin.readline().split()) K = list(map(int, sys.stdin.readline().split())) A = [i for i in range(1, N + 1)] cnt = 0 for i in range(M): A_len = len(A) A_index = A.index(K[i]) if A_index < A_len - A_index: while True: if A[0] == K[i] : del A[0] break else : A.append(A[0]) del A[0..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 5. 14.
• textsms

백준 1920 파이썬 수 찾기

시간초과 났다가 고친 문제,, 첫 리스트를 set으로 바꿔주면 된다. (어차피 중복도 없으니까) import sys N = int(sys.stdin.readline()) A = set(map(int, sys.stdin.readline().split())) # list로 하면 시간초과 남 M = int(sys.stdin.readline()) B = list(map(int, sys.stdin.readline().split())) for i in B: if i in A: print(1) else: print(0)

• format_list_bulleted 카테고리 없음
• · 2021. 2. 24.
• textsms

백준 1874 파이썬 스택 수열

처음엔 문제를 아예 이해 못했다.. 문제를 해석해보자면 입력된 수열 X = [4, 3, 6, 8, 7, 5, 2, 1] 이 있고 스택 Y에 1부터 순서대로 넣었다가 뒤에서부터 빼서 X 수열을 만들 수 있는지를 물어보는 거였다 push 한 번 하면 Y = [1], 두 번 하면 Y = [1, 2] 처럼 되고 출력된 예시처럼 push를 4번 한 이후에는 Y = [1, 2, 3, 4]가 되고, 다섯번째 출력처럼 pop을 하면 X[0]과 같은 값이 나온다 이런 식으로 push, pop 하면서 X[N]까지 하면 되는 것,, import sys N = int(sys.stdin.readline()) X = [] # 입력 받아서 리스트에 저장 for i in range(N): X.append(int(sys.stdin.r..

• format_list_bulleted 카테고리 없음
• · 2021. 2. 24.
• textsms

백준 1085 파이썬 직사각형에서 탈출

직사각형 w x h 내부의 점(x, y)에서 밖으로 탈출하는 최소 거리를 구하는 문제 w - x , h - y 중 작은 걸 고르면 된다 단!! 그 거리보다 x, y가 0으로 가는게 더 빠를 수도 있으니 총 네 가지 중 가장 작은 것 출력 import sys x, y, w, h = map(int, sys.stdin.readline().split()) print(min((w-x), (h-y), x, y))

• format_list_bulleted 카테고리 없음
• · 2021. 2. 23.
• textsms

백준 1436 파이썬 영화감독 숌

언뜻 보기엔 진짜 아,, 이거 경우의 수 다 구해야하는건가 ㅜㅜ 10,000개를 언제 다 구하지 ㅠ 싶었는데 생각해보니까 그냥 1씩 더하면 될 것 같았다..!! N = int(input()) S = [] count = 666 # 첫번재 수는 알고있으니까,, while len(S) != N : # 구해야하는 수 까지만 X = list(str(count)) for i in range(len(X)-2): if X[i] == X[i+1] == X[i+2] == '6': # 세 수 연속으로 6인지 확인 if count not in S : # 중복 아닌지 확인 S.append(count) # 1씩 더해주기 count += 1 print(S[N-1]) 설마설마 했는데 진짜 됐다 ㅋㅋ 시간 초과 날 줄 알았는데 다른 ..

• format_list_bulleted 카테고리 없음
• · 2021. 2. 21.
• textsms