본문 바로가기

Tech68

1904번 01타일 동적 프로그래밍이 어려워서 한 문제씩 차근차근히 공부해 보기로 했다. 1. 문제의 이해 00이 쓰여진 타일과 1이 쓰여진 타일로 크기 N을 몇 가지 만들 수 있나? 라는 문제다. 문제를 단순화하면, 00은 길이2, 1은 길이1로 생각한다. 그러면 2와 1을 써서 만들 수 있는 합이 N나오는 순열 개수 구하기다. 길이가 1일 때 만들 수 있는 순열은 [1] 한 가지. 길이가 2일 때 만들 수 있는 순열은 [2]와 [1,1] 두 가지다. 2. dp의 정의 타일을 길이만큼 채워 나갈 때 공간이 점점 줄어들고, 그 과정에서 과거에 채워 본 공간이 계속 등장한다. 다시말해 과거의 연산을 이용해서 가짓수를 구할 수 있다. 길이 1과 2를 계산한 후 길이 3의 공간을 채운다고 했을 때, 길이 1짜리 타일을 붙이고 나.. 2024. 2. 25.
음? 2024. 2. 24.
카데인 알고리즘(Kadane's Algorithm) 가장 큰 부분순열의 합을 구하는 문제는 "최대 부분 배열 합(Maximum Subarray Sum)" 문제로 알려진 유명한 문제다. 해결법으로 가장 유명한 알고리즘은 카데인 알고리즘(Kadane's Algorithm)이다. 카데인 알고리즘은 동적 프로그래밍을 활용하여, 배열을 한 번만 순회하면서 최대 부분 배열의 합을 효율적으로 찾는다. 이 알고리즘은 시간 복잡도 (O(n))을 가지며, 여기서 (n)은 배열의 크기다. 카데인 알고리즘의 기본 아이디어는 각 단계에서 현재까지의 최대 부분 배열 합을 계속 업데이트하는 것이다. 이때 두 가지 선택을 고려한다: 현재 원소를 포함하는 새로운 부분 배열을 시작하는 것이 더 나은지, 아니면 현재 원소를 이전 부분 배열에 추가하는 것이 더 나은지. 아래는 카데인 알고리.. 2024. 2. 24.
RGB거리 import sys raw = sys.stdin.readlines() n = int(raw[0]) c = [[int(x) for x in line.split()] for line in raw[1:]] dp = [[0,0,0] for _ in range(n)] dp[0] = c[0] for i in range(1, n): dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + c[i][0] dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + c[i][1] dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + c[i][2] print(min(dp[n-1])) 이 코드는 집을 칠하는 데 필요한 최소 비용을 계산하는 동적 계획법(Dynamic Progr.. 2024. 2. 22.
# 9251번 LCS def lcs(A, B): lenA, lenB = len(A), len(B) DP = [[0] * (lenB+1) for _ in range(lenA+1)] for i in range(1, lenA+1): for j in range(1, lenB+1): if A[i-1] == B[j-1]: DP[i][j] = DP[i-1][j-1] + 1 else: DP[i][j] = max(DP[i-1][j], DP[i][j-1]) return DP[lenA][lenB] def main(): A = input() B = input() print(lcs(A, B)) if __name__ == "__main__": main() lcs(A, B) 함수는 두 문자열 A와 B를 입력으로 받습니다. 변수 lenA와 lenB는 각.. 2024. 2. 19.
# 12865 평범한 배낭(Python 파이썬) N, K = map(int, input().split()) # 물품의 수 N, 최대 무게 K 입력 받기 items = [(0, 0)] # 물건의 무게와 가치를 저장할 리스트, 0번 인덱스는 사용하지 않기 위해 초기값 설정 for _ in range(N): W, V = map(int, input().split()) # 각 물건의 무게 W와 가치 V 입력 받기 items.append((W, V)) # dp[i][w]: 처음 i개의 물건을 고려했을 때, 무게 w까지의 배낭에 담을 수 있는 최대 가치 dp = [[0 for _ in range(K+1)] for _ in range(N+1)] for i in range(1, N+1): for w in range(1, K+1): if items[i][0] 13 무게.. 2024. 2. 17.
백트래킹(Backtracking, 퇴각검색) # 14889번 스타트와 링크, # 9663번 N-Queen [파이썬] 목차 그래프와 트리 탐색 알고리즘 백트래킹의 소개 개념 방법 성능개선 개발 활용 사례(예산 활용법 찾기) 알고리즘 설명 코드보기 백준 문제 #14889 스타트와 링크 # 9663번 N-Queen α–β A* B* 퇴각검색 빔 벨먼-포드 최상 우선 양방향 Borůvka 분기 한정법 BFS 영국박물관 D* DFS 데이크스트라 에드먼즈 플로이드-워셜 Fringe search 언덕등반기법 IDA* 반복적 깊이심화 존슨 Jump point 크러스컬 Lexicographic BFS LPA* 프림 SMA* 출처: https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89 퇴각검색 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 퇴각검색.. 2024. 2. 14.
프로필 마크다운 I'm Hyunsu Park(Hanzch, Uranus99.77) 2024. 2. 10.
14889번 스타트와 링크 - 백 트래킹 14889번 스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 더보기 문제의 이해 어떤 사람과 팀이 되느냐에 따라 능력치가 달라질 때 두 팀의 능력치 차이가 가장 적을 때 얼마인지 알아내는 문제다. 직관적으로 떠오르는 방법은 조합을 구하고 팀 1,2를 조합해서 최소값을 찾으면 되는 문제인데 백트래킹이 붙어 있어서 아마 안 되겠지 생각하며 해 보았는데 성공. 조합을 생각해 보면 한 팀만 구성하면 나머지 팀이 완성되기 때문에, 그리고 인원이 짝수인 것이 보장되기 때문에 $$n C (n/2) = \frac{n!}{(n/2)!.. 2024. 2. 8.
백준 # 31287번 장난감 강아지 - 파이썬 4 2 URLD YES 3 2 URD NO 시뮬레이션으로는 풀리지 않고 시간 초과가 난다. 생긴 도형의 최종점과 원점의 관계를 통해 그림을 새로 그리지 않고 원점을 최종점(x,y)에 대해 -x, -y 만큼 이동한다고 생각하고 문제를 풀었지만 시간 초과를 도무지 해결할 수가 없었다. 먼저 1회 순회하면서 0,0을 지나는지, 어느 점을 지나는지 기록하고, 최종점을 구한 뒤에 2회 반복부터는 좌표에 대한 함수로 구하려고 했는데.... 안되었다. 망한 코드를 보자. 이거보다 개선된 k회 포지션을 기준으로 하는 코드가 있는데 의미없다. def can_return_to_origin(n, k, text): x, y = 0, 0 positions = set() # 거쳐간 좌표들을 저장할 집합 # 명령어 순회 for t.. 2024. 2. 5.
[Python]collections.Counter 파이썬 collections.Counter에 대한 설명 파이썬의 collections 모듈에 있는 Counter 클래스는 요소들의 개수를 셀 때 매우 유용한 데이터 구조입니다. Counter는 사실상 사전(dictionary)의 하위 클래스로, 해시 가능한(hashable) 객체를 카운트하는 딕셔너리입니다. 각 요소는 딕셔너리의 키(key)로 저장되며, 그 요소의 개수가 키의 값(value)으로 저장됩니다. Counter 클래스의 알고리즘 Counter 클래스의 알고리즘은 주어진 입력(리스트, 튜플, 문자열 등)에서 요소의 등장 횟수를 계산하여, 각 요소를 키로, 해당 요소의 개수를 값으로 하는 사전 형태로 저장합니다. 이 과정은 내부적으로 해시 테이블을 사용하여 효율적으로 수행됩니다. 주요 기능 초기화.. 2024. 2. 5.
# 11659번 구간 합 구하기 4 1 초 256 MB 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 제한 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ i ≤ j ≤ N 예제 입력 1 복사 5 3 5 4 3 2 1 1 3 2 4 5 5 예제 출력 1 복사 12 9 1 from sys import stdin as si input = si.readline n,m = map(i.. 2024. 2. 5.

티스토리툴바