2020-08-14코딩테스트

백준 1037번 문제 - 약수

문제 링크 : https://www.acmicpc.net/problem/1037

N의 약수들은 제곱으로 N이 되는 약수를 제외하고 대칭이 되는 숫자들끼리 곱하여 N을 구할 수 있다.

예를 들어, 16의 경우 약수들은 {1, 2, 4, 8, 16}으로 16을 구하기 위해 1과 16, 2와 8, 4(제곱)을 선택하여야 한다.

N의 약수들이 주어졌을 때, N은 최소값과 최대값을 저장하여 곱함으로서 구할 수 있고 이는 다른 최대, 최소 값을 제외하고 저장할 필요가 없다는 것을 의미한다.

그러나 주어지는 약수들은 1,000,000이하의 정수로 입력되는 점을 고려하였을 때, 두 정수의 곱으로 표현되는 정수 N은 16비트로 표현되는 int형 정수가 아닌 32비트 정수로 표현하여야 한다.

32비트 정수를 표현하기 위해 최소 약수와 최대 약수의 곱은 long long int형 정수로 형변환을 하여 출력되도록 하였다.

#include<stdio.h>
using namespace std;
int aliqot, N, alimin=1000000,alimax=1;

int main(){
    scanf("%d",&N);
    while(N--){
        scanf("%d",&aliqot);
        alimin = (aliqot<alimin)?aliqot:alimin;
        alimax = (aliqot>alimax)?aliqot:alimax;
    }
    printf("%lld",(long long int)alimin*alimax);
    return 0;
}

2020-08-05코딩테스트

백준 1032번 문제 - 명령 프롬프트

문제 링크 : https://www.acmicpc.net/problem/1032

명령 프롬프트 문제는 주어진 문자열들을 비교하여 불일치가 발생한 문자에 대해 ?로 표현하여 출력하는 문제이다.

하나의 문자열이라도 불일치가 발생한 경우 불일치가 발생한 위치의 문자는 ?로 출력되므로
비교할 기준이 되는 문자열 하나만을 저장하여 다른 문자열들과 비교하고 불일치가 발생한 위치의 문자를 ?로 변경한다면 공간적인 낭비를 줄일 수 있다.

또한 문자열의 길이 최대 값은 50이지만 그보다 작은 길이의 문자열 입력이 발생할 수 있다.

scanf 함수를 통해서 입력 받은 문자열의 마지막 문자는 NULL(‘\0’)이 입력되므로 (i<51 && arr[i] != NULL) 혹은 (i<51 && arr[i])의 조건문을 수행한다면 &&연산에 의하여 i<51을 만족하지 않는다면 뒤의 연산을 수행하지 않기 때문에 문자열 길이 내의 검사를 수행할 수 있다.

#include<iostream>
using namespace std;
#define MAXSIZE 51
int N;
char arr[MAXSIZE], temp[MAXSIZE];

int main(){
    scanf("%d",&N);
    scanf("%s",&arr);
    for(int i=1;i<N;i++){   
        scanf("%s",temp);
        int j=0;
        while(j<MAXSIZE && temp[j]){
            if(arr[j]!=temp[j]) arr[j] = '?';
            j++;
        }
    }
    printf("%s\n",arr);
}

2020-07-26코딩테스트

백준 1021번 문제 - 회전하는 큐

문제 링크 : https://www.acmicpc.net/problem/1021

회전하는 큐 문제는 다음과 같은 3가지 연산을 수행한다.

1. 첫 번째 원소를 뽑아낸다.
2. 원소들을 좌측으로 한 칸씩 이동시킨다.
3. 원소들을 우측으로 한 칸씩 이동시킨다.

2번 연산 이후 3번 연산을 사용하게 된다면 원소는 제자리로 돌아가게 될 것이다.

따라서 원소를 뽑아내는데 필요한 2, 3번 연산의 최소 값은 원하는 원소가 첫 번째 원소가 될 때 까지 2번 연산을 수행하거나 3번 연산을 수행하는 경우 중 수행한 연산의 최소 값이 된다.

(원소의 위치)와 (원소의 위치 - 큐의 크기)의 계산으로 이를 확인하였으며 구현한 내용은 아래와 같다.

#include<iostream>
#include<vector>
using namespace std;
int N,M,result=0;
vector<int> vec;

void myPop(int k){
    int current = 0;
    while(vec[current]!=k)        current++;    //뽑아내고자 하는 원소의 위치 확인
    if(current<vec.size()-current){//2번 연산
        while(vec.front()!=k){
            vec.push_back(vec.front());
            vec.erase(vec.begin());
            result++;
        }
    }else{//3번 연산
        while(vec.front()!=k){
            vec.insert(vec.begin(),vec.back());
            vec.pop_back();
            result++;
        }
    }
    vec.erase(vec.begin());//1번 연산
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++){
        vec.push_back(i);
    }
    for(int i=0;i<M;i++){
        int k;
        scanf("%d",&k);
        myPop(k);
    }
    printf("%d\n",result);
    return 0;
}

2020-07-12코딩테스트

백준 1012번 문제 - 유기농 배추

문제 링크 : https://www.acmicpc.net/problem/1012

유기농 배추 문제는 DFS 또는 BFS를 통해 해결할 수 있다.

DFS란 깊이 우선 탐색(Depth-First Search), BFS란 너비 우선 탐색(Breadth-First Search)으로서 모든 정점을 한 번씩만 방문하여 모든 노드를 탐색하는 그래프 탐색 알고리즘이다.

명칭에서도 알 수 있듯이, DFS는 깊이 우선 탐색으로 더 이상 이동할 수 있는 노드가 없을 때까지 연결된 노드를 지속적으로 방문한 후 이전 노드로 돌아가 연결된 다른 노드를 방문하는 backtracking 방식을 사용하며 BFS는 너비 우선 탐색으로 노드에 가까운 노드들을 모두 방문한 후에 해당 노드들에 연결된 노드를 방문하는 방식으로 구현되어있다.

DFS의 경우 깊이를 우선시 하기 위해 LIFO인 stack을 사용하거나 재귀함수를 사용하여 탐색할 수 있으며, BFS의 경우 너비를 우선시 하기 위해 FIFO인 queue를 사용한다.

유기농 배추 문제는 배추가 심어져 있는 땅의 위치 X와 Y를 입력으로 받는다.
입력받은 배추들을 확인할 예정에 두고 인접한 위치에 배추가 존재하지 않을 때까지 방문하지 않은 인접 배추들을 확인하도록 하여 그룹을 체크할 수 있다.

#include<iostream>
#include<vector>
using namespace std;
#define MAXSIZE 51
int T,M,N,K;
int arr[MAXSIZE][MAXSIZE]={0};
bool bvisited[MAXSIZE][MAXSIZE]={false};
vector<pair<int,int>> vec;
int result=0;

void grouping(int x, int y){
    bvisited[x][y]=true;
    if(x>0&&arr[x-1][y]&&!bvisited[x-1][y]){
        grouping(x-1,y);
    }
    if(x+1<M&&arr[x+1][y]&&!bvisited[x+1][y]){
        grouping(x+1,y);
    }
    if(y>0&&arr[x][y-1]&&!bvisited[x][y-1]){
        grouping(x,y-1);
    }  
    if(y+1<N&&arr[x][y+1]&&!bvisited[x][y+1]){
        grouping(x,y+1);
    }
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %d",&M,&N,&K);
        vec.clear();
        result=0;
        for(int i=0;i<N;i++){//y
            for(int j=0;j<M;j++){//x
                bvisited[i][j] = false;
                arr[i][j]=0;
            }
        }
        while(K--){
            int i,j;
            scanf("%d %d",&i,&j);
            arr[i][j] =1;
            vec.push_back(make_pair(i,j));
        }
        for(int i=0;i<vec.size();i++){
            int x = vec[i].first;
            int y = vec[i].second;
            if(!bvisited[x][y]){
                grouping(x,y);
                result++;
            }
        }
        printf("%d\n",result);

    }
    return 0;
}

2020-07-11코딩테스트

백준 1018번 문제 - 체스판 다시 칠하기

문제 링크: https://www.acmicpc.net/problem/1018

체스판 다시 칠하기 문제는 8x8 크기의 체스판으로 만들 때 체스판의 경우의 수가 좌상단 첫번째 칸이 흰색인 경우와 검은색인 경우 두가지 밖에 없다는 점을 읽었다면 쉽게 풀 수 있는 문제이다.

NxM의 보드판이 주어졌을 때 8x8의 체스판을 구하기 위해 정할 수 있는 시작점은 (0,0)부터 (N-8,M-8)까지 가능하다.

가능한 각 시작점을 기준으로 8x8의 가능한 체스판 2개에 대해 불일치한 수를 구해 최소값을 구함으로서 해답을 구할 수 있다.

#include<iostream>
using namespace std;
#define MAXSIZE 51
#define CHESSSIZE 8
int N,M,result=64;//8x8이므로 아무리 색을 다시칠해도 64의 결과가 나올 수 없음
char arr[MAXSIZE][MAXSIZE];

int check(int n,int m){ //8x8에서 인접한 위치와 충돌이 일어나는 수
    int result1=0, result2=0;
    for(int i=0;i<CHESSSIZE;i++){
        for(int j=0;j<CHESSSIZE;j++){
            if(i%2==j%2){//0,0 || 1,1
                if(arr[n+i][m+j]!='W') result1++;
                if(arr[n+i][m+j]!='B') result2++;
            }else{//0,1 || 1,0
                if(arr[n+i][m+j]!='B') result1++;
                if(arr[n+i][m+j]!='W') result2++;
            }
        }
    }
    return (result1<result2)?result1:result2;
}

int main(){
    scanf("%d %d",&N,&M);
    for(int i=0;i<N;i++) scanf("%s",&arr[i]);
    
    //풀이 1: 가장 간단한 방법, N-8, M-8의 경우의 수를 전부 조사하여 최소값 구하기
    for(int i=0;i<=N-8;i++){//시작점 세팅
        for(int j=0;j<=M-8;j++){
            int temp = check(i,j);
            result = (result>temp)?temp:result;
        }
    }
    printf("%d\n",result);
}

2020-07-07코딩테스트

백준 1009번 문제 - 분산처리

문제 링크 : https://www.acmicpc.net/problem/1009

분산처리 문제는 어려워보이는 제목과는 달리 컴퓨터가 10대라는 점만으로 해결방법을 알 수 있는 쉬운 문제이다.

1번째 컴퓨터는 1번째 데이터, 11번째 데이터, 21번째 데이터와 같이 일의 자리가 1인 번호의 데이터를 처리하며 $a^b$개의 데이터 중 마지막 데이터는 일의 자리에 따라 처리할 컴퓨터의 번호가 결정된다.

그러나 $1\leq a < 100 , 1\leq b < 1,000,000$의 조건으로 보아 단순히 $a^b$를 계산하여 일의 자리를 찾는 것은 무리가 있어보인다.

이때 생각해야 할 것이 “일의 자리의 규칙성”이다.

예를 들어, $3^7$의 데이터에 대하여 생각해보자. $3^1=3$, $3^2=9$, $3^3=27$, $3^4=81$, $3^5=243$, $3^6=729$, $3^7=2187$로 일의자리가 3 -> 9 -> 7 -> 1의 반복이 이루어짐을 확인할 수 있다.

10 이하의 자연수에 대하여 지수함수의 일의 자리는 최대 4가지 경우의 수가 존재하며, 11 이상의 자연수는 일의 자리에 대해서만 계산하므로 10 이하의 자연수와 동일한 결과를 얻는다.

따라서 $a^b$의 일의 자리는 ${(a \mod 10)}^{b} \mod 10$이며 일의 자리의 반복 중 $b \mod 4$번째 결과와 동일한 결과를 갖는다.

#include<iostream>
using namespace std;
int arr[4];

int main(){
    int T,a,b;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&a,&b);
        arr[0]=a%10;
        arr[1]=(arr[0]*a)%10;
        arr[2]=(arr[1]*a)%10;
        arr[3]=(arr[2]*a)%10;
        printf("%d\n",(arr[(b-1)%4]==0)?10:arr[(b-1)%4]);
    }
    return 0;
}