시간 제한 - 2s 메모리 제한 - 512MB 풀이 기존 벽 부수고 이동하기 1, 2, 3과는 다른 형식의 문제입니다. 정석대로라면 BFS, DFS를 통한 그래프 탐색문제로 풀 수 있지만, 그래프 탐색을 쓰지않은 풀이는 없는 것 같아서 이런 방법도 있다고 알려드리기 위해 포스팅합니다. 1. N * M 행렬을 순회하며 입력을 받으며 입력 값을 체크합니다. 2. 만약 입력 값이 0이라면 이미 지나왔으며 인접한 위, 왼쪽을 체크해 0인지 확인하고, 0이라면 두 좌표를 union 연산으로 묶어주고 두 그룹의 크기를 합쳐줍니다. 3. 입력이 끝난 시점에서 각 노드는 그룹이 완성된 상태입니다. 4. 다시 입력받은 배열을 순회하며 0이라면 그대로 출력, 1이라면 상하좌우 그룹의 크기를 더한 후 10을 나눈 나머지를 ..

시간 제한 - 1s 메모리 제한 - 256MB 풀이 1. 부분 수열의 합 / 부분 수열의 길이 = 해당 부분 수열의 평균임을 이용해 풀이 (N까지의 누적합 / N = 평균) 2. (N까지의 누적 합 - x까지의 누적 합) / (N - x) = x부터 N까지의 평균 인덱스 0 1 2 3 4 5 6 배열 1 1 1 1 1 1 누적합 0 1 2 3 4 5 6 평균 0 1 1 1 1 1 1 위 테이블에서 6까지의 평균은 당연히 1이다. 만일 찾으려는 값이 1이라면, 이를 만족하는 구간은 모든 구간인 N * (N + 1) / 2인 21이 나와야 함(1:1, 1:2, 1:3, 1:4, 1:5, 1:6, 2:2, 2:3 ••• 6:6) 3. 누적합을 구하고 평균을 계산해 해당 값이 나온 횟수를 구해준다. 4. 평균을..

당신이 만약 백준 플래티넘 티어에 도전하는 모험가라면 부스터 한개는 남겨놓았길 바란다. 최소 골드 2부터 시작하는 쉽지 않은 알고리즘임에도 불구, 트리를 초기화 및 업데이트하고 누적합만 구하는 accumulator가 된다면, 골1 수문장은 쉽게 돌파할 수 있을 것이기 때문이죠. 세그먼트 트리는 데이터 배열에서 특정 범위에 대한 쿼리를 효율적으로 수행하는 균형 잡힌 이진트리 형태의 자료구조로 트리의 리프 노드는 전체 배열의 단일 요소를 표현하며, 트리 내부의 각 노드는 요소의 범위를 나타냅니다. 트리의 각 내부 노드는 상위 노드가 표현하는 범위의 왼쪽과 오른쪽을 절반씩 나타내는 두 개의 하위 노드를 가지며, 상대적으로 적은 수의 노드로 어레이의 전체 범위를 나타낼 수 있으며 범위 값의 수정과 검색에 있어 ..

시간 제한 - 2s 메모리 제한 - 256MB 풀이 1. 최단경로가 최대가 되기 위해서는 최단경로를 끊어야한다. 최단경로가 아닌 간선을 끊어봐야 최단경로는 그대로이기 때문 2. 최단경로를 구해, 해당 경로에서 거치는 노드를 하나씩 끊고, 다시 최단경로를 구하는 방식으로 최대 값을 구한다. 3. 최단 경로가 여러 개일 때, 현재의 최단 경로만 확인하는게 의미가 있는지? 3.1) 동일한 최단경로가 없을 때(A->B) - A->B가 최단경로이므로, A->B를 끊으면 A->C->B로 최단경로가 1 늘어나며 A-C, C->B 등 최단경로 이외의 간선을 끊어도 결과는 A->B로 같은 걸 확인할 수 있음 3.2) 동일한 최단 경로가 중복되지 않는 경로로 존재할 때(A->G) - A->B->D->G 또는 A->C->E..

시간 제한 - 1s 메모리 제한 - 128MB 풀이 1. 구슬과 추를 활용해 무게를 재는 방법 1.1) 그림 1을 식으로 나타내면 구슬 + 추a + 추b == 추x + 추y ?로 표현 가능 1.2) 그림 2를 식으로 나타내면 구슬 == 추x + 추y ?로 표현 가능 -> 방정식의 성질을 이용해 1.1의 식을 구슬 == 추x + 추y - 추a - 추b와 같이 나타냄으로 두 식을 같게 생각할 수 있음 2. 1번의 추1부터 추n까지의 조합을 이용해 만들 수 있는 무게 중 구슬의 무게가 있으면 비교 가능하다고 판단 가능 입력 추의 수 N, N개의 추 구슬의 수 M M개의 구슬 자료구조 dp 테이블을 만들까했지만 추를 이용해 만들 수 있는 무게의 집합을 표현하기에 set 자료구조가 좋다고 판단함 추n-1개의 se..

시간 제한 - 2s 메모리 제한 - 128MB 풀이 1. 처음에는 무조건 1번을 풀어야 함 2. 최소, 최대 값의 차이가 각 단계의 해가 되기 때문에 Memorization을 사용이 어려움 ex) 10 5 15 0 20 ...의 경우, 10 다음에 5/ 15 어떤 문제를 푸는 것이 최적인지 알기 어렵다. 각 단계까지의 depth, 최대 값, 최소 값을 기준으로 기록하면 최대 1000 * 1000 * 50의 3차원 벡터가 생겨 128MB 메모리를 초과함 3. 따라서 brute force로 진행하되 백트래킹 최적화로 덜 계산하는 편이 좋겠다고 생각함 입력 총 문제의 갯수(N)와 최대-최소 간 기준 값(V) 흥미도 X0 X1 X2 .. Xn 자료구조 각 문제의 흥미도를 담기 위한 int형 배열 로직 1. 맨 ..