두두의 알고리즘 (145) 썸네일형 리스트형 [기타] 릿코드 Easy 20 'Valid Parentheses' (Python) https://leetcode.com/problems/valid-parentheses/ Valid Parentheses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문자열에서 (), {}, []가 있는지 확인한다. (), {}, []가 있다면 문자열에서 없앤다. (), {}, []가 없을 때까지 반복한다. 문자열에 문자가 남아있다면 False를 반환하고, 없다면 True를 반환한다. class Solution: def isValid(self, s: str).. [기타] 릿코드 Easy 1816 'Truncate Sentence' (Python) https://leetcode.com/problems/truncate-sentence/ Truncate Sentence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 띄어쓰기로 문자열을 구분한다. 순서대로 k 수의 단어를 구한다. 단어별 띄어쓰기 구분으로 문자열을 만든다. class Solution: def truncateSentence(self, s: str, k: int) -> str: s = s.split(' ') return ' '.join(s[:k]) [크루스칼] 백준 2887번 '행성 터널' (Python) https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 1. 모든 행성이 연결되도록 요구하므로, 최소 신장 트리를 만드는 문제임 2. x,y,z축 정렬 후 n-1개의 간선만 고려하면 최적의 솔루션 찾을 수 있음 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_p.. [크루스칼] 난이도2, University of Ulm Local Contest '어두운 길' (Python) 한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요... [서로소 집합] 난이도2, 핵심 유형 '여행 계획' (Python) 한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1~N번까지의 번호로 구분됩니다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있습니다. 이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다는 의미입니다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판단하고자 합니다. 예를 들어 N=5이고, 다음과 같이 도로의 정보가 주어졌다고 가정합시다. 1번-2번 1번-4번 1번-5번 2번-3번 2번-4번 만약 한울이의 여행 계획이 2번->3번->4번->3번이라고 해봅시다. 이 경우 2번->3번->2번->4번->2번->3번의 순서로 여행지를 방문하면, 여행 계획을 따를 수 있습니다. 여행지의 개수와 여행지 간의 연결 정보가 주어졌을 때,.. [크루스칼] 백준 1647번 '도시 분할 계획' (Python) https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 1. 모든 노드를 포함하면서 사이클이 존재하지 않고, 최소비용으로 신장트리를 만들어야 하므로 크루스칼 알고리즘 적용 2. 비용순으로 간선 정렬 3. 사이클이 발생하지 않는 경우에만 집합 합치기 4. 최소 신장트리를 구성하는 간선 중에서 가장 비용이 큰 간선 제거 def find_parent(parent, x): if parent[x]!=x: parent[x] .. [서로소 집합] 난이도2, 핵심 유형 '팀 결성' (Python) 학교에서 학생들에게 0번부터 N번까지의 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다. 1. '팀 합치기' 연산은 두 팀을 합치는 연산이다. 2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오. 첫째 줄에 N,M이 주어진다. M은 입력으로 주어지는 연산의 개수이다. (1 [다익스트라] 난이도2, ACM-ICPC '화성 탐사' (Python) 당신은 화성 탐사 기계를 개발하는 프로그래머입니다. 그런데 화성은 에너지 공급원을 찾기가 힘듭니다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 합니다. 화성 탐사 기계가 존재하는 공간은 N X N 크기의 2차원 공간이며, 각각의 칸 을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N-1][N-1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다. 첫째 줄에 테스트 케이스의 수 T(1 이전 1 2 3 4 5 ··· 19 다음