개발하는 동그리

주제대표적인 알고리즘 기법(DP vs 다익스트라 vs 완전탐색) 구분하기 ✅ 알고리즘 세 가지 분류분류대표 기법주로 사용하는 상황완전탐색 (Brute Force)백트래킹, DFS, BFS가능한 모든 경우를 직접 탐색해야 할 때 (최대값, 조합 등)동적 계획법 (DP)Memoization, Tabulation중복된 하위 문제가 있고, 최적해를 저장하여 재활용 가능할 때다익스트라 (Dijkstra)우선순위 큐 기반 최단 경로가중치가 있는 그래프에서 최소 거리, 최소 비용 계산 시 ✅  각 기법의 특징 비교항목완전탐색동적 계획법 (DP)다익스트라시간 효율성가장 낮음 (보통 O(2ⁿ), O(n!))중간 (O(N²) ~ O(N×M))높음 (O(E log V))공간 효율성낮거나 중간중간 (DP 테이블 필요)중간 (..

기법알고리즘 기법 [유니온파인드] (Union-Find) 체감 난이도골드 3 설명유니온-파인드(또는 Disjoint-Set)는 서로소 집합(Disjoint Sets)을 효율적으로 관리하는 자료 구조로, 주로 그래프에서 연결성 문제를 해결하는 데 사용됩니다. 이 기법은 다음 두 가지 핵심 연산을 기반으로 작동합니다:Find (루트 찾기): 원소가 속한 집합(트리)의 대표자(루트 노드)를 찾습니다.경로 압축(Path Compression)을 통해 트리의 깊이를 줄여 이후 연산을 더 빠르게 수행할 수 있도록 최적화합니다.Union (집합 병합): 두 집합을 하나로 병합합니다.크기(Size Union) 또는 랭크(Rank Union)를 기준으로 병합하여 트리의 깊이를 최소화합니다.-- 정리 --각각의 리스트에서..

기법메모이제이션 체감 난이도골드 3 설명HashMap에 있으면 꺼내서 계산식에 사용없다면, 계산해서 저장  장점메모이제이션한번 계산한건 저장해두고 필요할 때 꺼내쓸 수 있는 것여러번 계산이 필요할 때, 시간을 단축시킬 수 있다.  코드import java.util.HashMap;public class MemoizationExample { static HashMap memo = new HashMap(); public static int fibonacci(int n) { // 1. 메모에 값이 있으면 반환 if (memo.containsKey(n)) { return memo.get(n); } // 2. 기본 케이스 ..

기법부분 배열 정렬 체감 난이도실버 3 설명ListA 의 startIdx부터 endIdx-1까지의 부분 배열을 정렬합니다.Arrays.sort(ListA, startIdx, endIdx)[ListA]정렬하고자 하는 배열[startIdx]부분 배열의 시작 인덱스입니다. 해당 인덱스는 포함됩니다.[endIdx]부분 배열의 끝 인덱스입니다. 이 값은 포함되지 않으며, endIdx - 1이 실제로 정렬되는 마지막 인덱스입니다.예를 들어, startIdx = 2, endIdx = 5이면, 인덱스 2, 3, 4의 값만 정렬됩니다. 장점기존 배열의 변경: Arrays.sort는 배열을 직접 변경하는 방법입니다.즉, 배열을 새로 반환하는 것이 아니라, 기존 배열에서 지정된 범위만 정렬하여 결과를 제공합니다.이 방식은 ..

기법알고리즘 기법 [비트연산(비트 마스크)] 부분 합 체감 난이도골드 1 설명비트연산을 이용한 부분합 구하기비트마스크는 수열의 각 원소에 대해 포함 여부를 나타내는 이진수입니다. 예를 들어, 수열에 3개의 원소가 있으면, 각 원소를 포함하거나 제외하는 경우는 총 8가지입니다(이진수로 000부터 111까지).각 비트가 1이면 해당 원소를 포함하고, 0이면 제외합니다.배열이 [3, 1, 2]일 때, 모든 부분수열을 비트마스크로 나타내면 다음과 같습니다:비트마스크 000: 아무 원소도 포함하지 않음 → 부분수열 [] (합 = 0)비트마스크 001: 마지막 원소만 포함 → 부분수열 [2] (합 = 2)비트마스크 010: 두 번째 원소만 포함 → 부분수열 [1] (합 = 1)비트마스크 011: 두 번째와 마지막 ..

탐색 알고리즘은 특정한 값(데이터)을 어떤 자료 구조 안에서 효율적으로 찾기 위해 사용하는 알고리즘입니다.탐색 대상은 배열, 리스트, 트리, 해시 테이블 등 다양한 자료구조일 수 있으며, 각 구조에 따라 적합한 탐색 방식이 다릅니다. 탐색 알고리즘의 종류선형 탐색 알고리즘 ( Linear Search Algorithm )원리 : 데이터의 첫 번째 요소부터 하나씩 차례대로 비교하며 원하는 값을 찾는 방법.정렬 여부와 무관하게 사용 가능.시간 복잡도 : O(n) 특징 : 가장 단순하지만 느리고, 데이터가 많을수록 성능 저하.이진 탐색 알고리즘 ( Binary Search Algorithm )원리 : 정렬된 배열에서 중앙값과 타겟 값을 비교하면서 탐색 범위를 절반씩 줄이는 방식.정렬 필요 : 오름차순 또는 내..

완전 탐색 알고리즘 Brute-Force 란? Brute Force는 말 그대로 “무차별 대입 방식“을 의미합니다. 가능한 모든 해답 후보를 하나하나 모두 시도해보는 방법으로, 문제를 해결하는 가장 직관적이면서도 비효율적인 접근 방식입니다. ✅ 개념 및 특징정의 : 가능한 모든 해를 전부 탐색하여 정답을 찾음전략 : 논리적인 계산 없이 모든 경우를 대입시간 복잡도: 일반적으로 매우 높음 (O(n), O(n^2), O(2^n)특징 :구현이 매우 간단입력이 적은 경우 유용함항상 정답을 찾을 수 있음 (단, 시간이 오래걸림)최적의 알고리즘은 아님 ✅ 사용 조건더 효율적인 해결책이 존재하지 않을 때가능한 모든 해를 확인해볼 필요가 있을 때문제의 입력 크기가 작아서 탐색이 부담되지 않을 때완전한 탐색이 요구되는 ..

탐욕 알고리즘(Greedy Algorithm) 이란? Greedy Algorithm(탐욕 알고리즘)은 문제를 해결하는 데 있어 매 순간마다 가장 좋아 보이는 선택(최적의 선택)을 하는 방식입니다. 전체 문제 해결을 위해 가능한 선택지 중 그 순간 최선의 선택을 반복하여 결과를 도출합니다.이 알고리즘의 핵심은 “지금 가장 좋아 보이는 선택이 전체적으로도 최적의 결과로 이어진다”는 믿음에 기반합니다. ✅ 탐욕 알고리즘의 절차 1. 선택 절차 (Selection Procedure) 현재 상황에서 가장 최적인 선택을 한다. 예를 들어, 가장 작은 비용, 가장 높은 가치 등을 기준으로 결정한다. 2. 적절성 검사 (Feasibility Check) 선택한 값이 문제의 조건을 만족하는지 검사한다. 조건을 만족하지 ..

빅오(Big-O) 표기법으로 알아보는 시간 복잡도의 모든 것⏱ 시간 복잡도(Time Complexity)란?시간 복잡도는 알고리즘이 입력값(Input)의 크기(n)에 따라 수행 시간(연산 횟수)이 어떻게 변하는지를 나타내는 지표입니다.즉, 어떤 코드를 작성했을 때 데이터의 양이 증가하면 실행 시간도 어떻게 변할지를 예측할 수 있도록 도와주는 개념입니다. 🧮 시간 복잡도 표기법: Big-O, Big-Ω, Big-θ시간 복잡도는 주로 다음과 같은 세 가지 수학적 표기법으로 표현됩니다.표기법의미설명표기법의미설명Big-O (O)최악의 경우가장 느릴 수 있는 경우의 실행 시간을 나타냅니다. 일반적으로 알고리즘 분석에서 가장 많이 사용됩니다.Big-Ω (Omega)최선의 경우가장 빠르게 종료될 수 있는 경우를 나..