Algorithm Problem

[python] SWEA - 3408. 세가지 합 구하기

🤔문제 해결 D3 | 수학 💨 1부터 N 까지 숫자의 합: N * (N + 1) / 2 💨 1부터 N 개의 홀수의 합: N ** 2 💨 1부터 N 개의 짝수의 합: N * (N + 1) 💻소스 코드 # 인풋 T = int(input()) Ns = [int(input()) for _ in range(T)] # 풀이 results = [] for tc in range(T): n = Ns[tc] result = [] # 전체: n(n+1)//2 result.append(n*(n+1)//2) # 홀수: n**2 result.append(n**2) # 짝수: n(n+1) result.append(n*(n+1)) results.append(result) # 결과 for tc in range(T): print(f'#..

[python] SWEA - 3376. 파도반 수열

🤔문제 해결 D3 | dp? (피보나치) 💨 N = N-3 + N-2 💻소스 코드 # 인풋 T = int(input()) Ns = [int(input()) for _ in range(T)] # 풀이 # N-3 + N-2 = N, 피보나치랑 비슷, 숫자가 나올때 마다 구하면 시간이 오래걸리므로 한번에 구해놓고 해결하자. pado = [1, 1, 1] for i in range(3, 101): # N 의 범위가 100 까지 pado.append(pado[i - 3] + pado[i - 2]) # 결과 출력 for tc in range(T): print(f'#{tc + 1} {pado[Ns[tc] - 1]}') 📕문제 확인 출처: SW Expert Academy SW Expert Academy SW 프로그래밍..

[python] SWEA - 3307. 최장 증가 부분 수열

🤔문제 해결 D3 | DP 💨 [python] 백준 - 11055. 가장 큰 증가 부분 수열 💨 각 숫자마다 이전의 숫자와 비교하면서 점점 길이를 늘려 나간다. 💻소스 코드 # 입력 T = int(input()) Ns = [] for tc in range(T): N = int(input()) numbers = list(map(int, input().split())) Ns.append((N, numbers)) # 풀이 - DP results = [] for tc in range(T): N, numbers = Ns[tc] # 두번째 부터 끝까지 # 자신의 앞쪽의 숫자들을 탐색 # 현재 자신이 몇개의 연속된 증가하는 부분 수열인지 체크 # 초기화: 자신 혼자 이므로 1로 초기화 dp = [0] * N dp[0..

[python] SWEA - 3304. 최장 공통 부분 수열

🤔문제 해결 D3 | DP (LCS) 💨 역시 SWEA의 난이도는 믿을게 못된다. 이게 겨우 D3라니... 💨 [python] 백준 - 9251. LCS (참고) 💨 지난번에 백준에서 한번 풀었고, 코딩테스트할 때 한번 풀었고, 이번에 다시 푸니깐 어느정도 이해가 된거 같다. 💻소스 코드 # 입력 T = int(input()) Ns = [input() for _ in range(T)] # 풀이 - LCS results = [] for tc in range(T): A, B = Ns[tc].split() dp = [[0] * (len(A) + 1) for _ in range(len(B) + 1)] for i in range(1, len(dp)): for j in range(1, len(dp[i])): # 같..

[python] SWEA - 3282. 0/1 Knapsack

🤔문제 해결 D3 | DP( Knapsack ) 💨 냅색알고리즘 💨 각 아이템에 대해서 가방의 크기를 0부터 1씩 최대무게까지 늘려가며 계산. 💨 가방의 크기가 해당 아이템의 무게보다 작으면 아이템을 넣지 못한다. 이전까지의 무게와 가치 적용 💨 가방의 크기가 해당 아이템의 무게보다 크면 아이템을 넣을지 말지 선택한다. 💨💨 이전까지의 무게와 가치 vs (이전까지의 무게 - 현재 아이템의 무게)의 가치 + 현재 아이템의 가치 💻소스 코드 # 입력 T = int(input()) Ns = [] for tc in range(T): N, K = map(int, input().split()) items = [list(map(int, input().split())) for _ in range(N)] Ns.appen..

[python] SWEA - 3975. 승률 비교하기

🤔문제 해결 D3 | 수학 💨 D1이라고 해도 아까운 문제 D0.5 💨 알고리즘 해결문제가 아닌 입출력 속도의 문제이다. 💨 심지어 파이썬은 sys.stdin 을 막아놓음( 표준 입출력 input 만 사용하도록 ) 💨 입력 받고 계산해서 출력하는 것보다 💨 입력을 다 받고 그 후 계산해서 출력하는 것이 빠르다. 💻소스 코드 lst = [] T = int(input()) for tc in range(T): lst.append(tuple(map(int, input().split()))) for tc in range(T): A, B, C, D = lst[tc] ALICE = A / B BOB = C / D print(f'#{tc + 1}', end=' ') if ALICE > BOB: print('ALICE'..