.

입력 출력 9 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 -1 0 1 -1 0 1 -1 0 -1 1 0 1 -1 0 1 -1 0 1 -1 1 0 -1 0 1 -1 10 12 11 이 문제는 -1, 0, 1로 각각 이루어진 종이의 개수를 구하는 문제입니다. 이는 기존에 풀던 분할 정복 알고리즘을 사용하여 풀면 됩니다. 기존의 쿼드 트리를 4개가 아닌 9개로 진행하면 쉽게 풀립니다. 입력 개수의 최대가 3의 7승이기 때문에 2190으로 MAX를 설정합니다. 이 외의 나머지는 모두 분할 정복과 같습니다. 그렇다면 소스코드로 봅시다. #in..

입력 출력 8 11110000 11110000 00011100 00011100 11110000 11110000 11110011 11110011 ((110(0101))(0010)1(0001)) 이 문제는 쿼드 트리를 사용한 분할 정복 문제입니다. 하나의 큰 파일을 받아 압축파일을 만들어 내는 것인데요. 정사각형 안이 모두 1이거나 0이면 각각 1과 0을 반환해서 출력해줍니다. 처음에 입력을 받을 때 공백이 없음을 확인할 수 있습니다. 따라서 STL 으로 받습니다. 그 후에는 기본적인 분할 정복을 사용하여 풀면 쉽게 풀립니다. 그렇다면, 소스코드로 봅시다. #include #include using namespace std; bool adj[65][65]; string str; void sol(int x, ..

입력 출력 55-50+40 -35 이 문제는 괄호를 쳐서 최대한 작은 수를 만들어 내는 문제입니다. 이는 그리디 알고리즘을 사용합니다. 또한 이 안에 어떤 규칙이 있는지 생각해볼 만한 문제입니다. 간단하게 말하자면 -가 나오면 다음 -가 나올 때까지 괄호로 묶어주면 됩니다. 저는 우선 연산자와 숫자를 모두 받기 위해서 STL 중 을 사용했습니다. 이후의 숫자나 연산자를 구분해주기 위해 를 사용했습니다. 만약, -가 나올 때 괄호로 묶어준다면, 첫 번째 -후에는 모든 숫자가 마이너스 값이 된다는 것을 알 수 있습니다. 그렇다면 소스코드로 봅시다. #include #include #include using namespace std; string str; vector data; vector op; int ma..

입력 출력 11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 4 이 문제는 팀원들이 각각의 회의 예정 시간이 주어지고 그에 따라 가장 많이 회의실을 배정할 수 있는 횟수를 구해내는 문제입니다. 이 문제는 그리디 알고리즘을 사용하여 풀리는 문제입니다. 그리디 알고리즘은 그때마다 최적의 선택을 하여 문제를 푸는 것을 말합니다. 물론, 그렇게 하여 최적해가 나온다는 보장은 없습니다. 따라서 이러한 알고리즘은 정말 확신이 설 때만 사용하시고 웬만하면 DP를 사용하시길 권합니다. 그렇다면, 소스코드로 봅시다. #include #include #include using namespace std; int n; vector v; int solution(){ int tmp =..

입력 출력 4 5 1 1 2 1 3 1 4 2 4 3 4 1 2 4 3 1 2 3 4 5 5 3 5 4 5 2 1 2 3 4 3 1 3 1 2 5 4 3 1 4 2 5 1000 1 1000 999 1000 1000 999 1000 999 이 문제는 DFS와 BFS를 구현해 보는 문제입니다. 처음에 노드와 간선의 개수와 그에 대한 데이터들이 들어옵니다. 그래프를 구현하고 그에 따른 깊이 우선 탐색과 너비 우선 탐색을 진행하면 되는 문제입니다. 그래프의 구현을 위해서 원래는 vector 와 같은 인접 리스트를 사용했었습니다. 하지만 이번 입출력 데이터를 보시면, 노드의 번호 순서대로 접근하는 것을 볼 수 있습니다. 따라서, vector STL로 구현하려면 각각의 요소가 정렬이 필요합니다. 저는 그 과정을 배..

입력 출력 7 6 1 2 2 3 1 5 5 2 5 6 4 7 4 이 문제는 그래프를 구현하고 탐색을 진행하는 문제입니다. 이는 또한 첫 번째 노드와 연결되어 있는 연결 요소들의 개수를 세는 것과 같습니다. 그 과정은 BFS나 DFS 둘 다 가능합니다. 저는 DFS(깊이 우선 탐색)를 구현하기 위해 인접 리스트를 사용했습니다. 각각의 vector의 크기를 할당하기 위해서 resize함수를 사용했습니다. 그렇다면, 소스코드로 봅시다. #include #include using namespace std; vector adj; vector chk; int cnt = 0; void dfs(int num){ chk[num] = true; cnt++; for(int i = 0; i < adj[num].size(); ..