🔗 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 (0,0)에서 (n,n)으로 가는 경주로를 건설할 때, 최소비용의 도로 건설비용을 반환한다. 직선도로는 100원, 방향이 바뀌는 구간(코너)는 500원의 비용이 든다. 💻Solution from collections import deque def solution(board): dx = [-1,1,0,0] dy = [0,0,-1,1] def bfs(board, dir): n = len(board) dp = [[int(1e9)]*n for _ in range(n)] d..

🔗 Problem Link 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ❔Thinking 배추밭과 배추의 위치가 주어질 때, 배추를 보호하는 최소한의 배추흰지렁이 수를 반환한다. 배추흰지렁이는 인접한 모든 배추를 보호할 수 있다. 💻Solution import sys from collections import deque input = sys.stdin.readline dx = [-1,1,0,0] dy = [0,0,-1, 1] T = int(input()) for _ in range(T): M, N, K = map(in..

🔗 Problem Link 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❔Thinking A,B 두 사람이 S지점에서 출발하여 각자의 집 C,D로 가는 택시 합승 최소 비용을 반환한다. (합승하지 않을 수 있다.) 💻Solution def solution(n, s, a, b, fares): INF = int(1e9) answer = INF # 2차원 그래프 생성 graph = [[INF] * (n+1) for i in range(n+1)] # 그래프 초기화 for i in range(1,n+1): for j in range(1, n+1): if i ==..

🔗 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 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ❔Thinking 한 글자를 의미하는 '?'를 포함하는 쿼리가 여러개 주어질 때, 각 쿼리가 words의 몇 단어와 매치되는지를 반환한다. 💻Solution 1. 이진탐색을 활용한 풀이 from bisect import bisect_left, bisect_right def solution(words, queries): answer = [] word_list = [[] for _ in range(100001)] word_list_reversed = [[] for _ in range(1..