🔗 Problem Link 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr❔Thinking상자를 열어서 해당 상자 안에 있는 숫자에 해당하는 상자를 연속적으로 열어나간다.한번에 열 수 있는 상자의 수를 기록하고, 더이상 열 수 있는 상자가 없을 때까지 상자를 선택하여 연다.한번에 연 상자들을 그룹화할때, 두 개의 그룹의 상자 수를 최대로 한 경우를 반환한다. 그룹이 하나라면 0이다.💻Solutiondef solution(cards): answer = [] visited = [False] * len(cards) def dfs(num:int): cnt = 0 ..

무(無)방향 그래프 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. find함수는 해당 노드의 root 노드를 찾는 함수이다. union은 두 노드가 속한 집합을 합치는 함수이다. 만약 root 노드가 같다면, 이는 사이클이 존재함을 의미한다. def find(x, parent): if x != parent[x]: parent[x] = find(parent[x], parent) return parent[x] def union(a,b,parent): a = find(a, parent) b = find(b, parent) parent[max(a,b)] = min(a,b) 방향 그래프 방문 여부를 확인하는 visited, 현재 탐색 경로를 나타내는 stack을 노드의 개수만큼 정의한다. 모든 노드에 대해..

🔗 Problem Link 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net ❔Thinking N명의 사람에 대한 친구관계가 주어질 때, 베이컨 법칙에 따른 총합이 제일 적은 사람을 반환한다. 💻Solution 1. 플로이드-워셜을 활용한 풀이 import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) graph = [[INF] * (n+1) for _ in range(..

🔗 Problem Link 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❔Thinking 출발지, 도착지가 적힌 ticket이 주어질 때, 모든 여행지를 방문하는 여행 경로를 반환한다. 💻Solution from collections import defaultdict def solution(tickets): answer = [] # ticket 도착지 내림차순 정렬 tickets = sorted(tickets, key=lambda x: x[1], reverse=True) # 티켓 그래프 생성 tickets_dict = defaultdict(list) f..

🔗 Problem Link Combinations - 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 ❔Thinking 1부터 n까지의 숫자들 가운데 k개를 뽑아 조합한 결과를 반환한다. 💻Solution 1. 조합을 활용한 풀이 from itertools import combinations def combine(self, n: int, k: int): n_list = [i for i in range(1,n+1)] return list(combinations(n_..

🔗 Problem Link Permutations - 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 ❔Thinking 주어진 숫자들을 모두 활용해 만들 수 있는 수열을 리스트에 담아 반환한다. 💻Solution 1. 조합을 활용한 풀이 from itertools import permutations def permute(self, nums): return list(permutations(nums, len(nums))) 2. DFS를 활용한 풀이 - 반복문 def ..