728x90 Programming Language Training/Python73 Baekjoon Training #12865 #12865 평범한 배낭 이 문제는 Knapsack Problem(냅색 문제)이다. 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제를 말한다. 이때, 짐을 쪼개서 넣을 수 있는 경우와 쪼개지 못하고 넣는 경우 두가지가 존재한다. 쪼갤 수 있는 경우 분할가능 배낭문제(Fractional Knapsack Problem), 쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem)이라 부른다. 위 문제는 쪼갤 수 없는 0-1 Knapsack의 경우이고 이는 동적계획법(Dynamic Programming)으로 풀 수 있다. 알고리즘 1) x축엔 가방 1~K 까지의 무게, y축은 물건 N개 개수 만큼.. 2023. 8. 6. Baekjoon Training #10828 #10828 스택 나의 오답 코드 #스택 import sys input = sys.stdin.readline n=int(input()) num_list=[] for i in range(n): command = input() if command.startswith("push "): splitted_list = command.split() value = int(splitted_list[1]) num_list.append(value) elif command == "pop": if len(num_list) == 0: print(-1) else: a = num_list.pop() print(a) elif command == "size": print(len(num_list)) elif command == "empt.. 2023. 7. 24. Baekjoon Training #5430 #5430 AC import sys from collections import deque input = sys.stdin.readline T = int(input()) # 테스트 케이스의 개수 T입력 for i in range(T): p = input().strip() # 함수 입력 n = int(input()) # 정수 배열의 정수의 수 입력 err = 0 # 에러 상태인지 확인 arr = input().strip() # 정수 배열 입력 dq = deque(arr[1:-1].split(',')) # []와 , 를 제거하여 deque 자료구조로 dq에 입력 if n == 0: # n이 0이면 빈 deque으로 설정 dq = deque() R_cnt = 0 # R연산 횟수 카운터 for i in range.. 2023. 5. 4. Baekjoon Training #9660 #9660 돌 게임 6 N=int(input()) if N%7 == 2 or N%7 == 0: print("CY") else: print("SK") 나름 골드 문제인데 너무나 간단하다. 이는 코드는 간단하지만 dp문제같이 문제 자체의 특징을 찾아서 분석하는 것이 중요하기 때문이다. 위 문제를 보면 돌을 한번에 1,3,4개를 가져갈 수 있다. 돌의 개수에 따라 상황을 생각해보자. 돌 1개 - 상근 승 돌 2개 - 창영 승 돌 3개 - 상근 승 돌 4개 - 상근 승 여기까지는 쉽게 생각해볼 수 있다. 여기서부터는 승리를 위해서는 상근이 시작하기 때문에 처음에 상근이가 돌을 가져가면서 이전 경우에서 창영승인 경우인 돌수로 만들 수 있느냐를 판단해야한다. 왜냐하면 창영승인 돌수는 결국 두번째 선택자가 무조건 승.. 2023. 4. 2. Baekjoon Training #2630 #2630 색종이 만들기 import sys input = sys.stdin.readline # 시간단축용 n = int(input()) # 색종이 변의 길이 base = [list(map(int,input().split())) for _ in range(n)] # 색 베이스를 2차원 배열로 세팅 ans_list = [] # 정답을 담을 ans_list 초기화 # 색 구분하는 check함수 def check(x, y, n): color = base[x][y] # 시작점 색을 기준점으로 설정 # 2중 for문을 통해 전체 색 조사 for i in range(x, x+n): for j in range(y, y+n): if color != base[i][j]: # 확인중인 칸의 색이 기준점 색과 다르면 n2 .. 2023. 3. 30. Baekjoon Training #1891 #1891 사분면 Source Code d, num = input().split() # d: 총 단계 수, num: 이동 경로를 나타내는 문자열 d = int(d) # d를 정수형으로 변환 x, y = map(int, input().split()) # x: 가로 이동거리, y: 세로 이동거리 size = (2**d) def find(num, idx, curX, curY, size): # 단계가 0이 되면 현재 좌표를 기억하고 리턴 if size == 0: # 전역 변수선언 global tarX, tarY tarX, tarY = curX, curY # 타겟 좌표 설정 return # 자리수별로 번호에 따른 다음 이동을 찾아 재귀 호출 if num[idx] == '1': find(num, idx+1, cur.. 2023. 3. 25. Baekjoon Training #11501 #11501 주식 import sys input = sys.stdin.readline n = int(input()) # 몇번의 거래를 진행할지 입력 for _ in range(n): # 거래 횟수만큼 반복 days = int(input()) # 몇일동안 거래진행할지 결정 stock = list(map(int, input().split())) # 거래일동안 주식가격 리스트 stock = list(reversed(stock)) # 역순정렬 리스트로 변경 max_price = stock[0] # max_price 초기화 profit = 0 # 총 이익 0으로 초기화 for price in (stock[1:]): # 0번 인덱스를 max_price로 설정하였으므로 1번 인덱스부터 조사 진행 if price > .. 2023. 3. 16. Baekjoon Training #2470 #2470 두 용액 메모리 초과 오답 import sys import itertools input = sys.stdin.readline n = int(input()) sol_list = list(map(int,input().split())) # 산도를 입력받음 combi_list = itertools.combinations(sol_list, 2) # 모든 조합 생성후 리스트에 담음 mixed_list = [sum(t) for t in combi_list] # 튜플로 구성된 리스트에서 튜플값들을 더하여 리스트에 다시 입력 acid_list = [abs(num) for num in mixed_list] # 해당 값들의 절대값을 리스트에 담음 min_mix = min(acid_list) # 그중 최소값을 찾음.. 2023. 3. 14. Baekjoon Training #1062 #1062 가르침 오답(by chatGPT) import itertools import sys input = sys.stdin.readline N, K = map(int, input().split()) words = [input().strip() for _ in range(N)] if K < 5: print(0) else: alpha_list = set('abcdefghijklmnopqrstuvwxyz') - set('antic') max_count = 0 for comb in itertools.combinations(alpha_list, K-5): count = sum(all(c in comb for c in w[4:-4]) for w in words) max_count = max(max_count, .. 2023. 3. 10. 이전 1 2 3 4 5 6 ··· 9 다음 728x90
