SSAFY

[python] SWEA - 3131. 100만 이하의 모든 소수

🤔문제 해결 D3 | 소수(에라토스테네스의 체) 💨 주어진 범위만큼의 길이를 가진 모든 원소가 1로 된 리스트를 만든다. ( 이 문제에서 범위는 10**6 ) 💨 리스트의 0번째와 1번째는 미리 0으로 만들어둔다. ( 소수가 아니므로 ) 💨 2부터 끝까지 반복문을 실행하면서 💨 해당 인덱스의 값이 0이 아니라면 💨 해당 인덱스를 제외한 배수의 인덱스의 값을 모두 0으로 바꿔준다. ( 소수가 아니므로 ) 💨💨 EX) 2번째 값이 1이면 4, 6, 8 ... 은 모두 0으로 바꿔준다. 💨 원소의 값이 1인 녀석들은 모두 소수이다. 💻소스 코드 N = 10 ** 6 + 1 eratos = [1] * N eratos[0], eratos[1] = 0, 0 for i in range(2, N): if eratos[..

[python] SWEA - 3750. Digit sum

🤔문제 해결 D3 | 문자열 💨 결과가 한자리 숫자가 될 때까지 각 자리의 숫자를 더해준다. 💨 SWEA 는 모든 입력을 받고 계산하고 모든 출력을 하는게 더 빠르다. 💨 알고리즘의 성능 차이라기 보다 테스트하는 시간의 초과인듯 하다. 💻소스 코드 # 인풋값 전부 받기 T = int(input()) numbers = [input() for _ in range(T)] # 계산하기 results = [] for tc in range(T): number = numbers[tc] answer = 0 while True: sum_num = 0 for n in number: sum_num += int(n) if sum_num > 9: # 결과값이 두자리 수 이면 다시 분해해서 더하기 number = str(sum_..

[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])): # 같..