문자열

[python] 백준 - 1148. 단어 만들기

🤔문제 해결 딕셔너리에 퍼즐의 각 알파벳을 키, 그 알파벳의 개수와 사용된 횟수의 딕셔너리를 벨류로 가진다. 퍼즐에 있는 알파벳으로 낱말을 만들 수 있다면 퍼즐에서 사용될 알파벳의 used_cnt 를 +1 해준다. 위와 같은 결과가 나오게 되고, used_cnt 가 가장 적은 값들, 가장 많은 값들을 알파벳 오름차순으로 출력해준다. 💻소스 코드 import pprint import sys input = sys.stdin.readline # 인풋 받아서 단어 or 퍼즐 따로 배열로 만드는 함수 (두번 반복할거 같아서 함수로 만듦) def input_func(arr, sign): arr = [] while True: input_value = input().strip() if input_value == sig..

[python] 백준 - 9251. LCS

🤔문제 해결 G5 | 다이나믹프로그래밍, 문자열 LCS란 최장 공통 부분 문자열(Longest Common Subsequence)이다. 순서는 맞지만 연속하지 않아도 되는 같은 문자열을 찾는 것이다. 예를 들어 ABCAB와 BDCB가 있다. ABCAB 와 BDCB 의 LCS는 BCB이다. LCS가 뭔지 안다고 해도 처음 접하면 구하는건 당연히 어렵다. 완전탐색을 하려고 했지만 역시나 시간초과가 발생했다. 문제 해결법이 DP이고 다른 고수들의 풀이방법을 참고해서 해결했다. 먼저 위와 같이 DP를 구성한다. 먼저 1번 째 행을 채워보면 AC와 C가 만나서 LCS는 1이다. 두번 째 행을 보자. A와 CA가 만나서 LCS는 1이다. ACA와 CA가 만나서 LCS는 2이다. 세번 째 행을 보자. A와 CAP =..