본문 바로가기

Tech/Coding51

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.
#1927번 최소 힙 최소 힙(Min Heap) 이해와 파이썬 구현 최소 힙이란? 최소 힙은 완전 이진 트리를 기반으로 한 자료구조로, 각 노드의 값이 자식 노드의 값보다 작거나 같아야 하는 특성을 가집니다. 이로 인해 트리의 루트에는 항상 최소값이 위치하게 됩니다. 최소 힙은 다양한 알고리즘과 자료구조에서 중요하게 활용됩니다. 최소 힙의 기본 연산 삽입(Insertion): 새 요소를 힙의 마지막에 추가한 뒤, 부모 노드와 비교하며 힙의 조건을 만족시킬 위치로 조정합니다. 삭제(Deletion): 힙에서 요소를 제거할 때 주로 최소값(루트 노드)을 제거합니다. 루트 노드를 제거한 후 마지막 요소를 루트로 옮기고, 힙의 조건을 만족시키도록 재조정합니다. 최소값 찾기(Find Min): 루트 노드에 위치한 최소값을 즉각적으로 .. 2024. 2. 5.
백준 #1168번 요세푸스 문제 2 와 세그먼트 트리 파이썬 + 11025번 요세푸스 문제 3 백준에서 변형 문제 2개를 제외하면 정통(?) 요세푸스 문제는 아래와 같습니다. 요세푸스 순열을 구하는 문제 마지막 생존자를 구하는 문제 문제 제목 요세푸스 문제 0 11866번 2초/512MB 요세푸스 문제 1158번 2초/256MB 요세푸스 문제 2 1168번 0.15초/128MB 요세푸스 문제3 11025번 1 초/ 16 MB 마지막 요세푸스 문제 1179번 2초 128MB 입력범위 및 부가조건 1 ≤ K ≤ N ≤ 1,000 1 ≤ K ≤ N ≤ 5,000 1 ≤K≤ N≤ 100,000 Java X: 0.8 PythonPyPy: 0.75 Kotlin (JVM): 0.8 1 ≤K≤N≤ 5,000,000 1 ≤ N ≤ 10^15 1 ≤ K ≤ 90 요세푸스 문제 - 위키백과, 우리 모두의 백과사전 위.. 2024. 2. 4.
#2563번 색종이 2563번 색종이 문제 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오. 예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다. 입력 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연.. 2024. 2. 2.

티스토리툴바