문제https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이정석적인 구간합 풀이 (투포인터) 접근법문제를 조금 읽어보면 알 수 있듯, 특정 합(k)을 만족하는 구간을 구하는 문제로 구간합을 구하는 알고리즘을 적용해서 풀 수 있다.처음에 떠올린 방법은 투포인터를 활용해서 구간합 조건을 검색하는 방식이였고, 두번째는 누적합이다.만약 '비내림차순'이 아니라 정렬이 되어 있다는 가정이라면 이분탐색을 활용해도 풀 수 있다. 우선 해당 문제의 조건은 간단하다. 만족하는 구간합이 여러 CASE일 경우 아래 조건에 따..

이전 포스팅에 이어 이번에는 MST 알고리즘을 구현하는 방식 중 하나인 프림 알고리즘에 대해 알아보려 합니다.우선 MST에 대해 다시 한번 짚고 넘어가겠습니다. 📑 MSTMST를 다시한번 간단하게 설명하면 "최소 비용으로 모든 정점을 연결한 트리 구조"입니다.MST도 트리이기 때문에, 트리 구조 특성 상 사이클이 발생하면 안되는데요.이유는 트리는 정점 간 유일한 경로, 최소 연결성이라는 특성이 있기 때문입니다. 이러한 MST를 구하는 방식 중 하나인 크루스칼 알고리즘에 대해서는 아래 포스팅을 참고해주세요.[JAVA] 크루스칼 알고리즘 (Kruskal Algorythm) [JAVA] 크루스칼 알고리즘 (Kruskal Algorythm)최근 알고리즘 문제 풀이를 다시 시작하며 기억에서 희미해져버린 MST ..

최근 알고리즘 문제 풀이를 다시 시작하며 기억에서 희미해져버린 MST 알고리즘에 대해서 정리해볼까 합니다.정리하려는 주된 내용은 아래와 같습니다.❓ MST가 무엇인지, 크루스칼 알고리즘의 구현 및 동작 방식 📑 MST란?MST는 Minimum Spanning Tree의 약자로 최소 신장 트리를 찾기 위한 알고리즘입니다.또한 Spanning Tree(신장 트리)는 간단하게 설명하면 모든 정점을 포함하면서 사이클이 없는 연결 그래프를 의미합니다.더보기왜 사이클이 없어야할까❓ (25.06.21 추가)처음에는 모든 정점이 연결만 되면 된다고 생각했습니다. (이 과정에서 사이클이 생기든 말든지요.)그러나 MST 또한 트리이며, 트리 특성을 생각해보면 사이클이 없어야 합니다.트리에서 한 정점에서 다른 정점으로 가..

백준에서 시뮬레이션 문제를 풀다가 한참을 디버깅하면서 삽질했던 과정을 기록하고자 합니다.. 결론부터 말씀드리자면, double 자료형의 부동소수점 오차로 인한 문제였습니다.추가로 짝수/홀수 구분을 (2&1)로 해야하는데 (2^1)로 하고서는 "왜맞틀"했던 저를 발견할 수 있었습니다..(반성하고 자바의 정석 다시 펼칠게요) 🔗 문제https://www.acmicpc.net/problem/20057문제는 삼성 기출로 유명한 마법사 상어 시리즈입니다. 📝 풀이간단하게 풀이를 설명하자면 달팽이 회전 로직을 구현 후 각 방향에 따른 '위치 및 비율'을 인덱싱하여 구현했습니다.2차원 격자 문제를 많이 풀어봤다면 쉽게 떠올리고 풀 수 있을거라 생각합니다. 조심해야하는 부분은 오른쪽부터 시작하는 달팽이 회전이 아니..