알고리즘

MST란?신장 트리 (Spanning Tree)신장 트리(Spanning Tree)란 "무방향" 연결 그래프에서 사이클 없이 모든 정점을 연결하는 트리를 말한다. 아래 그림의 형태를 말하며, 신장 트리는 여러개 존재할 수 있다. 신장트리 특징n개의 정점일때, n - 1개의 간선을 가진다.사이클을 이루지 않는다.최소 신장 트리 (MST, Minimum Spanning Tree)MST는 최소 비용 신장 트리를 뜻하며 그래프에서 모든 정점을 연결하되, 간선의 가중치 합이 최소가 되는 트리를 말한다. 프림 알고리즘 (Prim Algorithm)정점 기반 알고리즘으로 한 정점에서 시작하여 가중치가 낮은 간선을 선택하여 트리를 확장하는 방식.동작 과정시작 정점을 선택하여 MST 집합에 추가한다.MST 집합과 연결된..

문제https://www.acmicpc.net/problem/27921https://level.goorm.io/exam/195037/%EB%8F%99%EC%A0%84-%ED%8D%BC%EC%A6%90/quiz/1 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io 해결 방법이번 문제는 1번 동전 배치 위에 2번 동전 배치를 한 칸씩 이동시켜 동전이 가장 많이 겹치는 경우를 찾으면 되는 문제이다. 유사한 개념으로 CNN에서 Kernel의 stride를 1로 했을때와 비슷하다고 생각할 수 있다. 구현에서 고려해야할 점은 가로, 세로 각각 더 긴 길이만큼 이동시켜야한다. 가로 세로 각각 더 긴 길이만큼 탐색해야하는 이유는, 모든 경우를 탐색하기 위함이다..

문제https://level.goorm.io/exam/43068/1a-%EC%9D%B8%EA%B3%B5%EC%A7%80%EB%8A%A5-%EC%B2%AD%EC%86%8C%EA%B8%B0/quiz/1 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io 해결방법해당 문제를 처음 읽었을때는, BFS로 해결 가능한 문제라고 생각했다. 그러나 입력값의 조건에 의하면 2 * 10^9이기때문에, 이는 무조건 메모리초과가 발생하기때문에 새로운 방법이 필요했다. 문제에서 조건으로 한칸씩이동, 중복이동 가능의 특성을 고려하면 짝수번째 이동했을때는 좌표의 절대값의 합이 짝수번째 칸에 위치하고, 홀수번째 이동했을때는 홀수번째 칸에 위치한다. 이를 코드로 구현하면 시간초..

문제https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해결방법해당 문제는 주어진 2차원 배열에서 중류별 옷의 개수를 구한 후, 경우의 수를 구하면 되는 문제이다.예를 들어, 종류가 [a, b, c] 3개이고 각 [3, 2, 1]개의 옷이 있다고 하면한 종류만 고르는 경우3 + 2 + 1 = 6(a + b + c)두 종류만 고르는 경우3 * 2 + 2 * 1 + 3 * 1 = 11(ab + bc + ac)세 종류만 고르는 경우3 * 2 * 1 = 6(abc)이를 전개하면 abc + ab + bc..

문제https://www.codetree.ai/trails/complete/curated-cards/challenge-glacier/description?page=1&page_size=20 Code Tree | Learning to Code with ConfidenceA super-comprehensive, meticulously arranged Coding Learning Curriculum engineered by Algorithm Experts composed of former International Olympiad in Informatics (IOI) medalists.www.codetree.ai 해결방법해당 문제를 해결하려면 빙하에 둘러쌓여 있지 않은 물의 영역을 구하는 로직이 중요하다. 문제..