log

📃 문제 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 💻 코드 #include #include #include using namespace std; int N; vector v; stack s; int cnt = 0; int main() { cin >> N; int x, y; for (int i = 0; i > x >> y; v.push_back(y); } ..

📃 문제 https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 왼쪽부터 차례대로 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 www.acmicpc.net 💻 코드 #include #include #include using namespace std; int N; long long bridge[1000001]; long long dp[1000001] = { 0 }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N;..

📃 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 💻 코드 #include #include using namespace std; int N, M; int arr[200001]; int main() { cin >> N >> M; for (int i = 0; i > arr[i]; sort(arr, arr + N); int start = 1; int end = ar..

🔎 백트래킹이란? 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법 → 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아간다 == 가지치기 (가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다!) 백트래킹 기법의 유망성 판단 어떤 값이(어떤 노드가) 해가 될 가능성이 있다면 유망하다고 하며, 유망하지 않은 값에 가지 않는 것을 가지치기라고 한다. 유망하지 않다고 판단되면 그 값의 이전으로 돌아가 다음 값으로 넘어간다. (이전 노드로 돌아가 다음 자식 노드로 간다.) 🔎 DFS vs 백트래킹 vs 분기한정법 DFS 가능한 모든 경로를 깊이 우선으로 탐색하는 것 (한 방향으로 갈 수 있는 경로를 먼저 탐색) → 현재 정점과 인접한 간선들을 모두 검사하여 아직 ..