두두의 알고리즘/문제 (124) 썸네일형 리스트형 [힙] 백준 11286번 '절댓값 힙' (Python) https://www.acmicpc.net/problem/11286 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 1. 최솟값이라는 우선순위대로 출력하므로 힙 사용 #내코드 #17분/40분 import heapq import sys input = sys.stdin.readline result = [] queue = [] n = int(input()) for i in range(n): x = int(input()) if x != 0: heapq.heappush(queue,[ab.. [손코딩] 문제 1~3 1. 회문은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함. 회문을 판별할 수 있는 함수를 리스트 슬라이싱을 활용해서 만드세요 ex) rumur 질문 ex) string 변수에 null(None)이 올 수 있는지, null이 왔을 때 함수의 리턴값이 무엇이 되어야 하는지 2. 특정 기간 동안의 가격 변화가 주어졌을 때, 그 주식 한 주를 한번 사고 팔아 얻을 수 있는 최대 수익을 계산하는 알고리즘을 만들어 보세요 질문 ex) 가격 변화가 어떻게 주어지는지 : 파이썬 리스트 형태로 원화 형태로 가격(숫자)이 주어짐 (0번 인덱스가 가장 이전 시간, 그리고 순차적으로 해서 마지막 인덱스가 가장 나중 시간) output : [최대수익, 언제 샀는지, 언제 팔았는지에 대한 인덱스 번호] de.. [기타] 릿코드 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] .. 이전 1 2 3 4 ··· 16 다음