코딩 연습장

3197. 백조의 호수 (G2) boj.kr/3197 더보기 Graph + DisjointSet, O(NM * a(K)) 모든 영역을 라벨링하여 큐에 넣은 뒤, 백조가 속한 두 영역이 합쳐질 때까지 한 칸씩 BFS 17406. 배열 돌리기 4 (G5) boj.kr/17406 더보기 Permutation + Simulation, O(K! * KNM) 주어진 쿼리의 순서를 바꿔가며 회전을 수행한 후 배열의 값을 계산 6593. 상범 빌딩 (G4) boj.kr/6593 더보기 Graph, O(T * LRC) 단순 3차원 BFS, 채점 시간을 보니 테스트케이스가 다소 부실하지 않나 생각 2636. 치즈 (G5) boj.kr/2636 2638. 치즈 (G4) boj.kr/2638 더보기 Graph, O(K * N..

백준 11726번 - 2xn 타일링입니다. https://www.acmicpc.net/problem/11726 DP를 공부했다면 한 번쯤 봤을 문제입니다. 상당히 간단합니다. N=1일 때부터 하나씩 채워나갑시다. 구분하기 편하게 알록달록 색을 넣었습니다. 청색, 황색 블럭은 기존에 타일링에 이용했던 모양, 녹색 블럭은 n이 증가함에 따라 새롭게 추가된 모양입니다. 이런 규칙으로 구해보면 N 출력 1 1 2 2 3 3 4 5 5 8 6 13 7 21 8 34 9 55 ... 1, 2, 3, 5, 8, 13, ... 어디서 많이 본... 피보나치네요. 그림그리는게 문제 푸는 것보다 오래 걸린 문제네요. 수고하세용 :)

오랜만의 글 이네요. 백준 5549번 - 행성 탐사입니다. https://www.acmicpc.net/problem/5549 전형적인 구간합 문제 입니다. N x M 크기의 행성의 지도와, 조사 대상 영역 K개 각각의 양 끝 좌표가 주어집니다. 행성을 한 번 탐사하기 위해 걸리는 시간은 O(NM), 즉 모든 K에 대해 재탐사를 수행한다면 시간 복잡도는 O(KNM)이 됩니다. 따라서 탐사는 재탐사는 불가능합니다. 한 번의 탐사 결과를 기억해서 재활용합시다. 간단하게 (1, 1)부터 시작해서 (X, Y)까지 탐사 결과를 dp[ X ][ Y ]에 저장합니다. 이제 (X1, Y1)부터 (X2, Y2),까지의 탐사 결과는 구간합(prefix-sum)을 이용하여 쉽게 구할 수 있습니다. 위와 같이 N x M이 4구..

백준 1915번 - 가장 큰 정사각형입니다. https://www.acmicpc.net/problem/1915 알고리즘 스터디에서 풀었는데, 반례를 못 찾아서 상당히 고전했습니다. 0과 1로 구성된 n x m 사이즈의 배열중에서 1로만 이루어진 가장 큰 정사각형을 찾는 문제입니다. 예를 들어 위와 같은 배열이 주어졌다면 이 배열에서 가장 큰 크기의 정사각형의 크기는 3x3입니다. 주어진 배열을 탐색하면서 정사각형을 찾으면 되겠네요. 1x1 크기의 정사각형을 찾으려면 어떻게 해야 할까요? → 한 개의 1을 찾으면 됩니다. 그럼, 2x2 크기의 정사각형을 찾으려면 어떻게 해야 할까요? 2x2 크기의 빨간 사각형 안에 있는 모든 값이 1이면 됩니다. 간단하게 시각화 해봅시다. 4칸 중에 가장 작은 값을 찾아서..