해나의 컴공생존기

https://www.acmicpc.net/problem/1992 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서..

https://www.acmicpc.net/problem/1780 문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 출..

https://www.acmicpc.net/problem/5427 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트..

모든 경우의 수를 하나하나 확인해봐야하는 문제다! 엥 간단하다! 하고 덤볐는데 for문 8개 돌리기밖에 생각이 안났다. 어쩌지어쩌지하다가 재귀를 풀면 될 것 같다..! 라고생각했고 배열을 만들어 맨 앞에서 부터 차례대로 채워 나가면 되겠다는 생각을 했다. 인자 n번째 칸을 결정하는 함수를 만든뒤 차례차례 뒤에를 채울 수 있게 재귀를 돌렸다. n번째칸이 문제에서 제시된 M과 같다면 모아놓은 배열을 출력하고 다시 새로운수를 만들면된다. #include using namespace std; int N, M; int num[10]; int check[10]; void NM(int n) { if (n == M) { for (int i = 0; i < M; i++) { cout M; NM(0); return 0; }

1. 알고리즘 설명 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 큐에서 맨 앞의 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 해당칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 큐가 빌 때까지 2번을 반복 시간복잡도는 모든 칸이 큐에 한번씩 들어가므로 칸이 N개일 때 O(N)이된다. 2. 코드 BFS는 코딩테스트에서 굉장히 중요한 부분이므로 꼭 잘 숙지해야함! #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int bo..