viamemine

📍 다이나믹 프로그래밍(동적 계획법) '한 번 계산한 문제는 다시 계산하지 않도록 한다'는 알고리즘으로,메모리 공간을 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법이다.  이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.구현은 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성된다.    💥 다이나믹 프로그래밍의 '동적' 의미는, 자료구조에서 사용하는 동적 할당(Dynamic Allocation):프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법과는 다르다. 별다른 의미 없이 사용된 단어이다.   📍 다이나믹 프로그래밍의 조건 1. 최적 부분 구조(Optimal Substructure):큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답..

문제 올바른 풀이 import sys T = int(input()) for i in range(T): N, M = map(int, sys.stdin.readline().split()) queue = list(sys.stdin.readline().split()) idx = list(range(len(queue))) # 인덱스 처리 idx[M] = 'target' order = 0 # 순서 while True: if queue[0] == max(queue): # 첫번째 값이 가장 크면 order+1 order += 1 if idx[0] == 'target': # 첫번쨰 값이 target이면 print(order) # order 출력 break else: # 첫번째 값이 target이 아니면 queue.pop..

문제 잘못된 풀이 (런타임 에러) 런타임 에러 command = ['(', ')', '[', ']'] while True: string = input() if string == '.': quit() for i in string: if i in command: if i == '(': check1 = 1 elif i == ')': if check2 == 1: check1 = 1 else: check1 = 0 elif i == '[': check2 = 1 elif i == ']': check2 = 0 if check1 == 0 and check2 == 0: print("yes") else: print("no") 해당 문제는 문자열을 다루는 문제이다. 처음에는 해당 문제를 check1, check2 변수를 통해..

문제 잘못된 풀이 import sys N = int(sys.stdin.readline()) num_list = [i for i in range(1,N+1)] # print(num_list) while len(num_list) > 1: num_list.pop(0) # 맨 위에 있는 원소 pop number = num_list.pop(0) # 두번째 있는 원소 pop하고 마지막에 붙이기 num_list.append(number) if len(num_list) == 1: print(num_list[0]) 나는 해당 문제를 queue의 자료구조를 생각하며 풀었다. 문제는 쉽게 풀 수 있었지만, 결과적으로 시간초과로 문제풀이에 실패하였다. 올바른 풀이 import sys from collections import..

문제 올바른 풀이 import sys N = int(input()) Deque = [] for i in range(N): command = sys.stdin.readline().split() if command[0] == 'push_back': # 뒤에 넣음 Deque.append(command[1]) elif command[0] == 'push_front': # 앞에 넣음 Deque.insert(0, command[1]) elif command[0] == 'front': if len(Deque) == 0: print('-1') else: print(Deque[0]) elif command[0] == 'back': if len(Deque) == 0: print('-1') else: print(Deque[..

문제 올바른 풀이 import sys N = int(input()) queue = [] for i in range(N): command = sys.stdin.readline().split() if command[0] == 'push': queue.append(command[1]) elif command[0] == 'front': # 가장 앞 원소 출력 if len(queue) == 0: print('-1') else: print(queue[0]) elif command[0] == 'back': # 가장 뒷 원소 출력 if len(queue) == 0: print('-1') else: print(queue[len(queue)-1]) elif command[0] == 'size': print(len(queu..

문제 올바른 풀이 import sys N = int(input()) stack = [] for i in range(N): command = sys.stdin.readline().split() if command[0] == 'push': # stack에 입력 stack.append(command[1]) elif command[0] == 'top': if len(stack) == 0: # stack이 비어있으면 -1 출력 print('-1') else: print(stack[len(stack)-1]) elif command[0] == 'size': print(len(stack)) elif command[0] == 'empty': if len(stack) == 0: print('1') else: print('..

문제 올바른 풀이 N, M = map(int, input().split()) board = [] # 전체 보드를 나타내기 위함 result = [] # 결과값을 나타내기 위함 for i in range(N): board.append(input()) # 칠할 체스는 8*8 for i in range(N-7): # i,j는 체스판의 칠할 부분을 찾는 시작점 for j in range(M-7): black_first = 0 # 시작 지점이 검은색일 경우 white_first = 0 # 시작 지점이 흰색일 경우 # 자른 체스판을 처음부터 검사 for a in range(i, i+8): for b in range(j, j+8): if (a+b) % 2 == 0: # 어느색을 칠할지 결정 if board[a][b]..

문제 잘못된 풀이 import sys # 시간초과 N = int(input()) num_list = list(map(int, sys.stdin.readline().split())) M = int(input()) check_list = list(map(int, sys.stdin.readline().split())) for i in check_list: if i in num_list: print("1") else: print("0") 해당 문제는 주어진 수가 리스트 안에 있는지 여부를 판단하는 문제이다. 나는 문제를 딱 보자마자 바로 in을 써서 푸는 방법을 떠올렸고, 실제로 in을 사용해서 문제를 해결하면 쉽게 풀리는 문제이다. 하지만, 오늘도 시간초과 ... 문제를 보고 바로 떠오르는 해결방법이라도, 코..

문제 잘못된 풀이 import sys T = int(input()) cnt_0 = 0; cnt_1 = 0 def fibo(n): global cnt_0 global cnt_1 if n == 0: cnt_0 += 1 return 0 elif n == 1: cnt_1 += 1 return 1 else: return fibo(n-1) + fibo(n-2) for i in range(T): n = int(sys.stdin.readline()) result = fibo(n) print(cnt_0, cnt_1) cnt_0 = 0; cnt_1 = 0 나는 피보나치를 문제의 설명처럼 재귀(recursive)로 풀고자 하였다. 0과 1을 count하는 변수를 global로 선언하고 fibo() 함수에서 구하는 로직으로 ..