algortihm3 [Python] 소프티어 : 플레이페어 암호 https://softeer.ai/practice/info.do?idx=1&eid=804&sw_prbl_sbms_sn=162388 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 전형적인 구현 문제이다. key에 맞춰서 5x5 짜리 판을 초기화해 주고, 특정 알파벳의 위치를 저장한 테이블을 초기화한다. 이후 2자리로 잘라준다음 요구사항에 맞춰서 구현하면 된다. 주의할 점은 X가 단 하나 남았을 경우 XX가 만들어진다는 점과 J를 사용하지 않는다는 점이다. ✔️ 느낀 점 크게 어려울 것 없는 문제였다. 💻 코드 import sys ; input = sys.stdin.readline from collections import deque ALPHABET = ".. 2023. 3. 5. [Python] 백준 1005번 : ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 💡 문제 풀이 동적 프로그래밍과 위상정렬을 합친 문제이다. 위상정렬을 통해서 해당 노드까지 가는 길을 파악하고 DP로 최적화한다. 이해를 위해서 문제에서 제공된 첫 예제로 이해해 보자. 1부터 4까지 가기 위해서는 1 → 2, 3 → 4로 가야 한다. DP[i]에서 저장되는 값은 정점 i까지 도달했을 때의 최댓값이다. 4로 가는 길은 2가지이지만, 각 경로에 대한 비용을 따져서 최댓값으로만 .. 2023. 3. 3. [Python] 백준 1520번 : 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 💡 문제 풀이 그래프 탐색(DFS)에 DP를 곁들인 문제이다. 그냥 DFS로 구현하면 시간초과가 발생한다. 그래서 이미 지나온 길에 대해서는 이전에 방문한 결과를 바로 전달해 주는 방식으로 중간에 순회하는 시간을 줄일 수 있다. ✔️ 느낀 점 그냥 DFS 문제인 줄 알았지만 DP가 곁들인거 보고 큰코다쳤다. 💻 코드 import sys input = sys.stdin.readline dx = [.. 2023. 2. 26. 이전 1 다음