알고리즘/백준
-
[백준] 10999번 구간 합 구하기2알고리즘/백준 2025. 7. 15. 01:44
문제 링크https://www.acmicpc.net/problem/10999 문제 해설이 문제는 구간 합 구하기의 변형된 버전이다. 값을 특정 값 하나만 갱신하는 것이 아니라 주어진 구간을 갱신한다. "구간 합 구하기"에서 나온 로직을 조금 응용하는 정도로는 이 문제를 풀 수 없다. 시도해보면 시간 초과가 뜰 것이다. 업데이트 구간이 처음부터 끝까지일 경우 O(N)의 시간 복잡도가 나올 것이기 때문이다. 백준 블로그를 참고해도 된다. 그림으로 하나하나 뜯어서 설명할 자신이 없어 추상화된 설명이 진행될 것이다. 여기에서는 지연된 전파라는 개념을 사용한다. 지연이라는 단어를 쓰는 이유는 노드를 순회할 때 관련 서브 트리를 한 번에 전부 갱신하지 않기 때문이다. 전파는 다음 순회 때 방문하는 노드가 비로소 갱..
-
[백준] 2042번 구간 합 구하기알고리즘/백준 2025. 7. 10. 16:45
문제 링크https://www.acmicpc.net/problem/2042 문제 해설기본 개념세그먼트 트리의 개념을 정확하게 아는 것이 중요하다. 백준 블로그에 자세한 설명이 있지만 내 방식으로 이해한 걸 풀어서 정리해본다. 백준 북도 참고하길 바란다. 세그먼트 트리를 만드는 시작은, 리프 노드를 배열의 값으로 초기화하는 것이다. 우리가 사용할 트리는 데이터 기준으로는 완전(complete) 이진 트리로 마지막 레벨을 제외한 레벨이 모두 가득차 있고 마지막 레벨은 왼쪽 노드부터 연속적으로 채워진 상태이지만 실제로는 포화(perfect) 이진 트리를 사용할 거다. 모든 레벨에 노드가 있고 리프가 모두 같은 레벨인 포화(perfect) 이진 트리로 크기를 잡아두면 레벨(높이, h)를 구해서 트리의 전체 크..
-
[백준] 14503 로봇 청소기알고리즘/백준 2025. 7. 9. 01:12
문제 링크https://www.acmicpc.net/problem/14503 문제 해설문제에 있는 절차 그대로 풀어쓰면 된다. 전체 코드#include using namespace std;using Pair = pair;Pair dirs[] = { {-1,0}, {0, 1}, {1, 0}, {0, -1} };int map[50][50]{};int N, M, start_r, start_c, dir;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M; cin >> start_r >> start_c >> dir; for (int i = 0; i > map[i][j]; int current_r ..
-
[백준] 2573번 빙산알고리즘/백준 2025. 7. 3. 11:17
문제 링크https://www.acmicpc.net/problem/2573 문제 해설코드에 중복 로직이 있다. 실무였으면 함수로 뺐을 테지만 여기선 그냥 놔뒀다. 더 고민해보면 최적화를 할 수 있을 것 같지만, 지금 코드가 그렇다고 성능이 나쁜 건 아니다. 대충 보니까 상위 15% 정도는 된다. 다른 엄청나게 최적화된 코드보다 가독성이 좋다. 읽기 쉬운 글은 덜 전문적으로 보일 수 있으나 이해가 쉬운 것처럼. 전체 코드 #include #include using namespace std;int map[300][300]{};bool visited[300][300]{};int adjacent_row[] = {1, 0, -1, 0};int adjacent_col[] = {0, 1, 0, -1};int N, M..
-
[백준] 2468번 안전 영역알고리즘/백준 2025. 6. 18. 13:56
문제 링크https://www.acmicpc.net/problem/2468 문제 해설단지 번호 붙이기와 많이 비슷하다. 3차 반복문으로 해서 가장 바깥 반복문은 강수량이 0부터 최대값까지 해서 경우의 수를 구한다. 최대값은 100으로 해도 될 수 있는데 굳이 불필요하게 순회하기 싫어서 max_height를 구해 거기까지만 순회하도록 했다. 전체 코드 #include #include using namespace std;array, 100> map;array, 100> visited;int N;void dfs(int row, int col, int height);void init_visited();int adj_row[] = { 1, 0, -1, 0 };int adj_col[] = { 0, 1, 0, -1 ..
-
[백준] 13913 숨바꼭질4알고리즘/백준 2025. 6. 17. 23:55
문제 링크https://www.acmicpc.net/problem/13913 문제 해설쉽게 생각하면 쉽고 어렵게 생각하면 어려운 것 같다. 이게 출력이 모든 경우의 수를 검사하는 게 아니고 하나만 출력하면 되는 거라 어렵지는 않을 거다. 인덱스 경계를 늘 조심하도록 하자! 전체 코드#include #include #include #include #include using namespace std;int N, K;const int MAX_SIZE = 200000;array seconds;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); seconds.fill(-1); queue q; cin >> N >> K; seco..
-
[백준] 5014 스타트 링크알고리즘/백준 2025. 6. 17. 23:50
문제 링크https://www.acmicpc.net/problem/5014 문제 해설숨바꼭질을 풀었다면 어렵지 않다. 기본 원리가 동일하다. 전체 코드#include #include #include using namespace std;int F, S, G, U, D;const int MAX = 1000000;array building;int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); building.fill(-1); queue q; cin >> F >> S >> G >> U >> D; building[S] = 0; q.push(S); while (q.empty() == false) { int current = q.front(); q.pop(); ..
-
[백준] 1697번 숨바꼭질알고리즘/백준 2025. 6. 13. 18:13
문제링크https://www.acmicpc.net/problem/1697 해설seconds 배열 요소가 갱신됐으면 새로운 값으로 갱신되면 안 된다. 새로 갱신되는 값은 기존 값보다 무조건 클 것이기 때문이다. 우리는 최소 값을 구해야 하니까 방문한 요소는 건너뛰어 값을 보호하고 비효율도 예방한다. 그전에는 이런 최소 값을 구할 때 queue를 pair로 선언해 위치값과 거리 값을 같이 관리하는는 걸 선호했지만 이번에는 (x, y) 형태의 좌표에 관한 문제가 아니라 값을 갱신해나가면서 최소 값을 찾는 것이기 때문에 별도의 visited 배열을 두지 않고 하나의 정수형 배열에서 방문/미방문을 구분할 수 있다. 전체 코드#include #include #include using namespace std;in..