다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.예를 들어 S=0001100 일 때,전체를 뒤집으면 1110011이 된다.4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.
[입력] 첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.
[출력] 첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.
✅ 문제 풀이
문자열의 첫 문자를 기준으로 해서 문자열을 앞에서부터 순회한다.
첫 문자를 now에 저장해두고, 비교하다가 문자가 다르면 count를 해주고 now에 그 문자로 바꾸어준다.
위 과정을 반복하고 나면 최종 count값이 설정된다.
count값이 홀수이면 0을1로, 1을 0으로 바꾸는 횟수가 똑같기 때문에, count를 2로 나눈 몫에 1을 더한 것과 같다.
count값이 짝수이면, 0을 1로, 1을 0으로 바꾸는 횟수가 둘 중 하나가 더 적기 때문에, count를 2로 나눈 몫과 같다.
✏ 코드 전문
#include<iostream>
#include<string>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string str;
cin >> str;
int count=0;
char now = str[0];
for (int i = 1; i < str.length(); i++) {
if (now != str[i]) {
count++;
now = str[i];
}
}
if (count % 2 == 1) {
count /= 2;
count++;
}
else {
count /= 2;
}
cout << count;
return 0;
}
다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다. 다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)
[입력] 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.
[출력] 첫째 줄에 필요한 세트의 개수를 출력한다.
✅ 문제 풀이
주어진 방번호 N의 각 자리 수를 구해야한다. N을 10으로 나눈 나머지를 구하면 된다.
그리고 그 값을 카운트 해준 후, N을 10으로 나눈 몫으로 갱신한다.
카운트 하기 위해서 0부터 9까지의 출현 빈도를 저장할 배열을 선언해준다.
만약 각 자리의 수가 6또는 9이면, 6번 인덱스와 9번 인덱스의 값을 비교해서 똑같은 경우 6에 먼저 카운트 되도록 하고, 아니면 9에 카운트 되도록 한다. 6과 9는 뒤집어서 서로를 사용할 수 있기 때문이다.
그렇지 않다면 그냥 그 수에 해당하는 인덱스의 값에 카운트 되도록 한다.
필요한 상자수는 배열에서 가장 MAX인 값과 같게 된다.
✏ 코드 전문
#include<iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int arr[10] = { 0 };
int N;
cin >> N;
while (N > 0) {
if (N % 10 == 6 || N % 10 == 9) {
if (arr[6] == arr[9]) arr[6]++;
else arr[9]++;
}
else arr[N % 10]++;
N /= 10;
}
int max = arr[0];
for (int i = 1; i < 10; i++) {
if (max < arr[i]) max = arr[i];
}
cout << max;
return 0;
}
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. [입력] 첫째 줄에 정수 N, r, c가 주어진다.
[출력] r행 c열을 몇 번째로 방문했는지 출력한다.
✅ 문제 풀이
분할과 정복 파트에 있는 문제이다.
하지만 흔히 푸는 방식인 재귀함수 호출을 이용한다면, 테스트 케이스는 통과할지 몰라도, 시간초과 또는 메모리 초과가 발생할 것이다.
일단 메모리 초과가 나는 이유는, 배열을 선언하고 저장하는 형태로 접근해서 일 것이다.
입력을 보면 우리는 최대 2^30 크기의 배열이 필요하게 되기 때문에, 기가 수준의 메모리가 필요해진다.
사실상, 주어진 입력을 통해 배열을 굳이 선언하지 않고도 단순히 카운트한 값만을 이용할 수 있으니, 배열은 필요없다 -> 메모리초과 문제 해결
두번째는 시간 초과인데, 입력이 커지면, 굳이 필요없는 방문이 반복적으로 발생하게 된다. 즉 너무나 깊은 함수 호출로 인해 오히려 시간초과가 발생하는 것이다.
그럼 재귀호출 말고, 단순히 반복문으로 쉽게 카운트 하는 방법을 찾을 수 있다.
나는 다음과 같은 규칙을 찾아냈다.
1. 주어진 (r,c)의 번호는 이전에 이 영역에 도달하기 전에 크기가 1인 몇개의 영역을 지나왔는가와 동일하다.
예를 들어, 2*2크기의 배열이 있다고 할때, (1,1)에 도달 하기 전에는 (0,0),(0,1),(1,0)순으로 3개를 거친후 도달한다.
따라서 (1,1)의 번호는 3으로 매겨질 수 있는 것이다.
2. 주어진 (r,c)의 영역 범위와, 배열 크기에 따라 이전에 몇개를 거쳐오는지를 통채로 빠르게 계산할수 있다.
예를 들어 4*4 크기의 배열이 있다고 할때, (3,3)의 번호를 구하고 싶다고 하자.
이 위치는 배열을 4등분 했을 때, 방문 순서로 따지면 4번째 영역에 존재한다. 따라서 3번째 영역을 다 돌고 난 후의 값보다는 무조건 클 것이다.
그러므로 굳이 현재 (3,3)이 존재하는 4번째 영역을 제외하고는 일일이 탐색할 필요없이, 그 크기만큼 count에 더해주면 된다.
따라서 한 영역당 크기가 4이므로, 네번째 영역이라면, 4*3=12보다는 무조건 큰 번호를 가지게 된다.
이렇게 12를 count에 더해주고, 이제 네번째 영역을 하나의 배열이라 치고 위의 과정을 반복하면 된다.
이어서 설명하자면, 네번째 영역을 하나의 배열이라 치면 크기가 4인 배열이고, 여기서 (3,3)은 이 배열을 또 4등분 했을때 4번째 영역에 속하는 것이기 때문에, 한 영역당 크기가 1이므로, 1*3=3을 count에 더해주면 된다. 이제 (3,3)은 크기가 1인 배열이므로 더이상 쪼개지지 않고, 현재의 count 값인 15가 답이 되는 것이다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
void divide(int x, int y, int size, int &count, int &r, int&c) {
while (size >= 1) {
int set = pow(size / 2, 2);
if (r < x + size / 2 && c < y + size / 2) {
}
else if (r < x + size / 2 && c >= y + size / 2 && c < y + size) {
count += set;
y += size / 2;
}
else if (r >= x + size / 2 && r < x + size && c < y + size / 2) {
count += set * 2;
x += size / 2;
}
else {
count += set * 3;
x += size / 2;
y += size / 2;
}
size /= 2;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, r, c;
cin >> N >> r >> c;
int size = pow(2, N);//처음 행,열의 크기
int count = 0;
divide(0, 0, size, count, r, c);
cout << count;
}
코드로 표현하자면 다음과 같이 접근했다.
size를 배열의 한 변 길이로 두고, 그 배열에서 가장 처음 방문하는 곳을 x와 y로 두었다 .
배열의 한변 길이가 1이 될 때까지, 즉 계속해서 쪼개지는 배열이 하나의 요소가 될때까지 ,쪼개면서 count하도록 하였다.-> 분할과 정복
set는 현재 배열에서 4등분 했을 때 각 영역의 크기를 저장한다.
이제 4개의 영역마다 서로 다른 로직을 따르도록 할것이다.
만약 (r,c)가 1번 영역에 속한다면 = 1번 영역은 배열 시작인 x,y각각에 size/2를 더한 것의 내부에 존재하는 영역이다. 그렇다면 처음 방문인 거니까 x, y도 기준 그대로 이고, 이전 방문 내역이 없으므로 count하지 않아도 된다.
만약 (r,c)가 2번 영역에 속한다면 = 2번 영역은 배열 시작인 x에 size/2를 더한 것의 내부이면서, y는 size/2를 더한것의 이상이고 size를 더한 것보다는 작은 영역이다. 그렇다면 이전에 1번 영역을 방문한 거니까, count에는 set만큼 더해주고, y의 기준을 size/2만큼 더해주어서 갱신해준다. 이 부분이 다음 단계에서는 첫 방문이 되도록 하기 위함이다.
만약 (r,c)가 3번 영역에 속한다면 = 3번 영역은 배열 시작인 x에 size/2를 더한것의 이상이면서 size를 더한것보다는 작은 영역이고, y에 size/2를 더한 것보다는 작은 영역이다. 그렇다면 이전에 1번과 2번 영역을 방문한 거니까, count에는 set*2만큼 더해주고, x의 기준을 size/2만큼 더해주어서 갱신해준다. 이 부분이 다음 단계에서는 첫 방문이 되도록 하기 위함이다.
만약 (r,c)가 4번 영역에 속한다면 = 4번 영역은 배열 시작인 x에 size/2를 더한것의 이상이면서 size를 더한것보다는 작은 영역이고, y에 size/2를 더한 것의 이상이면서 size를 더한것보다는 작은 영역이다. 그렇다면 이전에 1번과 2번과 3번 영역을 방문한 거니까, count에는 set*3만큼 더해주고, x의 기준을 size/2만큼, y의 기준을 size/2만큼 더해주어서 갱신해준다. 이 부분이 다음 단계에서는 첫 방문이 되도록 하기 위함이다.
N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
[입력] 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
[출력] 첫째 줄에 경우의 수를 출력한다.
수열에서 연속적인 값들의 합이 M과 같은 경우의 수를 구하는 문제이다.
✅ 문제 풀이
일단 누적합을 나타내는 sum에는 수열에서 첫번째 값을 넣어두고 시작한다.
실행시간 조건이 0.5초이기 때문에, for문에 의한 순회는 한번을 최대로 해야 한다.
그럼 부분 합을 어떻게 구할 수 있을까?
두 포인터를 이용해서, 시작 지점과 끝 지점을 가리키도록 한다.
그것을 각각 s와 e로 하고, 수열의 인덱스를 가리키도록 한다.
처음에는 s와 e를 0으로 시작한다. 따라서 sum도 수열의 첫번째 값만을 담고 있어야 한다.
그렇게 해서 s<=e를 만족하는 한 계속 경우의 수를 찾아갈 것이다.
if문을 통해 현재의 sum값과 M을 비교한다.
만약 sum이 M보다 작으면, 더 더해주어야 하기때문에 e를 하나 늘리고, 현재 e가 가리키는 값을 sum에 더해준다. 이때 주의할 점은, 하나 늘어난 e가 N을 넘지 않아야 한다는 것이다. N을 넘지 않았을 경우에만 e가 가리키는 값을 sum에 더해주면 된다.=>유효성을 확인하는 부분이다.
만약 sum이 M과 같다면, 하나의 경우가 되는 것이므로, 경우의 수를 카운트하는 answer를 하나 늘려준다. 그리고 수열의 모든 값은 자연수이기 때문에, s를 늘리면 값을 줄고, e를 늘리면 값이 늘어나게 되는 건 분명하다. 따라서 이 경우에는 s와 e를 둘다 하나씩 늘리도록 한다.
만약 sum이 M보다 크다면, 빼주어야 하기때문에, sum에서 현재 s가 가리키는 값을 빼준다. 그리고 여기서 주의할 점이 있다. 만약 s가 e와 동일했었다면 다음 값을 sum에 넣어주어야 하기 때문에, s와 e를 둘다늘리고, 이 둘이 가리키는 값을 sum에 넣어주도록 한다. s와 e가 동일하지 않았다면 s를 하나 늘려주면 된다.
그리고 for문을 다 순회한 후에는 answer를 출력해주면 된다.
☑ 코드 전문
#include<iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin >> N >> M;
int arr[10000];
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int sum = arr[0];
int answer = 0;
for (int s = 0, e = 0; s <= e;) {
if (sum < M) {
e++;
if (e < N) sum += arr[e];
else break;
}
if (sum == M) {
answer++;
sum -= arr[s];
s++;
e++;
if (e < N) sum += arr[e];
else break;
}
if (sum > M) {
sum -= arr[s];
if (s == e && e < N - 1) {
s++;
e++;
sum += arr[e];
}
else {
s++;
}
}
}
cout << answer;
}
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다.
[입력] 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
[출력] 첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
✅ 문제 풀이
각 노드에 대한 자식 노드를 저장하기 위해서, vector 형태의 크기가 50인 배열 tree을 생성해주었다. vector<int> tree[50]
입력으로 N이 1부터 50까지 들어올 수 있기 때문에, 노드는 0~49임을 고려한 것이다.
차례대로 입력받을 때 0번 노드부터 부모를 입력받는다.
따라서 -1인 경우를 제외하고, 나머지 경우에 대해서는 입력받은 값을 p라고 했을 때, tree[p]에다가 해당 노드를 저장해준다. vector형태니까, push_back(해당 노드) 해주면 된다.
그럼 모든 노드에 대해서 바로 아래 자식 노드 리스트를 가지게 된다. 당연히, 자식이 없는 노드의 벡터는 비어있을 것이다.
그리고 삭제된 노드인지, 리프노드인지를 구별하기 위해 bool타입의 배열 leaf를 생성해서 false로 초기화 해주었다.
삭제할 노드를 입력받고, 해당 노드를 기준으로 dfs함수를 호출한다.
dfs 함수에서는 다음과 같이 동작한다. 입력 : tree, 삭제할 노드 node, leaf 로직 - 삭제할 노드의 자식 노드들을 순회한다. 즉 tree[node]를 순회한다. - 이 때 자식 노드를 num에 저장해두고, 자식의 자식들을 순회하기 위해 dfs를 호출하여 삭제할 노드로 num을 넘겨준다. -그리고 해당 노드에 대해 모두 순회했으면, tree[node]를 clear하여 모두 삭제해주고, 이는 삭제된 노드이므로 leaf[node]를 true로 변경해준다.
입력한 삭제 노드에 대해 위 로직을 따르고 나면, 이제 입력 값만을 부모에서 삭제해주면 된다.
부모를 찾기위해서 2중 for문을 통해 입력받은 값을 자식으로 갖는 노드가 있는지 순회하고, 일치하다면 해당 부모 노드의 배열에서 삭제하도록 한다. 그리고 순회를 즉시 멈춘다.
이제 삭제할 노드를 기점으로 모두 삭제되었으므로, tree배열을 순회하면서 leaf가 false이고(=삭제되지 않은노드), tree[i]의 size가 0인 노드를 카운트 하여 출력한다.
☑ 코드 전문
#include<iostream>
#include<vector>
using namespace std;
void dfs(vector<int> tree[], int node, bool leaf[]) {
for (int i = 0; i < tree[node].size(); i++) {
int num = tree[node][i];
dfs(tree, num, leaf);
}
tree[node].clear();
leaf[node] = true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
vector<int> tree[50];
bool leaf[50] = {false};//false->true 개수만 세기
for (int i = 0; i < N; i++) {
int p;
cin >> p;
if (p == -1) continue;
else {
tree[p].push_back(i);
}
}
int node;
cin >> node;
dfs(tree, node, leaf);
bool br=false;
for (int i = 0; i < N; i++) {
for (auto it = tree[i].begin(); it != tree[i].end(); it++) {
if (*it==node) {
tree[i].erase(it);
br = true;
break;
}
}
if (br) break;
}
int answer = 0;
for (int i = 0; i < N; i++) {
if (!leaf[i]&&tree[i].size() == 0) answer++;
}
cout << answer;
return 0;
}
