[c++] 백준 21940 가운데에서만나기

❔ 문제https://www.acmicpc.net/problem/21940 🔍 문제 요약입력도시 수 N, 도로 수 MM개의 단방향 도로친구 수 K, 각 친구의 도시 Ci목표: 친구들이 선택 가능한 도시 중, 왕복시간 최대값이 최소가 되는 도시 X를 찾아라! (여러 개일 경우 오름차순 출력) 🔑 해결 전략 : 다익스트라 모든 도시에서 모든 도시로의 최단 거리를 구해둔다각 친구의 도시에서 도시 X까지 + 도시 X에서 다시 친구의 도시까지왕복 시간 = dist[friend][X] + dist[X][friend]친구들 각각의 왕복 시간을 비교해서, 최대 왕복 시간이 최소가 되는 도시를 선택한다! 💙 Step 1: 전체 최단거리 구하기 (다익스트라)vector> min_dist(MAX+1,vector(MAX..

• format_list_bulleted 백준
• · 2025. 6. 8.
• textsms

[c++] 백준 14888 연산자 끼워넣기

❔ 문제백준 14888번 - 연산자 끼워넣기https://www.acmicpc.net/problem/14888 🔍 문제 요약입력 수의 개수 N (2 ≤ N ≤ 11)N개의 수 (1 ≤ Ai ≤ 100)덧셈, 뺄셈, 곱셈, 나눗셈 개수 (총합은 N-1)목표 주어진 수의 순서를 유지하면서 연산자를 끼워넣어 식을 만든다.연산 우선순위 무시하고 앞에서부터 계산만들 수 있는 결과 중 최댓값과 최솟값을 구한다🔑 해결 전략: DFS모든 연산자 조합을 탐색하면서 계산 결과를 저장하고 최대값, 최소값을 갱신하는 방식으로 해결! 💙 Step 1: 초기 설정dfs(nums[0], 1);첫 숫자를 시작 값으로 설정하고다음 숫자부터 연산자를 하나씩 선택해서 적용 💙 Step 3: DFS로 모든 경우의 수 탐색int d..

• format_list_bulleted 백준
• · 2025. 5. 6.
• textsms

[c++] 빠른 입력 - fread로 입력 받기 (수정필요)

🎯 요약 정리cin은 빠르지 않음. sync_with_stdio(false)를 써도 fread에는 밀림.fread는 버퍼를 한 번에 통째로 읽기 때문에 cin보다 최대 수십 배 빠를 수 있음입력 받는 과정에서의 오버헤드를 줄여서 빠르게 처리하는 것. 🔍 코드 분석#define bsz 1 = 48) { ret = ret * 10 + tmp - 48; tmp = read(); } return ret;} 🔹 #define bsz 1 bsz는 버퍼 크기를 정하는 건데, 1 는 2의 14승 = 16,384 바이트 (16KB) 를 의미.즉, 한 번에 16KB만큼 입력을 미리 읽어놓겠다는 뜻버퍼의 크기를 몇으로 하든 상관은 없지만, 너무 작지만 않으면 되고 너무 크지만 않으면 된다. 크기를 키우기 전에 ..

• format_list_bulleted 공부/c++
• · 2025. 5. 5.
• textsms

[c++] 15681 트리와쿼리

❔ 문제https://www.acmicpc.net/problem/15681🔍 문제 요약입력정점 수 N, 루트 정점 R, 쿼리 수 Q 트리 간선 N-1개 (양방향) 쿼리 Q개 (U: 서브트리 루트)출력각 쿼리마다 정점 U를 루트로 하는 서브트리의 크기 출력 ⛔️ 틀린 코드 분석 ❌ 잘못된 접근 코드 1 (Union-Find + 자식 -> 부모 역추적 방식// 15681_트리와쿼리#include#include#includeusing namespace std;#define MAX 100001int union_find[MAX];int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); //트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q ..

• format_list_bulleted 백준
• · 2025. 5. 4.
• textsms

[c++] 15686 치킨배달

❔ 문제https://www.acmicpc.net/problem/15686 🔍 문제 요약입력: N : N × N 크기의 도시 (2 ≤ N ≤ 50)M: 선택할 치킨집 최대 개수 (1 ≤ M ≤ 13)도시 정보 (0 == 빈칸, 1 == 집, 2 == 치킨집)목표: 치킨집 중 M개를 선택했을 때, 도시의 치킨 거리의 최솟값을 구하기⛔️ 틀린 생각 처음에는 단순히 치킨거리의 합이 작은 순서대로 M개를 선택 했는데, 이는 최적의 해를 보장하지 않았다.- 반례4 21 1 0 20 0 2 02 0 0 00 0 0 0답은 4인데 위의 논리로 풀면 5가 나온다. 🔑 해결 전략: 브루트포스 + 조합 탐색모든 치킨집 조합 중 M개를 선택하여, 각 조합마다 도시의 치킨 거리를 계산하고 최솟값을 저장 💙 Step 1:..

• format_list_bulleted 백준
• · 2025. 5. 3.
• textsms

[C++] next_permutation & prev_permutation

📌 개요C++의 헤더에는 순열을 생성하는 두 가지 함수가 있다next_permutation: 사전순 다음 순열을 생성prev_permutation: 사전순 이전 순열을 생성조합/순열 문제에서 굉장히 자주 쓰이며, 특히 비트마스크 조합 탐색과 찰떡궁합이다. 🧠 기본 원형bool next_permutation(Iterator first, Iterator last);bool prev_permutation(Iterator first, Iterator last);현재 순열을 기준으로 다음 / 이전 순열을 생성더 이상 만들 수 있는 순열이 없으면 false 반환 ✅ 예제 1: 숫자 순열 전체 출력vector v = {1, 2, 3};do { for (int x : v) cout 결과: 1 2 3 → 1 ..

• format_list_bulleted 공부/c++
• · 2025. 5. 3.
• textsms