들어가며백준 1647번 '도시 분할 계획' 문제는 최소 신장 트리(MST)의 성질을 활용한 흥미로운 문제입니다. 핵심 아이디어는 전체 그래프에서 MST를 만든 후, 가장 비싼 간선 하나를 제거하면 두 개의 연결된 마을로 나눌 수 있다는 점입니다.문제 분석📋 문제 요약시간 제한: 2초 | 메모리 제한: 256MB | 정답률: 49.164%N개의 집과 M개의 길이 있는 마을을 두 개의 마을로 분할각 마을 내에서는 모든 집이 연결되어야 함남은 길의 유지비 합을 최소화🎯 핵심 통찰마을을 두 개로 나누기 = MST에서 간선 하나 제거하기왜 이 방법이 최적일까요?MST는 N-1개의 간선으로 모든 정점을 연결MST에서 간선 하나를 제거하면 정확히 두 개의 트리가 생성가장 비싼 간선을 제거해야 남은 비용이 최소해결..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/92343문제2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 ..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/340199문제민수는 다양한 지폐를 수집하는 취미를 가지고 있습니다. 지폐마다 크기가 달라 지갑에 넣으려면 여러 번 접어서 넣어야 합니다. 예를 들어 지갑의 크기가 30 * 15이고 지폐의 크기가 26 * 17이라면 한번 반으로 접어 13 * 17크기로 만든 뒤 90도 돌려서 지갑에 넣을 수 있습니다. 지폐를 접을 때는 다음과 같은 규칙을 지킵니다.지폐를 접을 때는 항상 길이가 긴 쪽을 반으로 접습니다.접기 전 길이가 홀수였다면 접은 후 소수점 이하는 버립니다.접힌 지폐를 그대로 또는 90도 돌려서 지갑에 넣을 수 있다면 그만 접습니다.지갑의 가로, 세로 크기를 담은 정수 리스트 wallet과..

머리글2021 KAKAO BLIND RECRUITMENT의 합승 택시 요금을 풀면서 무지와 어피치가 합승을 할 수 있다는 점에 주목하여 플로이드-워셜 알고리즘을 사용했지만, 효율성 테스트에서 낮은 점수를 받았다. 이를 계기로 다익스트라 알고리즘과 플로이드-워셜의 차이를 다시 정리하고, 각 알고리즘의 적절한 사용 전략을 세울 필요성을 느꼈다.다익스트라(Dijkstra) 알고리즘은 하나의 정점에서 출발하여 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이고, 플로이드-워셜(Floyd-Warshal) 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.Dijstra vs FloydWarshall출처 : https://loosie.tistory.com/146다익스트라(Dijkstra..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/120866문제다음 그림과 같이 지뢰가 있는 지역과 지뢰에 인접한 위, 아래, 좌, 우 대각선 칸을 모두 위험지역으로 분류합니다.지뢰는 2차원 배열 board에 1로 표시되어 있고 board에는 지뢰가 매설 된 지역 1과, 지뢰가 없는 지역 0만 존재합니다.지뢰가 매설된 지역의 지도 board가 매개변수로 주어질 때, 안전한 지역의 칸 수를 return하도록 solution 함수를 완성해주세요.내 답안def solution(board): answer = 0 bomb = [] n = len(board) #폭탄 찾기 for i in range(n): for ..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/120907문제덧셈, 뺄셈 수식들이 'X [연산자] Y = Z' 형태로 들어있는 문자열 배열 quiz가 매개변수로 주어집니다. 수식이 옳다면 "O"를 틀리다면 "X"를 순서대로 담은 배열을 return하도록 solution 함수를 완성해주세요.내 답안def solution(quiz): return ["O" if eval(i.split("=")[0]) == int(i.split("=")[1]) else "X" for i in quiz]남의 풀이def solution(quiz): answer = [] for q in quiz: p, a = q.split("=") ..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/120882문제영어 점수와 수학 점수의 평균 점수를 기준으로 학생들의 등수를 매기려고 합니다. 영어 점수와 수학 점수를 담은 2차원 정수 배열 score가 주어질 때, 영어 점수와 수학 점수의 평균을 기준으로 매긴 등수를 담은 배열을 return하도록 solution 함수를 완성해주세요.내 답안def solution(score): # 각 학생의 영어와 수학 점수의 평균 계산 avg = [sum(i)/2 for i in score] # 평균을 기준으로 점수가 높은 순서대로 정렬 sorted_avg = sorted(avg, reverse=True) answer = [] ..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/120894문제영어가 싫은 머쓱이는 영어로 표기되어있는 숫자를 수로 바꾸려고 합니다. 문자열 numbers가 매개변수로 주어질 때, numbers를 정수로 바꿔 return 하도록 solution 함수를 완성해 주세요.내 답안def solution(numbers): answer = 0 c = dict(zip(["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])) for i in c.keys(): numbers = nu..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/120890문제정수 배열 array와 정수 n이 매개변수로 주어질 때, array에 들어있는 정수 중 n과 가장 가까운 수를 return 하도록 solution 함수를 완성해주세요.포인트이 문제의 핵심은 두 가지입니다. 첫 번째는 주어진 n과의 차이(절대값)가 가장 작은 원소를 찾는 것이고, 두 번째는 그러한 원소가 여러 개일 경우 더 작은 값을 반환하는 것입니다.내 답안def solution(array, n): # 주어진 배열에서 n과 가장 가까운 수 찾기 # 거리가 같은 경우 더 작은 수 반환 return min(array, key=lambda x: (abs(x - n), ..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/120852?language=python3문제소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.포인트이 문제는 수학적 이해와 알고리즘 설계 능력을 동시에 요구합니다. 주어진 수를 가능한 작은 소수부터 차례로 나누어 가며 소인수를 추출하는 과정을 통해, 반복문과 조건문 사용법을 숙달할 수 있습니다.내 답안def solution(n): ans..