본문 바로가기
728x90
반응형

알고리즘

 (31)
[ Python ] 1340번 : 연도 진행바 코딩테스트 해설백준 1340번: 연도 진행문제 유형 : 구현, 문자열, 파싱작성 코드import sysfrom datetime import datetimeinput = sys.stdin.readlinetoday = input().rstrip()today = datetime.strptime(today, "%B %d, %Y %H:%M")start_year = datetime(today.year, 1, 1, 0, 0, 0)next_year = datetime(today.year + 1, 1, 1, 0, 0, 0)today_seconds = (today - start_year).total_seconds()next_year_seconds = (next_year - start_year).total_seconds()..
[ Python ] 1149번 : RGB거리 코딩테스트 해설백준 1149번: RGB거리문제 유형 : DP작성 코드import sysinput = sys.stdin.readlineN = int(input())dp = [list(map(int, input().split(" "))) for _ in range(N)]for i in range(1, N): dp[i][0] += min(dp[i-1][1], dp[i-1][2]) dp[i][1] += min(dp[i-1][0], dp[i-1][2]) dp[i][2] += min(dp[i-1][0], dp[i-1][1])print(min(dp[N-1][0], dp[N-1][1], dp[N-1][2]))접근 방식 각 집을 칠할 때 이전 집에서 선택하지 않은 색 중 최소 비용을 선택하는 방식으로 ..
[ 알고리즘 ] 동적계획법(DP;Dynamic Programming) 동적 계획법 이란?쉽게 풀어쓰자면, 큰 문제를 작은 단위로 나눠 푸는 기법입니다. 이때 작은 문제들이 반복적으로 나타나고, 그 결과를 저장하여 중복 계산을 피하는 것이 핵심입니다. 이는 알고리즘의 효율성을 높이고 복잡한 문제를 효과적으로 해결할 수 있게 해줍니다.동적 계획법의 핵심 개념중복되는 부분 문제 (Overlapping Subproblems): 동일한 작은 문제들이 여러 번 반복되어 나타나는 경우.최적 부분 구조 (Optimal Substructure): 문제의 최적해가 부분 문제의 최적해로부터 구성되는 경우.이 두 가지 조건을 만족하는 문제에 동적 계획법을 적용하면 효율적인 해결이 가능합니다.메모이제이션(Memoization)이전에 계산한 결과를 저장하여 중복 계산을 피하는 기법입니다. 이는 재..
[ Python ] 토스 : 멋쟁이 숫자 코딩테스트 해설숫자로만 이루어진 문자열 s가 있습니다. (0 [조건]길이가 3인 s의 substring을 10진수로 읽은 숫자이다.각 자리의 숫자가 모두 같다.문자열s를 입력받아 멋쟁이 숫자를 리턴하는 함수를 만들어주세요.만약, 멋쟁이 숫자가 여러 개 존재하는 경우에는 가장 큰 수를 리턴합니다.만약, 가장 큰 멋쟁이 숫자가 000이라면 0을 리턴합니다.만약, 멋쟁이 숫자가 존재하지 않다면 -1을 리턴합니다.작성 코드import repattern = r"(\d)\1{2}"def solution(s): result = re.findall(pattern, s) if not result: return -1 return max(result) * 3접근 방식정규식을 이용하여 문자열 s의..
[ Python ] 1208번 : 부분수열의 합 2 코딩테스트 해설백준 1208번: 부분수열의 합 2문제 유형 : 이분 탐색, 중간에서 만나기작성 코드import sysfrom itertools import combinationsfrom collections import defaultdictdef input(): return sys.stdin.readline().rstrip()def sub_sums(seq_list): sum_list = defaultdict(int) for i in range(len(seq_list) + 1): for subset in combinations(seq_list, i): sum_list[sum(subset)] += 1 return sum_listdef solve(N, S,..
[ Python ] 6603번 : 로또 코딩테스트 해설백준 6603번: 로또문제 유형 : 수학, 조합론, 백트래킹, 재귀작성 코드import sysfrom itertools import combinationsdef lotto(numbers): for combination in combinations(numbers, 6): print(' '.join(map(str, combination))) print()while True: line = list(map(int, sys.stdin.readline().rstrip().split())) k = line[0] if k == 0: break numbers = line[1:] lotto(numbers)접근 방식itertools의 combina..
[ Python ] 15657번 : N과 M (8) 코딩테스트 해설백준 15657번: N과 M (8)문제 유형 : 백트래킹작성 코드import sysN, M = map(int, sys.stdin.readline().rstrip().split(" "))sequence = sorted(map(int, sys.stdin.readline().rstrip().split(" ")))def backtrack(start, current): if len(current) == M: print(" ".join(map(str, current))) return for i in range(start, N): backtrack(i, current + [sequence[i]])backtrack(0, [])접근 방식백트래킹 방식을 적용하..
[ Python ] 15656번 : N과 M (7) 코딩테스트 해설백준 15656번: N과 M (7)문제 유형 : 백트래킹작성 코드import sysN, M = map(int, sys.stdin.readline().split(" "))sequence = sorted(map(int, sys.stdin.readline().split(" ")))def recursion_tree(current_select: list, depth: int) -> list: if depth == M: return [current_select] results = [] for num in range(N): results.extend(recursion_tree(current_select + [num], depth + 1)) return re..
728x90
반응형

티스토리툴바