목록알고리즘 (73)
체뚱로그
풀이 시간: 01:38:37 시간 복잡도: O(M+N*N+N) = O(N^2) 단방향 경로 추가 O(M) + while문은 큐가 비어있을 때까지 반복하므로, 최악의 경우 모든 도시를 방문 O(N) * for문은 현재 도시와 연결된 도시 확인, 최악의 경우 한 도시에 모든 도시가 연결 O(N) + result 값 출력, 최대 N이므로 O(N) 공간 복잡도: O(N*M+N) = O(NM) one_way_route 크기 O(M) + result의 최대 크기는 N이므로 O(N) + shortest_route 크기 O(N) 참고 자료: https://kimjingo.tistory.com/57 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 ..
풀이 시간: 02:03:35 시간 복잡도: O(HWK) -> (4 + 8) * V * K = 12 * (H*W) * K 공간 복잡도: O(HWK) -> 2차원 배열 grid, 3차원 배열 visited의 공간 복잡도 참고: https://yabmoons.tistory.com/48 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. X X X X 말 X X X X 근데 원숭..
풀이 시간: 04:29:55 시간 복잡도: O(W*H + V + E) = O(W*H) - W*H: 이중 for문을 통해 grid 배열에 값 입력 - V: 그래프 정점의 수 (V = W*H) - E: 그래프 간선의 수 (각 정점은 최대 6개의 인접한 정점 가질 수 있음, 최대 E = 6*W*H) 공간 복잡도: O(1 + V) = O(W*H) - 1: grid[102][102] 정적 배열 크기 고정 - V: 그래프 정점의 수 (최대 V = W*H) 참고 https://ongveloper.tistory.com/155 https://hyeo-noo.tistory.com/335 https://khu98.tistory.com/277 https://currygamedev.tistory.com/10 문제 부유한 집안의..
풀이 시간: 01:54:53 시간 복잡도: O(NRCk) -> O(NRC) (k = 4이므로(?)) 공간 복잡도: O(RC) 참고: https://yabmoons.tistory.com/198 문제 봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다. 폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다. 봄버맨..
풀이 시간: 01:59:18 시간 복잡도: O(nm) → 총 n * m개의 (n, m) 쌍을 계산 공간 복잡도: O(nm) → 2차원 배열 참고 https://kmiiiaa.tistory.com/20 https://sdy-study.tistory.com/210 문제 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다. 각 구간은 한 개 이상의 연속된 수들로 이루어진다. 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다. 정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다. N개의 수들이 주어졌을 때, 답을 구하는..
풀이 시간: 01:58:30 시간 복잡도: O(21n) → O(n) : 숫자의 개수 n개와 가능한 결과의 범위가 0~20 (상수항 무시) 공간 복잡도: O(21n) → O(n) : 2차원 벡터 크기 n * 21 (상수항 무시) 참고: https://velog.io/@lacram/C-백준-5557번-1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서..