algolab은 국민대학교 소프트웨어학부 수업에서 사용되는 온라인 저지?(과제 제출 사이트)입니다.
이전 주차들과 마찬가지로 5주차 과제 제출 기한이 끝났기 때문에, 한번 풀이를 작성해보겠습니다.
파일 입출력에 관해서는 이전글에 남겨놨습니다.
-> 2020/04/14 - [KMU/algolab] - [KMU-algolab] c++ 프로그래밍 파일 입출력
(하지만, 굳이 파일 입출력을 사용하지 않아도 된다네요..)
18. 행렬덧셈
문제에서 주어진 테케가 이상(-가 ㅡ로 표기 되어있습니다.)하여서, 코드를 짜고 검증을 할 때, 이슈가 생겼던 문제입니다. 하지만 문제 자체는 쉬운 난이도입니다.
#include <iostream>
using namespace std;
int tc;
int m,n;
int a[110][110];
int b[110][110];
int main() {
freopen("input.txt","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> tc;
while(tc--) {
cin >> m >> n;
for(int y=0; y<m; y++) {
for(int x=0; x<n; x++) {
cin >> a[y][x];
}
}
for(int y=0; y<m; y++) {
for(int x=0; x<n; x++) {
cin >> b[y][x];
}
}
for(int y=0; y<m; y++) {
for(int x=0; x<n; x++) {
cout << a[y][x] + b[y][x] <<" ";
}
cout<<"\n";
}
}
}
19. 해밍수
제가 이 문제의 설명을 제대로 안읽고 그냥 풀어버리고 나서, 설명을 읽은지라
문제의 의도와 조금 다른 풀이일 수도 있습니다.
삼중 for문으로 2, 3, 5를 각각 몇번 제곱할 것인지를 구합니다.
근데, 이때 제발 pow좀 쓰지 마세요..
개인적으로 pow는 double로 return되는데다가, 범위가 커질때, 시간복잡도를 먹는 괴물이라고 생각해서 쓰지 않습니다.
그리고, 문제 상에서 주어진 최대값 39580750을 활용해 그 숫자보다 큰 경우가 나오거나, 오버플로우가 나오는 경우에는 배열에 숫자를 집어넣지 않고, 개수를 세지 않습니다.
마무리로, 배열에 넣은 숫자들을 정렬하고, n-1번째 숫자를 출력합니다.
참고로, 해밍수를 구하는 전처리 과정을 테케 반복문 이전에 넣어놓으면 시간복잡도를 아낄 수 있겠죠?
또, 이 문제는 priority_queue + BFS 로도 해결할 수 있는 문제여서, O(N + logN)으로도 해결 가능합니다. 단지 N의 범위가 크지 않아 삼중 for라는 무식한 방법으로도 해결할 수 있는 것이죠.
#include <iostream>
#include <algorithm>
#define MX 398580751
using namespace std;
typedef long long ll;
int tc,N;
ll cnt;
ll ar[110000];
int main() {
freopen("input.txt","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll k1 = 1;
for(int x=0; x<=50; x++) {
ll k2 =1;
for(int y=0; y<=50; y++) {
ll k3 = 1;
for(int z=1; z<=50; z++) {
ll Z = k1*k2*k3;
if(Z <0) continue;
ar[cnt++] = Z;
k3*=5;
if(k3 > MX) {
break;
}
}
k2*=3;
if(k2 > MX) {
break;
}
}
k1*=2;
if(k1 > MX) {
break;
}
}
sort(ar,ar+cnt);
cin >> tc;
while(tc--) {
cin >> N;
cout << ar[N-1]<<"\n";
}
}20. 집합연산
이 문제는 할 말이 많습니다.
"비트" 로 해결하는 문제입니다... 비트..
그냥 #include <set> 하면 되는데, 왜 이렇게 길게 풀었겠습니까요...ㅠㅠ
문제 의도를 최대한 반영해서 풀려고 노력했으니 그렇죠..
암튼, 문제에서 unsigned int에 대해서 설명을 해주고 있네요?
unsigned int는 32비트를 사용하는 자료형입니다.
문제상에서는 집합에 들어오는 숫자의 범위가 0부터 132라고 합니다.
따라서 결론적으로는 unsigned int ar[5]; 라는 5칸 짜리 배열안에 집합 정보를 저장하라는 이야기입니다.
왜 그런것인지 이야기 해봅시다.
32비트 unsigned int 자료형의 a라는 변수가 있다고 해봅시다.
a라는 변수에 숫자가 들어가겠죠?
만약 0번째 비트에 1이 들어가면, 어떤 A라는 집합에 0이 들어가있다는 이야기라고 생각합시다.
그러면 또 만약 5번째 비트에 1이 들어가면, 어떤 A라는 집합에 5가 들어가있다는 이야기라고 생각해봅시다.
또다른 예시를 들어, B = {0, 1, 5} 라는 집합이 있을 때, 0000....10011 이라는 이진수로 바꾸어서, 1 + 2 + 16 = 19 라는 숫자로 저장을 하라는 이야기입니다.
이제 다시 문제로 돌아와서, 5칸 배열이 있다면 한 칸당 다음 숫자 범위를 저장한다고 생각하는 것입니다.
[0] 번째 배열칸 : 0~ 31
[1] 번째 배열칸 : 32~ 63
[2] 번째 배열칸 : 64~ 95
[3] 번째 배열칸 : 96~ 127
[4] 번째 배열칸 : 128~ 159
이렇게하면 133칸의 배열을 선언하는 것이 아니라, 5칸의 배열을 선언하면 된다는 이야기 되죠..
아래는 참고 내용과 코드입니다.
A라는 변수에 집합의 정보를 저장한다고 생각하고 가정한 예제입니다.
// z라는 숫자를 집합에 추가한다.
A |= (1 << z)// z라는 숫자는 집합에 포함되어있는가?
if((A & (1 << z)) {
// code
}// z라는 숫자는 집합에 없는가?
if((A & (1 << z) == 0) {
// code
}
아래는 제 풀이 코드입니다.
좀 더럽게 짜긴 했습니다.
비트연산이 막 등장해서.. 그래도 위에 예제를 보시고나면 이해가 되실 겁니다.
#include <iostream>
using namespace std;
typedef long long ll;
int tc;
ll A,B,i;
ll a[11];
ll b[11];
int main() {
freopen("input.txt","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> tc;
while(tc--) {
for(int x=0; x<10; x++) a[x]=b[x]=0;
cin >> A;
for(int x=0; x<A; x++) {
cin >> i;
ll idx = i/32;
ll z = i%32;
a[idx] |= (1 << z);
}
cin >> B;
for(int x=0; x<B; x++) {
cin >> i;
ll idx = i/32;
ll z = i%32;
b[idx] |= (1 << z);
}
// 교집합
int cnt = 0;
for(int y =0; y<6; y++) {
for(int x=0; x<32; x++) {
if((a[y] & (1<<x)) && (b[y] & (1<<x))) {
cnt++;
}
}
}
cout << cnt << " ";
for(int y =0; y<6; y++) {
for(int x=0; x<32; x++) {
if((a[y] & (1<<x)) && (b[y] & (1<<x))) {
// cnt++;
cout << y*32+x << " ";
}
}
}
cout << "\n";
// 합집합
cnt = 0;
for(int y =0; y<6; y++) {
for(int x=0; x<32; x++) {
if((a[y] & (1<<x)) || (b[y] & (1<<x))) {
cnt++;
}
}
}
cout << cnt << " ";
for(int y =0; y<6; y++) {
for(int x=0; x<32; x++) {
if((a[y] & (1<<x)) || (b[y] & (1<<x))) {
cout << y*32+x << " ";
}
}
}
cout << "\n";
// 차집합
cnt = 0;
for(int y =0; y<6; y++) {
for(int x=0; x<32; x++) {
if((a[y] & (1<<x)) && !(b[y] & (1<<x))) {
cnt++;
}
}
}
cout << cnt << " ";
for(int y =0; y<6; y++) {
for(int x=0; x<32; x++) {
if((a[y] & (1<<x)) && !(b[y] & (1<<x))) {
cout << y*32+x << " ";
}
}
}
cout << "\n";
}
}이 문제를 풀고 나서는 한번
https://www.acmicpc.net/problem/13701
13701번: 중복 제거
문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 이상 500만 이하이다.
www.acmicpc.net
요 문제를 해결해보세요. :)
21. 이동평균
간단한 스위핑 문제였습니다. (한마디로, 그냥 긁으면 되는 문제)
길이가 K인 연속된 구간들의 합을 구해야 하는 상황이죠?
아, 그러면 그냥 길이가 K인 구간을 만들어 놓고, 한칸씩 옮기자는 이야기가 됩니다.
따라서, 에.. 코드에 주석을 달아놓았습니다.
주석 부분을 확인해주세요..
#include <iostream>
using namespace std;
int tc;
int k,n;
int ar[330],S,cnt;
int ans[330];
int main() {
freopen("input.txt","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> tc;
while(tc--) {
cin >> n;
for(int x=0; x<n; x++) cin >> ar[x];
cin >> k;
S = cnt = 0;
for(int x=0; x<k; x++) S+=ar[x]; // 길이가 K인 첫번째 구간의 합
ans[cnt++]=S; // 답 저장해놈.
for(int x=k; x<n; x++) {
S += ar[x]; // 맨 뒤에 한칸 추가
S -= ar[x-k]; // 맨 앞에 한칸 제거
ans[cnt++]=S; // 답 저장
}
cout <<cnt << " ";
for(int x=0; x<cnt; x++) {
cout << ans[x] / k <<" ";
}
cout<<"\n";
}
}
집합 연산 문제를
의도대로 풀려하셨다면 굉장히 어려운 한 주의 과제가 되었겠네요.
아무튼,
Rmx
'KMU > algolab' 카테고리의 다른 글
| [KMU - algolab] c++ 프로그래밍 week 6 과제 풀이 (0) | 2020.05.04 |
|---|---|
| [KMU - algolab] c++ 프로그래밍 week 4 과제 풀이 (0) | 2020.04.20 |
| [KMU - algolab] c++ 프로그래밍 파일 입출력 (5) | 2020.04.14 |
| [KMU - algolab] c++ 프로그래밍 week 3 과제 풀이 (0) | 2020.04.13 |
| [KMU - algolab] c++ 프로그래밍 week 2 과제 풀이 (2) | 2020.04.06 |