https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net # 조건 정사각형 모양의 지도가 있다. 1은 집이 있는 곳, 0은 집이 없는 곳 연결된 집의 모임의 단지를 정의하는데, 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다 총 단지수를 출력하고 각 단지에 속하는 집의 수를 오름차순으로 출력하라. # 접근 방법 및 solution 델타 함수를 이용한 dfs를 이용하여 연결된 단지를 체크해준다. 방문한 집들의 값을 0으로 변..

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net # 조건 크기가 NxM 크기인 배열 A 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미 배열은 회전 연산을 수행할 수 있는데 회전 연산은 (r,c,s) 세 정수로 이루어져있다. 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아래 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미 예 - 회전 연산 (3,4,2) 회전 연산이..

https://www.acmicpc.net/problem/17276 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net # 조건 크기가 n x n 인 2차원 정수 배열 X X를 45° 의 배수만큼 시계방향 혹은 반시계방향으로 돌리려고 한다. X를 시계 방향으로 45° 돌리면 아래와 같은 연산이 동시에 X에 적용되어야 한다: X의 주 대각선을 ((1,1), (2,2), …, (n, n)) 가운데 열 ((n+1)/2 번째 열)로 옮긴다. X의 가운데 열을 X의 부 대각선으로 ((n, 1), (n-1, 2), …, (1, n)) 옮긴다. X의 부 대각선을 X의 가운데 행 ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 조건 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임 계단을 밟으면 해당 계단에 쓰여 있는 점수를 얻게 된다. 아래 규칙을 지켜서 얻을 수 있는 점수의 최댓값을 구하라 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net # 조건 NxM 크기의 배열로 표현되는 미로 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸 (1,1) 에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸 수를 출력 # 접근 방법 BFS를 통하여 탐색을 진행한다. Queue에 넣어주며 방문기록을 현재 좌표+1로 해준다. 간선의 가중치가 모두 같은 그래프로 생각할 수 있기 때문에 bfs를 이용한다면 최단 경로를 바로 구할 수 있다. import sys sys.s..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net # 조건 흑백 영상을 압축하여 표현하는 데이터 구조 쿼드 트리 흰 점을 0, 검은 점을 1로 표현하는 2차원 배열 모두 0으로만 되어 있으면 압축 결과 '0' 모두 1로만 되어 있으면 압축 결과 '1' 섞여 있다면, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 -> 4개의 영상으로 나누어 압축 압축한 결과를 차례대로 괄호 안에 묶어서 표현 2^i 개를 하나로 압축 가능하며 하나로 ..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net # 조건 이중 우선순위 큐는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료구조 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제 데이터를 삽입하는 연산과 데이터를 삭제하는 연산 사용 데이터를 삭제하는 연산은 우선순위가 가장 높은 것을 삭제하는 것과 우선순위가 가장 낮은 것을 삭제하는 것으로 나뉜다...

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net # 조건 수직선 위에 N개의 좌표 X1, X2, ... Xn Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. 1

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net # 조건 2xN 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램 작성 방법의 수를 10,007로 나눈 나머지를 출력하라. # 접근 방법 규칙을 찾는 것이 좋을 것 같다. n = 1 인 경우 1가지 n = 2 인 경우 2가지 n = 3 인 경우 3가지 n = 4 인 경우 5가지 n = 5 인 경우 8가지 f(n) = f(n-2) * 2 + f(n-3) 으로 구할 수 있다. 또는 f(n) = ..