목록2025/02 (6)

몸과 마음이 건전한 SW 개발자

백준 GOLD 5 [11729번] 하노이 탑 이동 순서 {언어 : Python} [다시 풀어 보기]

문제 링크https://www.acmicpc.net/problem/11729정답 코드n = int(input())dp = [0] * 21dp[1] = 1for i in range(2, 21): dp[i] = dp[i-1] * 2 + 1print(dp[n])def hanoi(number, start, end, assist): if number == 1: print(start, end) return else: hanoi(number-1, start, assist, end) print(start, end) hanoi(number-1, assist, end, start)hanoi(n, 1, 3, 2)풀이 방법파라미터에 숫자, 시작 지..
알고리즘/다시 풀어 보기 2025. 2. 14. 16:32
백준 GOLD 5 [9251번] LCS {언어 : Python} [다시 풀어 보기]

문제 링크https://www.acmicpc.net/problem/9251정답 코드 1a = input()b = input()lenA = len(a)lenB = len(b)dp = [[0] * (lenA+1) for _ in range(lenB+1)]maxLength = 0for i in range(lenB): alphaB = b[i] for j in range(lenA): alphaA = a[j] if alphaA == alphaB: dp[i][j] += dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) maxLength = max(maxLen..
알고리즘/다시 풀어 보기 2025. 2. 13. 13:38
백준 SILVER 3 [3273번] 두 수의 합 {언어 : Python}

문제 링크https://www.acmicpc.net/problem/3273정답 코드n = int(input())arr = sorted(list(map(int, input().split())))val = int(input())left = 0right = n - 1answer = 0while left val: right -= 1 else: left += 1print(answer)풀이 방법투 포인터를 사용했다.정렬한 배열의 좌 우측에서 값을 가져온다.값이 원하는 값과 같다면 좌를 키우고 우를 낮춰서 범위를 줄여준다.값이 작다면 좌측에서 값을 키워야 하므로 좌를 키운다.값이 크다면 우측에서 값을 낮춰야 하므로 우를 낮춘다.좌우 값이 같지 않을 때 까지 한다.인덱스가 겹치지 않는 ..
알고리즘 2025. 2. 11. 15:22
백준 GOLD 5 [2565번] 전깃줄 {언어 : Python} [다시 풀어 보기]

문제 링크https://www.acmicpc.net/problem/2565정답 코드import sysinput = sys.stdin.readlinen = int(input())lines = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x:x[1])dp = [1] * nfor i in range(1, n): si, ti = lines[i] for j in range(i): sj, tj = lines[j] if sj 풀이 방법 입력 처리 및 정렬(시작점, 끝점)을 입력받고 끝나는 지점 기준으로 정렬한다.정렬은 그리디 + DP 조합을 활용하기 위한 사전 작업이다.DP 배열 정의 및 초기화dp[..
알고리즘/다시 풀어 보기 2025. 2. 10. 16:23
백준 GOLD 5 [12919번] A와 B 2 {언어 : Python} [반례 포함]

문제 링크https://www.acmicpc.net/problem/12919정답 코드s = input()t = input()lenS = len(s)lenT = len(t)answer = 0def isIncluded(arr): normarlString = "".join(arr) reversString = "".join(arr[::-1]) return normarlString in t or reversString in tdef dfs(length, arr): global answer if answer: return if length == lenT: string = "".join(arr) if string == t: an..
알고리즘 2025. 2. 7. 16:36
백준 GOLD 4 [10830번] 행렬 제곱 {언어 : Python}

문제 링크https://www.acmicpc.net/problem/10830정답 코드import sysinput = sys.stdin.readlinen, b = map(int, input().split())matrix = [list(map(int, input().split())) for _ in range(n)]optimization = dict()# matrix의 원소가 1000이하이기 때문에 처음부터 걸러준다.for i in range(n): for j in range(n): matrix[i][j] %= 1000optimization[1] = matrix# cal = calculationdef cal(leftM, rightM): newM = [[0] * n for _ in ra..
알고리즘/풀었지만 다시 보기 2025. 2. 4. 17:23
이전 Prev 1 Next 다음