알고리즘/백준
-
[백준] 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..
-
[백준] 7569번 토마토알고리즘/백준 2025. 6. 13. 12:37
문제 링크https://www.acmicpc.net/problem/7569 해설3차원 배열로 풀어도 되고 2차원 배열로 풀어도 된다. 나는 2차원 배열로 풀었다. 2차원 배열로 풀 때는 행 인덱스 처리를 잘해줘야 하는 케이스는 행이 바뀔 때 층이 바뀌는 때다. 3차원 배열로는 안 풀어봤지만 층 인덱스가 별도로 있으니 실수할 가능성이 적지만 2차원으로 할 때는 층이 바뀌는 경우를 그냥 지나칠 수 있다(내 얘기). 인접 토마토를 검사에서 가로 세로를 검사할 때 같은 층인 경우에만 탐색을 해야 한다. 코드가 최적화 여지가 있어 보이긴 한데..일단 넘어간다. while (q.empty() == false) { auto [pos, day] = q.front(); auto [n,..
-
[백준] 2644번 촌수 계산알고리즘/백준 2025. 6. 7. 16:20
문제 링크https://www.acmicpc.net/problem/2644 내 코드가 대단히 메모리를 적게 먹거나 코드 길이가 짧은 편에 속하지는 않는다. 그동안 제출된 현황의 코드를 보니까 메모리와 코드 길이 기준으로 대충 상위 30%에는 속한다. 가독성은 더 좋다고 생각한다. 내가 작성해서가 아니라 그냥 평범한 로직이라서 그렇다. #include #include #include using namespace std;int N, M;int p1, p2;vector parents;bool visited[101];queue> q;int main(){ cin >> N; cin >> p1 >> p2; cin >> M; parents.resize(N + 1); for (int i = 0..
-
[백준] 2667번 단지번호 붙이기알고리즘/백준 2025. 6. 1. 02:34
문제 링크https://www.acmicpc.net/problem/2667 해설반복문 돌면서 조건이 맞을 때 dfs() 함수를 호출한다. 일단 호출이 되면 인접한 집을 전부 돌고 나서 처음 호출한 곳으로 리턴한다. dfs() 호출이 끝나면 카운트를 우선 순위 큐(최소 힙)에 저장하고 0으로 초기화하고 이어서 반복문이 수행되도록 한다. 당연한 소리지만 bfs()로도 풀리는 문제다. 메모리 효율이나 속도는 bfs()가 더 좋다.#include #include #include using namespace std;priority_queue, greater> pq;bool map[25 + 2][25 + 2];bool visited[25 + 2][25 + 2];int N;int adj_dir_row[] = { 1,..
-
[백준] 2178번 미로 탐색알고리즘/백준 2025. 5. 30. 23:28
문제 링크https://www.acmicpc.net/problem/2178 로직이 분명히 문제가 없는데 틀렸다고 나오는 게 이해가 안 됐다. 알고 보니 경계 문제였다. 경계는 늘 문제구만. 거리 계산하는 부분을 별도로 배열로 관리하면 채점 상에 나오는 메모리가 (40kb) 정도 절약되지만, 큐를 통해 한 번에 관리하는 게 나는 더 편하다. 처음에는 DFS로 풀어보려다 복잡해질 것 같아 BFS로 거리 계산을 해보려고 하니까 금방 됐다. 경계만 아니었다면.. #include #include using namespace std;queue, int>> q;int N, M;int map[102][102];bool visited[102][102];int dist[102][102];int dir_n[] = { 1, ..
-
[백준] 1260번 DFS와 BFS알고리즘/백준 2025. 5. 30. 19:46
아주 아주 오랜만에 풀다 보니까 사소한 실수들이 있었다. 익숙해지는 수밖에 없겠지. 문제 조건 중에 방문할 수 있는 정점이 여러 개라면 정점 번호가 작은 것부터 순회하라고 했다. 어차피 인덱스 번호 = 정점 번호라서 반복문 돌릴 때 1번부터 하면 된다.#include #include #include using namespace std;void dfs(int start);void bfs();queue q;bool map[1001][1001] = { false };bool dfs_visited[1001] = { false };bool bfs_visited[1001] = { false };int N, M, start;int main(){ cin >> N >> M >> start; for (int i = 0; ..
-
[백준] 구간 합 구하기(2042번)알고리즘/백준 2021. 9. 19. 12:09
문제 링크 풀이 쉬운 문제는 아닙니다. 세그먼트 트리를 이용해야 합니다. 먼저 배열을 통해 살펴보겠습니다. 1. 구간 합 구하기 2. 특정 위치 값 변경 1번의 경우 점화식을 이용해서 푼다면 다음과 같으므로 O(N)입니다. s[0] = a[0]; for (int i = 1; i < n; ++i) { s[1] = s[i-1] + a[i]; } 2번은 a[4] = 3;의 방법으로 이루어지기 때문에 O(1)입니다. 1번이 M번, 2번이 K번 이루어진다면 O(NM + K)입니다. 문제에서 N, M, K는 적은 숫자가 아니기 때문에 O(NM + K)는 충분히 오래 걸릴 수 있습니다. 세그먼트 트리를 이용하면 O((M+K)*log₂N)에 가능합니다. O(NM + K)와 크게 다르지 않은 것처럼 보일 수 있는데, 문..