🧬 Programmers 301649번 - 대장균 개체 크기 분류하기 📍 문제 요약ECOLI_DATA 테이블에서 대장균 개체를 크기 내림차순으로 정렬상위 0%~25% → 'CRITICAL'26%~50% → 'HIGH'51%~75% → 'MEDIUM'76%~100% → 'LOW'ID와 분류명(COLONY_NAME)을 출력하고, ID 오름차순으로 정렬🧠 필요한 SQL 문법문법 목적문법사용 목적NTILE(4)데이터를 4등분해서 그룹 번호 부여 (1~4)CASE WHEN그룹 번호를 읽어, 분류 이름(CRITICAL 등)으로 변환ORDER BY최종 결과를 ID 기준으로 정렬🛠 SQL 쿼리문SELECT ID, CASE NTILE(4) OVER (ORDER BY SIZE_OF_COLONY DES..

1. std::map (Red–Black Tree 기반)🔍 특징내부 구조: 균형 이진 탐색 트리(대부분 Red–Black Tree)키 정렬: 항상 오름차순(기본)으로 정렬된 상태를 유지메모리 구조: 노드 단위 할당(포인터 2개, 균형 정보 등 포함)중복 키: 허용하지 않음 (std::map), 중복 허용하려면 std::multimap📈 주요 연산 시간 복잡도연산복잡도검색 find()O(log N)삽입 insert()O(log N)삭제 erase()O(log N)인덱스 operator[]O(log N)✅ 장점정렬된 순회: begin()→end()로 순회하면 키가 오름차순범위 검색 지원: lower_bound, upper_bound 등으로 키 구간 탐색예측 가능한 성능: 트리 깊이 제한으로 최악 상황도 ..

🔍 문제 요약문제 링크: 백준 9177주요 태그: 문자열, 다이나믹 프로그래밍탁자 위에 놓인 두 문자열 순서를 흐트러뜨리지 않고 섞어서(target interleaving) 세 번째 문자열을 만들 수 있는지 판별는 문제💡 문제 분석“두 문자열을 순서를 유지하면서 섞는다”는 Interleaving String 문제T개의 데이터 세트가 주어지고, 각 세트마다 first second word가 공백으로 구분되어 들어온다.word의 길이가 first + second와 다르면 무조건 불가능하다.접두사 기준의 DP로 자주 풀린다.dp[i][j]를 first의 앞 i글자, second의 앞 j글자를 섞어 word의 앞 (i+j)글자를 만들 수 있는지 여부로 정의. 🔑 아이디어2차원 DP상태:dp[i][j] = ..

🔍 DFS vs BFS 완벽 비교주제: DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)의 차이와 사용처주요 키워드: DFS, BFS, 그래프 탐색, 경로, 큐, 스택💡 개념 정리✅ DFS (Depth-First Search)한 방향으로 "끝까지" 들어가는 탐색 - 깊이 우선 탐색스택 기반 (보통 재귀)재귀 또는 명시적 스택으로 구현void dfs(int node) { visited[node] = true; for (int next : graph[node]) { if (!visited[next]) dfs(next); }}✅ BFS (Breadth-First Search)"가까운 노드부터" 차례로 탐색 - 너비 우선 탐색큐(Queue) 기반레벨 순서 탐색이 필요할 때 유용..

🔍 DFS 백트래킹 패턴 완벽 정리주제: DFS(깊이 우선 탐색)에서 자주 사용되는 visited 배열 처리 방식과 백트래킹 전략주요 키워드: DFS, 백트래킹, visited 배열, 그래프 탐색💡 DFS ,  백트래킹이란?DFS(Depth-First Search)는 그래프, 트리 탐색의 대표적인 알고리즘으로, 깊이 우선으로 한 방향 끝까지 탐색하는 방식이다.백트래킹은 DFS 탐색 중, 특정 조건을 만족하지 않거나 탐색이 종료되었을 때 이전 상태로 되돌아가며 다른 경로를 탐색하는 기법이다.❗️ DFS에서 visited[] 배열을 어떻게 관리하느냐에 따라 구현이 깔끔하고, 오류 없는 코드가 될 수 있다.🧩 DFS visited 처리 방식 ①: 내부 백트래킹 방식void dfs(int node, int..

🔍 문제 요약문제 링크: 백준 13023번 - ABCDE주요 태그: DFS, 백트래킹, 그래프 탐색💡 문제 분석총 N명(0 ~ N-1)이 참가한 알고리즘 캠프에서 친구 관계가 M개 주어진다.관계 A-B-C-D-E와 같은 연속된 5명의 친구 관계가 존재하는지 확인해야 한다.A-B B-CC-DD-E🔑 아이디어DFS를 활용하여 모든 노드에서 깊이 4까지 탐색한다. (간선 4개)경로 탐색 중 동일한 사람을 중복해서 방문하지 않기 위해 visited[] 배열을 활용깊이 4에 도달하면 즉시 종료하도록 flag 사용탐색을 마친 후에는 visited[]를 원래 상태로 복구 (백트래킹)🧩 풀이 전략인접 리스트 방식의 그래프 방식으로 푼다.모든 노드에서 DFS를 시작하면서 깊이 0부터 탐색방문한 노드는 visite..

🔍  문제 요약문제 링크: 백준 9419 - 프로그래밍 대회 전용 부지상근이의 목표상근이는 해마다 땅을 하나씩 사면서, 모든 땅을 최소 비용으로 사들이려 한다.1년이 지날 때마다 땅값은 두 배로 상승하므로, 더 비싼 땅일수록 먼저 사야 전체 비용이 줄어든다.조건매년 1개 땅만 구입 가능 (1년 후부터)가격은 2 × L × t^t로 증가 (L은 땅값, t는 구매한 해의 번호)총 보유 금액: 5,000,000 억원목표: 주어진 테스트 케이스마다 땅을 모두 구입할 수 있는지, 최소 비용을 출력한다.💡 문제 분석가격은 매년 기하급수적으로 증가하기 때문에, 비싼 땅부터 먼저 구매해야 최적의 해법각 테스트 케이스는 0으로 끝나며, 최대 40개의 땅 → O(n log n) 정렬 후 계산 가능단위가 억이고, 총 예..

🔍 문제 요약문제 링크: 백준 11059번 - 크리 문자열주요 태그: 문자열, 누적합, 슬라이딩 윈도우, 브루트포스 최적화💡 문제 분석숫자로 이루어진 문자열 S가 주어진다.연속된 부분 문자열 중 길이가 짝수이고,앞 절반의 합 == 뒤 절반의 합인 것을 '크리 문자열'이라 정의한다.모든 크리 문자열 중 가장 긴 길이를 출력해야 한다.🔑 아이디어모든 짝수 길이의 부분 문자열을 확인하며,각 부분을 앞/뒤 절반으로 나누고, 그 합을 비교해야 한다.부분합을 반복해서 계산하면 O(n³) 시간복잡도가 발생하므로,누적합(Prefix Sum) 기법을 활용해 각 구간의 합을 O(1)로 계산하도록 최적화한다.🧩 풀이 전략문자열 S의 각 숫자를 정수형으로 바꾼 뒤 누적합 배열을 만든다.prefix[i] = S[0] +..