Algorithm/Baekjoon117 1719. 택배 (Python) 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 플로이드 워셜 알고리즘을 사용하여 해결할 수 있다. 기존의 플로이드 워셜 알고리즘에서 최단거리를 기록하는 graph 배열에 첫 번째로 방문하는 집하장 정보를 추가한다. i에서 j로 가는 경로가 k 집하장을 거쳐서 가는 경로의 길이로 갱신될 때 graph[i][k]에 기록되어 있는 첫 번째로 방문하는 집하장 정보를 graph[i][j]에 기록해주면 된다. 코드 import sys input = sys.stdin.readline INF = float('inf') if .. 2022. 6. 24. 16398. 행성 연결 (Python) 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 풀이 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 만들면 된다. 크루스칼 알고리즘에 대해서 간단히 설명하자면 입력으로 주어진 간선 정보를 비용을 기준으로 오름차순 정렬한다(우선수위 큐를 사용하면 된다). 비용이 낮은 순으로 간선을 꺼내어 해당 간선을 사용했을 때 그래프에 사이클이 발생하는지 체크한다. 사이클이 발생하지 않을때만 해당 간선을 사용하여 그래프를 완성해 나간다. 이를 반복하여 총 N개의 정점이 있을 때 N-1개의 간선을 사용했다면 모든 정점이 사이클.. 2022. 6. 23. 2342. Dance Dance Revolution (Python) 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 3차원 dp를 사용하여 재귀 함수를 통해 답을 구할 수 있다. 3차원 배열인 dp에는 다음과 같은 정보가 저장된다. dp[left][right][idx] : idx번째 지시사항에서 왼발이 left에 오른발이 right 위치에 있을 때 사용되는 최소의 힘 왼발과 오른발을 모두 이동시켜가며 dp 배열에 최솟값이 저장되도록 구현해주면 된다. 다만 지시사항이 요구하는 위치가 왼발 또는 오른발과 같은 위치라면 두 발을 모두 이동시킬.. 2022. 6. 20. 9252. LCS 2 (Python) 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 LCS를 구하는 알고리즘(참고)을 그대로 적용하여 해결하면 된다. 추가적으로 최장 길이에 해당하는 문자열도 구해야 하는데 추가적으로 2차원 리스트를 하나 만들어서 문자열을 기록해 나가면 된다. 생각해 보니까 걍 2차원 리스트 하나만 써도 돼서 하나만 썼다. dp 배열 하나만 쓰고 여기에 문자열을 기록하고 길이는 len()을 사용했다. 두 문자열 A와 B가 있을 때 A의 i번째 문자와 B의 j번째 문자가 같다면.. 2022. 6. 20. 2473. 세 용액 (Python) 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 두 용액(링크)과 유사한 문제로 투 포인터를 사용하여 문제를 해결할 수 있다. 문제는 총 3개의 용액을 더해야 한다는 것인데 3개의 포인터를 두고 탐색하되 하나의 포인터는 움직이지 않고 고정시킨다. 그리고 나머지 2개의 포인터를 기존의 두 용액에서와 마찬가지로 합이 양수냐 음수냐에 따라서 이동시켜가며 0에 가까운 세 용액을 구하면 된다. 코드 if __name__ == '__main__': N = int(input()) values =.. 2022. 6. 19. 2629. 양팔저울 (Python) 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 풀이 재귀를 사용하여 1)저울의 왼쪽에 추를 올리는 경우, 2)저울의 오른쪽에 추를 올리는 경우, 3)추를 저울에 올리지 않는 경우로 나누어 재귀를 통해 구할 수 있는 구슬의 무게에 대한 경우의 수를 체크한다. 2차원 배열 dp에는 다음과 같은 정보가 저장된다. dp[weight][n] -> n번 추까지 사용했을 때 무게 weight를 만들 수 있는지에 대한 정보 코드 from collections import defaultdict # idx: idx번 째 추, .. 2022. 6. 18. 이전 1 2 3 4 5 6 ··· 20 다음
