본문 바로가기

dev/알고리즘문제풀이13

[ 백준 2098번 ] 외판원 순회 파이썬 [백준 2098번 바로가기] 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 유튜브 주니온 TV 아무거나 연구소 강의를 참고했습니다. [유튜브 주니온TV 강의 바로가기] 손글씨로 대체합니다 논리 및 점화식 집합 연산은 비트마스킹을 이용했습니다(아래에 간단한 설명 첨부했습니다) 비트마스킹 코드 import sys def 외판원순회(): # bit-masking functions # 원소 포함 여부 확인 def isIn(A: int, i: int): return (A & (1 2021. 9. 1.
[ 백준 12865번 ] 아주 평범한 배낭 파이썬 [백준 12865번 바로가기] 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 논리 배낭의 한계 무게에서 가질 수 있는 물건들의 가치의 최대값 각 무게마다의 최대 가치를 가지는 table을 만든다(table[i]: i무게에서 가질 수 있는 최대값) 각 물건마다 table[i]에 들어가는 경우를 생각해보고 가치의 최댓값을 갱신한다 ex) 한 물건으 무게가 w, 가치가 v라고 할 때, table[i]에서 이 물건을 고려해보자 --> i무게에서 w만큼.. 2021. 9. 1.
[ 백준 11049번 ] 행렬 곱셈 순서 파이썬 [백준 11049번 바로가기] 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 손글씨로 설명을 대체합니다 논리 점화식 동작 순서 예시 코드 import sys def minimum_matrix_operation(): # inputs N = int(sys.stdin.readline()) matrices = [None] * N for i in range(N): matrices[i] = list(map(int, sys.stdin.readline().split())) # table[i][j]: i-th-M.. 2021. 9. 1.
[ 백준 9251번 ] LCS 파이썬 [백준 9251번 바로가기] 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 논리 두 문자열 s1, s2의 끝자리가 같다면 lcs(s1, s2)는 lcs(s1[:-1], s2[:-1]) + 1과 같다 (마지막 문자가 같으므로 이를 제외한 것들의 lcs에서 1을 더함) 두 문자열 sl, s2의 끝자리가 다르다면 lcs(s1, s2)는 lcs(s1, s2[:-1])과 lcs(s1[:-1], s2) 중 큰 값을 취한다 공통 문자열을 확인하고 싶다면 lcs_table을 거.. 2021. 9. 1.

티스토리툴바