KiTFOx's Notepad 📝

1. 문제 요약

좌표 평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있음
진수는 두 양의 정수 k,d가 주어질 때 다음과 같이 점을 찍으려 함
원점 (0,0)으로부터 x축 방향으로 a*k(a=0,1,2,3...), y축 방향으로 b*k(b=0,1,2,3...)만큼 떨어진 위치에 점을 찍음
원점과 거리가 d를 넘는 위치에는 점을 찍지 않음 -> 반지름이 d인 원 안에서 모든 것을 해결함
k가 2, d가 4인 경우에는
(0,0),(0,2),(0,4),(2,0),(2,2),(4,0) 위치에 점을 찍어 총 6개의 점을 찍음
정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return하는 solution 함수 완성

2. 코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;


long long solution(int k, int d) {
    long long answer = 0;
    
    for(long long i=0;i<=d;i+=k){
        int y = sqrt(pow(d,2)-pow(i,2));
        answer+=y/(long long)k+1;
    }
    
    return answer;
}

3. 해설

이 문제에서 가장 주의해야할 점은 long long 이라는 자료형으로 변환인 것 같다

원점과의 거리가 d를 넘는 위치에는 점을 찍지 않는다는 전제 조건은 반지름이 d인 원 안에 모든 점들은 위치할 수 있다는 말과 같다

x 축의 방향으로는 a*k, y 축의 방향으로는 b*k 만큼 떨어진 위치에 점을 찍는다고하여서 k만큼 증가하는 for.문을 사용하면 된다

 int y = sqrt(pow(d,2)-pow(i,2));

y의 최댓값을 위의 코드로 구하고, 해당 최대 y값/k 를 하면 그 안에 b*k를 만족하는 갯수를 구할 수 있고, 0인경우를 포함해야하기 때문에 +1을 해준다

1. 문제 요약

k 개를 골라 상자 하나에 담아 판매
귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶음

처음에는 문제가 헷갈렸는데 결국 같은 크기의 귤을 모아서 최대한 판매하려고 하는 문제이다

2. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;


bool cmp(const pair<int,int>& lValue,const pair<int,int>& rValue){
    return lValue.second>rValue.second;
}

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    
    vector<pair<int,int>> tangerinePair;
    
    sort(tangerine.begin(),tangerine.end());
    
    /*for(int i=0;i<tangerine.size();i++){
        printf("%d ",tangerine[i]);
    }
    printf("\n");*/
    
    int prev = tangerine[0];
    tangerinePair.push_back(make_pair(tangerine[0],0));
    for(int i=0;i<tangerine.size();i++){
        //printf("%d ",tangerine[i]);
        if(prev==tangerine[i]){
            tangerinePair[tangerinePair.size()-1].second++;
        }
        else{
            tangerinePair.push_back(make_pair(tangerine[i],1));
            prev=tangerine[i];
        }
    }
    //printf("\n");
    
    sort(tangerinePair.begin(),tangerinePair.end(),cmp);
    
    int count=0;
    for(int i=0;i<tangerinePair.size();i++){
        //printf("%d %d\n",tangerinePair[i].first,tangerinePair[i].second);
        if(count>=k) break;
        count+=tangerinePair[i].second;
        answer++;
    }
    
    
    return answer;
}

3. 해설

먼저 vector<int> tangerine 벡터를 오름차순으로 정렬합니다

정렬한 다음  vector<pair<int,int>> tangerinePair에 <귤의크기,갯수>를 담았다

int prev = tangerine[0];
tangerinePair.push_back(make_pair(tangerine[0],0));

for(int i=0;i<tangerine.size();i++){
    if(prev==tangerine[i]){
        tangerinePair[tangerinePair.size()-1].second++;
    }
    else{
        tangerinePair.push_back(make_pair(tangerine[i],1));
        prev=tangerine[i];
    }
}

그 후, 귤의 갯수에 따라 vector<pair<int,int> tangerinePiar를 정렬해주었다

sort(tangerinePair.begin(),tangerinePair.end(),cmp);

bool cmp(const pair<int,int>& lValue,const pair<int,int>& rValue){
    return lValue.second>rValue.second;
}

그리고 for문을 이용하여 중복되는 갯수들을 k와 비교하여 더해줘서 수를 넘어가면 break하도록 제작하여주었다

int count=0;
for(int i=0;i<tangerinePair.size();i++){
    if(count>=k) break;
    count+=tangerinePair[i].second;
    answer++;
}

1. 문제 요약

열은 컬럼, 행은 튜플
첫번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장

(요약하자면 id 같은 고유 번호라는 것)

1. 해시 함수는 col, row_begin, row_end 을 입력으로 받음
2. 테이블의 튜플(행)을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 
만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬함

정렬된 데이터에서 S_i를 i번째 행의 튜플에 대해 각 컬럼의 값을 i로 나눈 나머지들의 합으로 정의
row_begin <= i <= row_end 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환함

2. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int sortIndex;

bool cmp(vector<int> lValue,vector<int> rValue){
    if(lValue[sortIndex]==rValue[sortIndex]) return lValue[0]>rValue[0];
    return lValue[sortIndex]<rValue[sortIndex];
}

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    int answer = 0;
    sortIndex=col-1;
    
    /*for(int i=0;i<data.size();i++){
        for(int j=0;j<data[i].size();j++){
            printf("%d ",data[i][j]);
        }
        printf("\n");
    }*/
    
    sort(data.begin(),data.end(),cmp);
    
    /*printf("\n\n");
    
    for(int i=0;i<data.size();i++){
        for(int j=0;j<data[i].size();j++){
            printf("%d ",data[i][j]);
        }
        printf("\n");
    }*/
    
    int s2;
    for(int i=row_begin-1;i<row_end;i++){
        s2=0;
        for(int j=0;j<data[i].size();j++){
            s2+=data[i][j]%(i+1);
            //printf("%d : %d %d ~~\n",(i+1),data[i][j],data[i][j]%(i+1));
        }
        //printf("%d !!\n",s2);
        answer= answer^s2;
    }
    
    
    return answer;
}

3. 해설

먼저, 테이블의 튜플을 col 번째 컬럼의 값을 기준으로 오름차순 정렬을 합니다

여기서 주의할 점은 col 번재 이기 떄문에 vector의 col-1의 값을 기준으로 정렬해야한다는 점입니다

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    int answer = 0;
    sortIndex=col-1;
    ...
}

bool cmp(vector<int> lValue,vector<int> rValue){
    if(lValue[sortIndex]==rValue[sortIndex]) return lValue[0]>rValue[0];
    return lValue[sortIndex]<rValue[sortIndex];
}

sortIndex라는 변수에 col-1을 할당해주고, algorithm 라이브러리의 sort함수와 제가 정의하는 cmp 비교함수를 이용하여 정렬을 진행했습니다

만약 비교 벡터들의 sortIndex 위치의 값이 같은 경우 기본키를 기준으로 내림차순 정렬을 진행하였습니다

그 후에는 ^ 연산자를 이용하여 XOR 비트 연산을 진행하였습니다

비트연산 XOR 이란?

베타적 OR 연산이라고도 부르는데

두 비트가 서로 다른 경우에만 1이 되고 그렇지 않으면 0이 되는 특이한 연산자

int s2;
for(int i=row_begin-1;i<row_end;i++){
    s2=0;
    for(int j=0;j<data[i].size();j++){
        s2+=data[i][j]%(i+1);
    }
    answer= answer^s2;
}

row_begin-1 에서 row_end까지 비트연산을 한 값들을 answer에 저장하였습니다

data[i][j]%(i+1)

는 정렬된 데이터에서 S_i를 i번째 행의 튜플(행)에 대해 각 컬럽의 값을 i로 나눈 나머지입니다

1. 문제 요약

절댓값이 10c 형태인 정수들이 적힌 버튼
현재 층 수에 버튼에 적혀 있는 값을 더한 층으로 이동
엘리베이터가 위치해 있는 층과 버튼의 값을 더한 결과가 0보다 작으면 엘리베이터는 움직이지 않음
0층이 가장 아래층
버튼 한번 당 돌 한개
최소한의 돌 최대한으로 내려가기
10단위로 나머지 계산
2,5,5,4 -> 16
1,6 -> 1+(10-6) = 5
7~9 인 경우 반올림해서 빼는 경우가 더 이득
1~5 인 경우 그냥 빼는 경우가 이득
2000 + 500 + 50 + 4
작은 결과들을 모아서 큰 결과 값을 만들 수 있는지 확인해보기

2. 코드

#include <string>
#include <vector>

using namespace std;

//최적의 사용 돌 갯수 구해서 answer에 더해주는 함수
void GetOptimalStoneCount(int& storey,int& answer){
    int count = storey%10;
    
    if(count<5) answer+=count;
    else{
        if(count==5&&storey%100<50){
            answer+=count;
        }
        else{
            answer+=10-count;
            storey=storey+10-count;
        }
    }
    storey/=10;
    //printf("%d, %d\n",storey,answer);
}

int solution(int storey) {
    int answer = 0;

    while(storey>1){
        GetOptimalStoneCount(storey,answer);
    }
    
    return answer+storey;
}

3. 해설

제가 선택한 알고리즘의 방법은 10씩 나눈다음 해당 값이 반올림이 가능한지 아닌지를 판별하는 것을 채택했습니다.

예를 들어, 맨 끝의 자리 숫자가 6이상인 경우 -6을 통해 6번 돌을 사용하는 것보다 한자릿수를 늘려서 처리하는 것이 이득입니다. 56의 경우 5+6 = 11 보다 4+6 = 10 의 경우 1의 이득을 더 볼 수 있습니다.

이러한 로직을 바탕으로 코드를 짜게 되면 최적의 돌을 구할 수 있습니다.

다만 5의 경우 주의해야할 점이 555, 545 이 경우입니다.

545의 경우 5+4+5 = 14가 최적의 돌의 경우의 수입니다.

만약 반올림을 해버리는 경우 5+5+5 = 15가 되기 때문에 더 많은 돌을 사용하게 됩니다.

555의 경우가 제일 헷갈려서 시간을 오래쓰게 되었습니다.

555의 경우,

560 -> +5  : 5번(+1)
600 -> +40 : 4번(+10)
1000 -> +400 : 4번(+100)
0 -> -1000 : 1번(-1000)

if(count==5&&storey%100<50){
	answer+=count;
}

해당 if문을 통해 10의 자리 수가5보다 작은 경우에는 반올림을 해주지 않고 그대로 - 를 감행하고, 반대의 경우에는 반올림을 진행하여 이득을 보는 형태로 코드를 사용하였습니다.

4. 테스트 케이스

999 -> 1+1 = 2

55 -> 5+5 = 10

75 -> 5+2+1 = 8

155 -> 5+4+2 = 11

545 -> 5+4+5 = 14

555 -> 5+4+4+1 = 14

1. 문제

bandage : {기술의 시전 시간, 1초당 회복량,추가 회복량}
health : 최대 체력
attacks : {몬스터의 공격 시간, 피해량}

Return : 모든 공격이 끝난 직후 남은 체력, 만약 체력이 0 이하면 -1 출력

2. 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

/*

Return
- 모든 공격이 끝난 직후 남은 체력
- 만약 체력이 0 이하가 되어 죽으면 -1

Rule
- 추가 회복량 : bandage
- 최대 체력 : health
- 몬스터의 공격 시간과 피해량 : attacks
- t 초 동안 1초마다 x 만큼의 체력 회복
- t 초 연속으로 성공하면 y만큼 체력을 추가로 회복

*/

void heal(int& healStat,int healValue,int healthMax){
    healStat+=healValue;
    if(healStat>healthMax) healStat = healthMax;    
}

int solution(vector<int> bandage, int health, vector<vector<int>> attacks) {
    int answer = health;
    
    int endTime = attacks[attacks.size()-1][0];
    int combo=0,attackIdx=0;
    for(int i=0;i<=endTime;i++){
        if(attacks[attackIdx][0]==i){
            answer-=attacks[attackIdx][1];
            combo=0;
            attackIdx++;
        }
        else{
            combo++;
            heal(answer,bandage[1],health);
            if(combo==bandage[0]){
                //active combo
                heal(answer,bandage[2],health);
                combo=0;
            }
        }
        
        if(answer<=0){
            answer=-1;
            break;
        }
    }
    
    return answer;
}

3. 해설

	 int endTime = attacks[attacks.size()-1][0];
    int combo=0,attackIdx=0;
    for(int i=0;i<=endTime;i++){
        if(attacks[attackIdx][0]==i){
            //cout<<"attackIdx: "<<attackIdx<<endl;
            answer-=attacks[attackIdx][1];
            combo=0;
            attackIdx++;
        }
        else{
            combo++;
            heal(answer,bandage[1],health);
            if(combo==bandage[0]){
                //active combo
                heal(answer,bandage[2],health);
                combo=0;
            }
        }
        
        if(answer<=0){
            answer=-1;
            break;
        }
        //cout<<"health: "<<health<<endl;
    }

endTime 은 attacks 배열의 맨 마지막 인자의 공격 시간을 받아왔습니다.
attacks는 시간순으로 오름차순으로 정렬이 되어 있기 때문에 재정렬할 필요가 없습니다.
받아온 마지막 공격 시간까지 체크를 하는 for문을 작동시킵니다.
combo 는 콤보를 받아올 변수이고 attackIdx는 attacks 공격할 배열의 순서를 의미합니다.
attackIdx는 공격을 받을 때, 다음 인자로 넘어가도록 설계되어 있습니다.

if(attacks[attackIdx][0]==i)

위의 if문은 attackIdx 순서에 따른 공격 순서가 i(시간)과 같은지 체크 하는 구문입니다.
만약, attacks 배열이 {{1,5},{3,10}} 로 이루어져 있다면
- 시간 1일 때 5를 공격한다.
- 시간 3일 때 10을 공격한다.
입니다.
만약 attackIdx 가 0 이면, 시간 1일 때 공격을 시전하면 됩니다.

answer-=attacks[attackIdx][1];
combo=0;
attackIdx++;

만약 i(시간)이 맞다면, 공격이 시전됩니다.
따라서 answer(현재 체력)을 attacks[attackIdx][1](피해량)만큼 감소시킵니다.
콤보는 깨지기 때문에 0으로 바꾸어줍니다.
해당 공격을 받고 나서는 다음 공격을 체크할 수 있도록 attackIdx를 증가시켜줍니다.

else{
	combo++;
	heal(answer,bandage[1],health);
	if(combo==bandage[0]){
		//active combo
		heal(answer,bandage[2],health);
		combo=0;
	}
}

만약 공격을 받지 않는다면 치유를 합니다.
콤보의 갯수를 늘리고, 치유를 합니다.

void heal(int& healStat,int healValue,int healthMax){
    healStat+=healValue;
    if(healStat>healthMax) healStat = healthMax;    
}

힐은 healthMax(최대 체력)을 넘어가면 다시 조정됩니다.

if(combo==bandage[0]){
	//active combo
	heal(answer,bandage[2],health);
	combo=0;
}

만약 콤보를 달성하면 추가 체력이 치유되도록 설정합니다.

if(answer<=0){
	answer=-1;
	break;
}

만약 체력이 0이하가 된다면 for문을 벗어나고 -1을 출력합니다.

1. 문제

전체 학생의 수 n,

체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 

여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때,

 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

2. 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

//n : 전체 학생의 수
//lost : 체육복을 도난당한 학생들의 번호 배열
//reserve : 여벌의 체육복을 가져온 학생들의 번호 배열
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    //앞 뒤 수를 비교할 것이기 때문에 정렬 과정이 꼭 필요함
    sort(lost.begin(),lost.end());
    sort(reserve.begin(),reserve.end());
    
    //두가지 배열을 통해 벡터의 삽입,삭제를 진행하지 않고
    //체크를 했는지 표시해줌
    bool isChecked[31]={false};
    bool isCheckedReserve[31]={false};
    int coverNum=0;
    
    //먼저 같은 값들은 모두 true로 변경하고 빌려줌으로써 메꿀수 있는 사람수를 증가
    for(int i=0;i<reserve.size();i++)
    {
        for(int j=0;j<lost.size();j++){
            if(reserve[i]==lost[j]){
                isChecked[j]=true;
                isCheckedReserve[i]=true;
                coverNum++;
            }
        }
    }
    //그 후 남은 것들을 이용하여 앞뒤의 경우의 수를 통해 메꿀수 있는 학생 수 계산
    for(int i=0;i<reserve.size();i++){
        if(coverNum==lost.size())break;
        for(int j=0;j<lost.size();j++){
            if(isChecked[j]||isCheckedReserve[i]) continue;
            else if(lost[j]-1==reserve[i]||lost[j]+1==reserve[i])
            {
                coverNum++;
                isChecked[j]=true;
                isCheckedReserve[i]=true;
            }
        }
    }
    
    //정답 = 총학생수 - 잃어버린 체육복 수 + 메꾼 학생 수
    answer = n-lost.size()+coverNum;
    
    return answer;
}

3. 해설

//n : 전체 학생의 수
//lost : 체육복을 도난당한 학생들의 번호 배열
//reserve : 여벌의 체육복을 가져온 학생들의 번호 배열
int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    
    //앞 뒤 수를 비교할 것이기 때문에 정렬 과정이 꼭 필요함
    sort(lost.begin(),lost.end());
    sort(reserve.begin(),reserve.end());

먼저 경우의 수에서 예외 사항을 제외하기 위해 정렬을 진행해준다. 잃어버린 사람들과 여벌의 체육복을 가지고 있는 사람들의 배열을 정렬을 진행한다.

    //두가지 배열을 통해 벡터의 삽입,삭제를 진행하지 않고
    //체크를 했는지 표시해줌
    bool isChecked[31]={false};
    bool isCheckedReserve[31]={false};
    int coverNum=0;
    
    //먼저 같은 값들은 모두 true로 변경하고 빌려줌으로써 메꿀수 있는 사람수를 증가
    for(int i=0;i<reserve.size();i++)
    {
        for(int j=0;j<lost.size();j++){
            if(reserve[i]==lost[j]){
                isChecked[j]=true;
                isCheckedReserve[i]=true;
                coverNum++;
            }
        }
    }

각각 체크를 했는지 안했는지 기록할 배열 두개를 준비한다. 만약 여벌을 이미 빌려주고, 대여 받은 사람의 경우 체크할 필요가 없기 때문이다.

맨 처음 여벌을 준비한 학생이 잃어버렸을 경우를 체크해준다. (reserve[i]==lost[j]) 이 경우

    //그 후 남은 것들을 이용하여 앞뒤의 경우의 수를 통해 메꿀수 있는 학생 수 계산
    for(int i=0;i<reserve.size();i++){
        if(coverNum==lost.size())break;
        for(int j=0;j<lost.size();j++){
            if(isChecked[j]||isCheckedReserve[i]) continue;
            else if(lost[j]-1==reserve[i]||lost[j]+1==reserve[i])
            {
                coverNum++;
                isChecked[j]=true;
                isCheckedReserve[i]=true;
            }
        }
    }
    
    //정답 = 총학생수 - 잃어버린 체육복 수 + 메꾼 학생 수
    answer = n-lost.size()+coverNum;
    
    return answer;
}

그 후 체크하지 않은 값들을 다시 체크해준다. 이 경우 여벌을 가지고 있는 학생의 id번호 앞뒤인지 아닌지를 체크해주면서 만약 여벌을 빌려주면 coverNum의 값을 높여준다. 이때 coverNum은 말그대로 얼만큼 잃어버린 학생들의 공백을 메꿀수 있는지 나타내는 변수이다.

따라서 정답은 총학생수에 잃어버린 체육복 수를 빼고 메꾼 학생 수를 더해주면 된다.

1. 문제

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

2. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> nums;
string aeiou[5]={"A","E","I","O","U"};

void repeatPermutation(string s, int maxLength)
{
    if(maxLength==s.size()) //문자열의 크기 == 채울 문자열 크기
    {
        nums.push_back(s);
        return; //재귀함수 종료
    }
    
    for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
    }
}

int solution(string word) {
    int answer = 0;
    
    for(int i=1;i<=5;i++){
        repeatPermutation("",i);
    }
    
    sort(nums.begin(), nums.end());  

    for(int i=0;i<nums.size();i++){
        if(word==nums[i]){
            answer=i;
            break;
        }
    }
       
    return answer+1;
}

3. 해설

vector<string> nums;
string aeiou[5]={"A","E","I","O","U"};

void repeatPermutation(string s, int maxLength)
{
    if(maxLength==s.size()) //문자열의 크기 == 채울 문자열 크기
    {
        nums.push_back(s);
        return; //재귀함수 종료
    }
    
    for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
    }
}

int solution(string word) {
    int answer = 0;
    
    for(int i=1;i<=5;i++){
        repeatPermutation("",i);
    }

재귀 함수를 통해서 모든 경우의 수를 저장합니다.

경우의 수는 1자리일 때, 2자리일 때, 3자리일 때, 4자리일 때, 5자리일 때 모든 경우의 수를 구해야합니다.

따라서 1자리의 경우

for(int i=0;i<5;i++){
        repeatPermutation(s+aeiou[i],maxLength); //재귀함수 호출
}

이 부분이 aeiou[0] ~aeiou[4] 까지의 값이 한번씩 호출 되면서 끝납니다.

2자리의 경우 위의 for문이 aeiou[0]+aeiou[0]~aeiou[4] 에서부터 aeiou[4]+aeiou[0]~aeiou[4] 까지 계산함으로 총 25가지의 문자열이 저장됩니다.

이와 같은 방법으로 5자리의 경우까지 재귀함수를 통해 저장합니다. 

sort(nums.begin(), nums.end());  

    for(int i=0;i<nums.size();i++){
        if(word==nums[i]){
            answer=i;
            break;
        }
    }
       
    return answer+1;
}

그 후, 사전적 배열로 나열해줘야합니다.

기존에 저장된 배열은 A,E,I,O,U,AA,AE,AI,AO,AU.... 등의 순서로 구성되어 있습니다.(함수 호출 순서에 따라 달라질 수 있으나 (1자리수...2자리수...3자리수.... 로 저장)

기본적으로 sort 함수는 string 변수에서 사전적 순서로 정렬해주기 때문에 별도의 판별 함수를 넣지 않아도 됩니다.

그 후 for문을 통해 받은 word 값과 nums[i]의 값이 같다면 해당 번호를 뽑아냅니다.

벡터는 0번부터 시작하기에 +1을 해주면 몇번째 수인지를 도출할 수 있습니다.

※ for문을 쓰지 않고 find() 함수를 통해서 한줄로 해결할 수도 있습니다.

1. 문제

출처:https://school.programmers.co.kr/learn/courses/30/lessons/86971

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

2. 코드

#include <string>
#include <vector>

using namespace std;

//dfs, visited 방법

int graph[101][101];
int visited[101];

int dfs(int cur, int n)
{
    if(visited[cur]) return 0;      //한번 방문한 곳은 재방문 X
    int child=1;      //하위 노드의 갯수
    visited[cur]=true;
    for(int i=1;i<=n;i++)
    {
        if(graph[cur][i])       //연결, 간적 없는 곳만
        {
            child+=dfs(i,n);
        }
    }
    return child;
}

void setGraph(int x,int y,int value)
{
    graph[x][y]=value;
    graph[y][x]=value;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    
    //연결되어 있는 모든 송전탑 1로 초기화
    for(int i=0;i<wires.size();i++){
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    for(int i=0;i<wires.size();i++){
        //방문 배열 초기화
        fill_n(visited,101,false);
        
        //끊을 전선 0으로 만들어주기 -> 전선 끊기
        setGraph(wires[i][0],wires[i][1],0);

        vector<int> diff;
        for(int i=1;i<=n;i++)
        {
            int tmp=dfs(i,n);       //깊이 탐색
            if(!tmp)continue;       //방문한 경우 생략
            diff.push_back(tmp);
        }
        answer = min(answer, abs(diff[0]-diff[1]));
        if(answer==0)break;
        //원상태로 돌려놓기
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    return answer;
}

3. 해설

//dfs, visited 방법

int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    
    //연결되어 있는 모든 송전탑 1로 초기화
    for(int i=0;i<wires.size();i++){
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    for(int i=0;i<wires.size();i++){
        //방문 배열 초기화
        fill_n(visited,101,false);
        
        //끊을 전선 0으로 만들어주기 -> 전선 끊기
        setGraph(wires[i][0],wires[i][1],0);

        vector<int> diff;
        for(int i=1;i<=n;i++)
        {
            int tmp=dfs(i,n);       //깊이 탐색
            if(!tmp)continue;       //방문한 경우 생략
            diff.push_back(tmp);
        }
        answer = min(answer, abs(diff[0]-diff[1]));
        if(answer==0)break;
        //원상태로 돌려놓기
        setGraph(wires[i][0],wires[i][1],1);
    }
    
    return answer;
}

dfs를 이용해서 풀어야하는 문제이다. 처음에 문제를 접근할 때 dp로 접근하여서 노드의 하위 갯수를 누적하였었는데 해당 경우는 노드가 정렬되어 있지 않을 때 적합하지 않기 때문에 사용할 수 없었다.

푸는 순서는 다음과 같습니다.

1. 먼저 연결되어 있는 모든 송전탑들을 2차원 배열에 1로 표시해줍니다.

    //연결되어 있는 모든 송전탑 1로 초기화
    for(int i=0;i<wires.size();i++){
        setGraph(wires[i][0],wires[i][1],1);
    }

2. 0~n번째 송전탑을 각각 끊는 for 문을 이용하여 n번 돌려줍니다.

    for(int i=0;i<wires.size();i++){

3. 방문 배열을 초기화 해주고, 2차원 배열에서 끊을 송전탑을 0으로 만들어줍니다.

        //방문 배열 초기화
        fill_n(visited,101,false);
        
        //끊을 전선 0으로 만들어주기 -> 전선 끊기
        setGraph(wires[i][0],wires[i][1],0);

4. dfs 탐색을 통해 방문하지 않고 연결이 끊어지지 않은 곳까지 탐색을 하여 하위 노드의 갯수를 반환하고 그 값들의 차이를 반환합니다.

        vector<int> diff;
        for(int i=1;i<=n;i++)
        {
            int tmp=dfs(i,n);       //깊이 탐색
            if(!tmp)continue;       //방문한 경우 생략
            diff.push_back(tmp);
        }
        answer = min(answer, abs(diff[0]-diff[1]));
        if(answer==0)break;
        //원상태로 돌려놓기
        setGraph(wires[i][0],wires[i][1],1);

1. 문제

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/87946

유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

2. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

//수열 next_permutation을 활용하여서 풀이
//경우의 수를 다 계산한 다음 차례로 검증함
int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    vector<int> v;
    // 0부터 던전 사이즈까지 벡터에 저장
	for(int i=0; i<dungeons.size(); i++){
		v.push_back(i);
	}
    
    do{
        int pirodo=k;
        int count=0;
		for(int i=0; i<v.size(); i++){
            if(pirodo>=dungeons[v[i]][0]){
                //피로도 차감 및 던전 갯수 올리기
                count++;
                pirodo-=dungeons[v[i]][1];
            }
		}
        answer=max(answer,count);
	}while(next_permutation(v.begin(),v.end()));
    
    return answer;
}

3. 해설

//수열 next_permutation을 활용하여서 풀이
//경우의 수를 다 계산한 다음 차례로 검증함
int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    vector<int> v;
    // 0부터 던전 사이즈까지 벡터에 저장
	for(int i=0; i<dungeons.size(); i++){
		v.push_back(i);
	}

경우의 수가 많지 않기에 완전 탐색을 통해 풀수 있는 문제이다.

정해진 배열에서 순서를 바꾸는 경우의 수를 구할 때는 수열을 사용해서 만들어준다.

먼저 0~ 던전의 갯수 까지의 배열을 만들어준다.

만약 던전의 갯수가 3이라면 [0,1,2] 가 만들어진다.

  do{
	int pirodo=k;
	int count=0;
	for(int i=0; i<v.size(); i++){
        	if(pirodo>=dungeons[v[i]][0]){
                //피로도 차감 및 던전 갯수 올리기
                count++;
                pirodo-=dungeons[v[i]][1];
            }
	}
    	answer=max(answer,count);
}while(next_permutation(v.begin(),v.end()));

만들어진 배열을 가지고 next_permutation() 함수를 통해서 수열의 경우의 수를 출력한다.

do while문을 통해 수열의 경우의 수를 받아올 때 피로도와 던전이 필요한 최소 피로도를 넘긴다면 던전을 클리어하도록 설계한다.

만약 최소 피로도를 넘기지 못하면 계산하지 않고 넘어간다.

계산이 끝난 후 만약 Count가 기존의 answer보다 클 경우 answer에 count 값을 삽입한다.

1. 문제

원본 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42842

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

2. 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    //완전 탐색
    int sum = brown+yellow;
    for(int i=2;i<sum;i++){
        if(sum%i!=0) continue;
        else
        {
            if((i-2)*(sum/i-2)==yellow)
            {
                answer.push_back(sum/i);
                answer.push_back(i);
                break;
            }
            else continue;
        }
    }
    
    return answer;
}

3. 해설

//완전 탐색
    int sum = brown+yellow;
    for(int i=2;i<sum;i++){
        if(sum%i!=0) continue;

먼저 brown+yellow를 더하면 모든 타일의 갯수를 구할 수 있습니다.

타일의 갯수는 가로x세로의 경우의 수를 구할 수 있기에 구해줍니다.

타일의 세로 길이는 1보다 커야하기에(0이나 1인 경우 노란색 구역이 생길 수 없음) i=2부터 for문을 돌려줍니다.

if(sum%i!=0) : 만약 나누어 질수 없는 경우라면 가로 세로를 구할수 없기 때문에 계산하지 않고 넘어갑니다.

        else
        {
            if((i-2)*(sum/i-2)==yellow)
            {
                answer.push_back(sum/i);
                answer.push_back(i);
                break;
            }
            else continue;
        }
    }

나누어지는 경우라면, 해당 가로 세로의 길이에서 2씩 빼서 yellow 영역의 갯수를 구합니다.

만약 yellow 갯수가 맞다면 해당 값들을 answer에 저장해줍니다.

1. 문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다.

흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

2. 코드

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int solution(string numbers) {
    int answer=0;
    
    //next_permutation을 사용
    //순열 계산에서 1자리,2자리 ~ n자리만 사용하는 모든 경우의 수 구하기
    sort(numbers.begin(),numbers.end());
    vector<unsigned int> nums;
    string sub;
    do {
        for (int i = 1; i <=  numbers.size(); i++)
        {
            sub = numbers.substr(0, i);
            nums.push_back(stoi(sub));
        }
    } while (next_permutation(numbers.begin(), numbers.end()));
    
    //중복된 숫자 제거하기
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(),nums.end()), nums.end());
    
    //에라토스테네스체 구하기
    unsigned int nn=9999999;
    vector<bool> isPrimeNum(nn+1);
    isPrimeNum[1] = true; // 1은 소수가 아니므로 true
    for(unsigned int i = 2; i <= sqrt(nn); i++){
        if(isPrimeNum[i]) continue; // 이미 true면 계산 제외
        for(unsigned int j = i + i; j <= nn; j += i) // i를 제외한 i의 배수들은 소수가 아니다.
            isPrimeNum[j] = true;
    }

    for(int i=0;i<nums.size();i++){
	    if(!isPrimeNum[nums[i]]&nums[i]>0)      //0인 경우 제외
            answer++;
    }
    
    return answer;
}

3. 해설

    //next_permutation을 사용
    //순열 계산에서 1자리,2자리 ~ n자리만 사용하는 모든 경우의 수 구하기
    sort(numbers.begin(),numbers.end());
    vector<unsigned int> nums;
    string sub;
    do {
        for (int i = 1; i <=  numbers.size(); i++)
        {
            sub = numbers.substr(0, i);
            nums.push_back(stoi(sub));
        }
    } while (next_permutation(numbers.begin(), numbers.end()));

먼저 경우의 수를 구하기 위해서 string을 정렬해주고, next_permutation 함수를 통해 1~n자리의 모든 경우의 수를 구합니다.

    //중복된 숫자 제거하기
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(),nums.end()), nums.end());

그 후, 중복 경우의 수가 있을 수 있으므로, 중복된 숫자를 제거해줍니다.

    //에라토스테네스체 구하기
    unsigned int nn=9999999;
    vector<bool> isPrimeNum(nn+1);
    isPrimeNum[1] = true; // 1은 소수가 아니므로 true
    for(unsigned int i = 2; i <= sqrt(nn); i++){
        if(isPrimeNum[i]) continue; // 이미 true면 계산 제외
        for(unsigned int j = i + i; j <= nn; j += i) // i를 제외한 i의 배수들은 소수가 아니다.
            isPrimeNum[j] = true;
    }

에라토스테네스체의 해 알고리즘을 이용하여 주어진 범위 내에서 소수가 아닌 값들을 true로 표시해줍니다.

    for(int i=0;i<nums.size();i++){
	    if(!isPrimeNum[nums[i]]&nums[i]>0)      //0인 경우 제외
            answer++;
    }

소수 판별 vector isPrimeNum을 가지고 경우의 수들의 리스트 nums의 값과 비교하여 만약 소수가 아닌 경우(false) answer을 한개 늘려줍니다.

경우의 수가 0인경우는 소수가 아니기 떄문에 제외합니다.

큐를 가장 쉽게 이해하는 방법은 줄을 서서 하는 싸인회를 생각하면 된다.
예를 들어서 유명 가수의 싸인회가 열린다고 가정해보자
나는 가수의 싸인회에 당첨이 되었고 현장에서 3번의 번호를 부여받았다.
다른 팬들은 1~20번의 번호를 부여받았다고 가정하였을 때, 진행자가 1번부터 싸인을 받으러 오라고 부를 것이다.
그리고 2~20번의 사람들에게 차례로 줄을 서라고 할 것이고 그 다음 차례는 2번부터 순서대로 싸인을 받으러 줄을 이탈할 것이다.
이게 바로 큐의 개념이다! FIFO(First In First Out) 선입선출 자료구조이다.
먼저 들어간 데이터는 먼저 빠져나온다. 즉 2번이 맨 앞에 있는데 3번이 먼저 빠져나갈 수 없다는 것이다.

큐가 쓰이는 구조는 어디에 있을 까? 미루어 짐작해보건데
명절날 내려가는 KTX 예매를 할 때, 내 앞의 대기자 00명이 있습니다. 라는 문구를 본 적 있는가?
아마도 그러한 곳에 쓰일 것 같다.
물론 이것 말고도 많은 곳에 쓰이겠지만 가장 가시적으로 볼 수 있는 느낌이 아닐까 싶다.

스택은 굉장히 많이 쓰이는 개념이다.
’가장 먼저 들어간 데이터가 가장 마지막에 나오는(FILO, First In Last Out) 구조‘ 이다.
배열과 링크드 리스트 둘다 구현 가능한데 이전 포스팅에서 언급했듯이
탐색은 빠른 배열, 용량의 제한이 자유로운 링크드 리스트 이기에 데이터의 종류에 따라 다르게 쓰일 듯하다.

스택은 말그대로 쌓다 인데, 가장 와닿는 것은 프링글스 통이 아닐까 싶다..!
물론 프링글스를 뒤집으면 우르르 쏟아져나온다만은.. 프링글스는 위에서부터 꺼내서 제일 밑에까지 먹을 수 있는 과자이다.
반대로 프링글스 통에 과자를 다시 넣는다면 맨 마지막에 넣은 과자부터 꺼낼 수 있을 것이다.

스택을 사용하여서 어떤 것을 만들면 유용할까 하고 생각하여보았는데
아무래도 Undo, Redo 아닐까 싶다.
한글(.hwp)에서도 잘 볼 수 있는데, 단축키 Ctrl+Z 를 통해 이전의 작업으로 돌아가는 기능 말이다.
이전의 작업들을 한개한개씩 쌓아놓고, 만약 되돌아가기를 실행한다면 한큐에 작업했던 것들을 제거하면 이전의 작업으로 돌아갈 수 있을 것이다.

프로그램을 짜다보면 배열을 사용할 때가 많아진다.

배열은 크기가 한정되어 있기 때문에 공간이 모자라는 경우가 종종 생길 수 있는데, C++을 사용하는 사람들은 STL의 vector를 보통 떠올린다. 나의 경우도 그랬고

하지만 STL의 vector 경우 크기에 상관없이 자유자재로 늘어나는 것처럼 보이지만 배열 형태에서 배열이 가득 찰 때마다 크기를 1.5배 ~ 2배 (컴파일러에 따라 다름) 늘린 후 다시 옮겨담는 형식이라고 한다.

따라서 링크드 리스트랑은 다른 개념이다.

링크드 리스트는 C에서 배열의 크기가 한정되어 있는 한계를 극복하고자 만든 개념이다.

하지만 여러가지 장단점이 있기에 소개하려고 한다.

🔹01. 링크드 리스트

유연하게 크기를 바꿀 수 있는 구조를 보고 '리스트(list)'라고 하는데, 링크드 리스트는 이 중에서 가장 간단히 구현하는 방법이다.

'리스트' 내의 각 요소는 '노드(Node)' 라고 부른다.

'링크드'는 '연결된' 이라는 뜻이다. 즉 링크드 리스트는 연결된 리스트이다.

구조

노드는 데이터와 포인터를 가진 구조입니다.

포인터는 뒤에올 노드를 가르킴으로써 해당 포인터를 이용해 다음 노드를 탐색할 수 있다.

첫 번째 노드를 헤드, 마지막 노드를 테일이라고 부른다.

마치 KTX 기차를 이어붙이는 것 처럼 뒤를 이어서 붙인다.

기차 사이의 이음새 역활을 하는 고리가 노드의 포인터가 하는 역할이다.

struct Node
{
    Data data;		//데이터
    struct Node* NextNode;	//다음 노드를 가리키는 포인터
}

링크드 리스트를 설정하기 위해서는 코드블록이 종료됨에 따라 사라지지 않도록 malloc() 함수를 통해 할당을 해준다.

이러한 링크드 리스트는 탐색 연산에서 약점을 가지고 있다.

앞에서부터 쭈욱 연결된 구조이다 보니 HEAD부터 탐색을 시작해서 만약 10개의 노드 중 10번째 노드를 찾으려고 한다면 1번부터 탐색해서 10번까지 다달아야한다.

따라서 n개의 노드 중 n번째 노드를 찾으려고 한다면 n번 탐색을 진행해야하기에 비용이 크고 속도가 느리다.

❗배열에 비해 링크드 리스트의 장단점 정리❗

🔸단점🔸

  1. 포인터 때문에 각 노드마다 4 byte의 메모리가 추가로 필요함

  2. 최약의 경우 n회의 노드 탐색 루프 -> 비용이 크고 속도가 느림

🔸장점🔸

  1. 새로운 노드의 추가,삽입,삭제가 쉽고 빠름

따라서, 링크드 리스트는 추가,삽입,삭제가 잦고 조회는 드문 곳에 유용하다.

🔹02. 더블 링크드 리스트

더블 링크드 리스트는 링크드 리스트의 탐색 기능을 개선한 자료구조이다.

이전 노드를 참조하는 포인터를 하나 더 Node 안에 만들어서 양방향 탐색이 가능하도록 만들었다.

🔹03. 환형 링크드 리스트

환형 링크드 리스트는 헤드와 테일을 연결한 링크드 리스트이다.

이러한 방법을 사용하면 테일에 접근하는 비용이 작아져서, 뒤에서부터 노드를 찾아 나가는 탐색을 구현할 수 있다.

예를들어 10개의 노드 중 8번째를 찾고 싶다면 HEAD에서 TAIL로 2번 탐색하면 더 빠르게 찾을 수 있다.

🔅알아두면 좋은 TIP🔅

유연하게 크기를 바꿀 수 있는 구조를 보고 '리스트(list)'라고 하는데,

C++ STL vector도 리스트의 일종이라고 볼 수 있겠다.

여기서 C++ STL vector 는 동적 배열의 형태이고,

C++ STL list는 더블 링크드 리스트로 구성되어있다고 한다.

문제

1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타낸다.

(1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸의 수를 구하는 프로그램 작성하시오.

입력 1

4 6
101111
101010
101011
111011

출력 1

15

코드

#include<iostream>
#include<queue>
#include<algorithm>
#define MAX 101

using namespace std;

int MAP[MAX][MAX];
int visited[MAX][MAX];
int dist[MAX][MAX];
int arrow[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int N, M;
pair<int, int> startP, endP;

queue < pair<int, int>> Q;

void BFS() {
    
    Q.push(make_pair(startP.first, startP.second));

    dist[startP.first][startP.second]++;
    visited[startP.first][startP.second] = 1;

    while (!Q.empty()) {
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();
        //좌우위아래 탐색
        for (int i = 0; i < 4; i++) {
            int ny = y + arrow[i][0];
            int nx = x + arrow[i][1];


            if ((nx >= 0 &&nx < M) && (ny >= 0 && ny < N)
                && MAP[ny][nx] == 1 &&!visited[ny][nx]) {
                visited[ny][nx] = 1;
                Q.push(make_pair(ny, nx));
                dist[ny][nx] = dist[y][x] + 1;
            }
        }
    }
    cout << dist[endP.first-1][endP.second-1];
}


void input() {
    string num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        for (int j = 0; j < M; j++) {
            MAP[i][j] = num[j]-'0';
        }
    }
}

int main() {

    cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

    int tmp;
    cin >> N>>M;
    startP = make_pair(0, 0);
    endP = make_pair(N, M);
    
    input();
    BFS();

    return 0;
}

*간단한 해설*

저 input 함수에서 cin을 통해 MAP을 받아옵니다.

주의할 점은 한 줄당 붙어있는 상태로 받아와서 cin으로 받은 다음 끊어서 저장해주어야합니다.

void input() {
    string num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        for (int j = 0; j < M; j++) {
            MAP[i][j] = num[j]-'0';
        }
    }
}

string으로 받은 다음 string에서 인자로 접근해주면 char 형이여서 char형을 int로 바꾸려면 '0'의 숫자를 빼주면 됩니다.

그런다음 BFS 탐색을 통해 최단 경로를 찾아주면 되는데 BOJ 6087번 레이저 통신과 문제가 매우 흡사합니다.

https://dana3711.tistory.com/90

다만 다른점은 목표 지점까지 가는데 걸리는 비용을 출력해야한다는 점입니다. 따라서

if ((nx >= 0 &&nx < M) && (ny >= 0 && ny < N)&& MAP[ny][nx] == 1 &&!visited[ny][nx]) 
{
    visited[ny][nx] = 1;
    Q.push(make_pair(ny, nx));
    dist[ny][nx] = dist[y][x] + 1;
}

4방향 탐색을 할때 만약 맵 안에 있고((nx >= 0 &&nx < M) && (ny >= 0 && ny < N)), 그 칸이 이동할 수 있는 칸이라면(MAP[ny][nx] == 1) 해당 칸을 방문하지 않았을 때

해당 칸으로 자리를 이동하고 가는 비용을 +1 해줍니다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

거울을 설치하면 방향을 90도 회전시킬 수 있다.

*은 벽으로 뚫고 지나갈 수 없다.

거울을 최소로 설치하여서 처음 시작지점 C에서 끝지점 C에 도달할때까지 가야한다.

최소로 설치할 수 있는 거울 수를 출력하라

입력 1

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

출력 1

3

코드

#include<iostream>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>

using namespace std;

//6087번 레이저 통신

char MAP[101][101];
int visited[101][101];
int w, h;
int arrow[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

pair<int, int> startP, endP;
queue<pair<int,int>> cntDir;
queue < pair<int, int>> Q;
void BFS() {
    for (int i = 0; i < 4; i++) {
        Q.push(make_pair(startP.first, startP.second));
        cntDir.push(make_pair(0, i));
    }
    visited[startP.first][startP.second] = 0;

    while (Q.empty() == 0) {
        int y = Q.front().first;
        int x = Q.front().second;
        int cnt = cntDir.front().first;
        int dir = cntDir.front().second;
        Q.pop();
        cntDir.pop();
        //좌우위아래 탐색
        for (int i = 0; i < 4; i++) {
            int ny = y + arrow[i][0];
            int nx = x + arrow[i][1];
            int nCnt = cnt;

            if (nx <0 || nx >= w || ny < 0 || ny >=h) continue;
            if (MAP[ny][nx] == '*') continue;
            if (dir != i) nCnt++;
            if (visited[ny][nx] >= nCnt) {
                visited[ny][nx] = nCnt;
                Q.push(make_pair(ny, nx));
                cntDir.push(make_pair(nCnt, i));
            }
        }
    }
    cout << visited[endP.first][endP.second];
}

void input() {
    bool isFirst = true;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'C') {
                (isFirst) ? startP = make_pair(i, j) : endP = make_pair(i, j);
                isFirst = false;
            }
            visited[i][j] = 10001;
        }
    }
}

int main() {

    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> w >> h;
    
    input();
    BFS();


    return 0;
}

*간단한 해설*

void input() {
    bool isFirst = true;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'C') {
                (isFirst) ? startP = make_pair(i, j) : endP = make_pair(i, j);
                isFirst = false;
            }
            visited[i][j] = 10001;
        }
    }
}

먼저 input 함수에서 cin을 통해 MAP을 받아옵니다.

그 중 만약 C가 입력되었다면 처음인지 아닌지를 판단해서 처음이라면 startP에 해당 위치를 넣고, 처음이 아니라면 endP에 해당 위치를 넣는다.

void BFS() {
    for (int i = 0; i < 4; i++) {
        Q.push(make_pair(startP.first, startP.second));
        cntDir.push(make_pair(0, i));
    }
    visited[startP.first][startP.second] = 0;

    while (Q.empty() == 0) {
        int y = Q.front().first;
        int x = Q.front().second;
        int cnt = cntDir.front().first;
        int dir = cntDir.front().second;
        Q.pop();
        cntDir.pop();
        //좌우위아래 탐색
        for (int i = 0; i < 4; i++) {
            int ny = y + arrow[i][0];
            int nx = x + arrow[i][1];
            int nCnt = cnt;

            if (nx <0 || nx >= w || ny < 0 || ny >=h) continue;
            if (MAP[ny][nx] == '*') continue;
            if (dir != i) nCnt++;
            if (visited[ny][nx] >= nCnt) {
                visited[ny][nx] = nCnt;
                Q.push(make_pair(ny, nx));
                cntDir.push(make_pair(nCnt, i));
            }
        }
    }
    cout << visited[endP.first][endP.second];
}

탐색을 시작할 위치인 startP의 위치를 4번 Q에 옮겨담습니다. 시작 위치에서 위,아래,왼쪽,오른쪽 방향을 탐색하는 방향을 저장해줍니다. 방향이 다르다면 거울의 갯수를 더해줘야하기 때문입니다. 

그 다음 Q가 빌때까지 while문을 돌립니다. Q의 첫번째 인자를 변수에 담고 좌우위아래 탐색을 시작합니다. 탐색에서 *인 벽을 만나거나 맵을 벗어나면 탐색을 건너뛰고, 만약 가던 방향과 현재 방향이 맞지 않다면 거울을 더해줍니다. 현재 방문한 위치에서의 거울을 사용한 갯수를 visited[][] 배열에 저장하기에 만약 사용한 갯수가 현재 카운트보다 높다면 최소로 사용해야하기때문에 변경해줍니다. 이것을 끝지점에 도달할때까지 계속 반복하여서 visited[끝지점.y][끝지점.x] 의 값을 출력하면 답이 됩니다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

입력 1

1000

출력 1

228875

코드

#include<iostream>
#include<cmath>

using namespace std;

//2749번 피보나치 수 3
//피사노 주기를 이용

long long arr[1500050];     //메모이제이션
int m = 1000000;            //나누는 수
int cycle;

int cycle_func() {
    int k=0,tmp=m;
    while (tmp > 1) {
        tmp /= 10;
        k++;
    }

    return 15 * pow(10, k - 1);
}

void pisano_fibo() {
    arr[0] = 0;
    arr[1] = 1;
    //파사노 주기에 의하여 1500000의 값들이 반복된 후에 다시 재 반복됨
    cycle = cycle_func();
    for (int i = 0; i < cycle; i++) {
        arr[i + 2] = (arr[i+1]+arr[i])%m;
    }
}

int main() {

    cin.tie(NULL);cout.tie(NULL);
    ios::sync_with_stdio(false);

    long long n;
    cin >> n;
    pisano_fibo();
    cout << arr[n % cycle];

    return 0;
}

*간단한 해설*

피사노 주기를 이용하여 푸는 문제이다 기본적으로 n의 범위가 1,000,000,000,000,000,000보다 작거나 같은 자연수 이기 때문에 기존에 쓰던 재귀함수를 이용하여서 푸는 방법은 시간이 매우 오래 걸리므로 쓸수가 없다. 따라서 피사노 주기를 통해 반복 주기를 찾고 그 주기동안의 피보나치 수열에서 m으로 나눈 나머지 값들을 배열에 저장한다. 그 후 저장한 배열에서 찾고자 하는 n번째가 주기에서 몇번째 숫자인지 찾아내서 해당 배열의 값을 출력하면 된다. 피사노 주기는

나누는 값을 M이라고 지칭했을 때,

M=10^k , cycle = 15 x 10^(k-1)

이다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

두 다각형이 주어졌을 때, 두 다각형의 민코프스키 합을 구하는 프로그램을 작성하시오. 만약 민코프스키 합이 여러 개의 다각형으로 이루어진다면 다음의 우선순위에 따라 하나의 다각형만을 구하도록 한다. 번호가 작은 것이 우선순위가 높은 것이다.

입력 1

3 3
0 0
1 0
1 1
0 1
0 0
1 0

출력 1

5
0 0
2 0
2 1
1 2
0 1

코드

#include<iostream>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;

//2244번 민코프스키 합
//Convex Hull(CCW(Counter Clock Wise)) 사용

typedef pair<long long, long long> Point2f;
Point2f a[1010];
Point2f b[1010];

//counter clock wise : 좌회전하는지 판단
//벡터 AB와 벡터 AC의 CW/CCW
// 0보다 크면 반시계방향으로 도는 것, 0보다 작으면 시계방향으로 도는 것
//int에 1LL을 곱해주면 long long으로 형변환을 쉽게 할 수 있음
int ccw(Point2f a, Point2f b, Point2f c) {
    long long res = a.x * b.y + b.x * c.y + c.x * a.y;
    res -= b.x * a.y + c.x * b.y + a.x * c.y;
    if (res > 0) return 1;          //시계 반대방향
    if (res) return -1;             //시계 방향
    return 0;                           //평면상
}

long long dist(Point2f a, Point2f b) {
    long long dx = 1LL*a.x - b.x;
    long long dy = 1LL * a.y - b.y;
    return dx * dx + dy * dy;
}

int main() {

    vector<Point2f> arr;
    int aNum, bNum;
    int xTmp, yTmp;
    int pIdx = 0;
    cin >> aNum >> bNum;
    pIdx = aNum * bNum;
    for (int i = 0; i < aNum; i++) {
        cin >> xTmp >> yTmp;
        a[i].x = xTmp; a[i].y = yTmp;
    }
    for (int i = 0; i < bNum; i++) {
        cin >> xTmp >> yTmp;
        b[i].x = xTmp; b[i].y = yTmp;
    }
    //모든 가능성이 있는 점들 vector 제작
    for (int i = 0; i < aNum; i++) {
        for (int j = 0; j < bNum; j++) {
            arr.push_back(Point2f{ a[i].x + b[j].x,a[i].y + b[j].y });
        }
    }

    //arr의 최소 값을 찾아서 0번 자리와 바꿈(0번을 제일 작은 값으로 설정)
    swap(arr[0], *min_element(arr.begin(), arr.end()));
    //0번을 제외한 점들을 반시계 방향으로 정렬
    //[&]{}는 람다식으로써 해당 함수에따라서 sort를 할지 말지 결정함
    sort(arr.begin() + 1, arr.end(), [&](Point2f& a, Point2f& b) {
        int cw = ccw(arr[0], a, b);
        //cw가 0 이상이면 반시계 방향이고 true를 반환 0이면 false 반환, cw가 -1인 경우(시계 방향) if문을 들어오지 않음
        if (cw) return cw > 0;          
        return dist(arr[0], a) < dist(arr[0], b); //cw가 -1인 경우 기준점 arr[0]에서의 거리순으로 정렬
        });

    vector<Point2f> hull;
    for (int i = 0; i < arr.size();i++) {
        while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), arr[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(arr[i]);
    }
    cout << hull.size() << "\n";
    for (int i = 0; i < hull.size(); i++) {
        cout << hull[i].x << " " << hull[i].y << "\n";
    }

    return 0;
}

*간단한 해설*

convex hull로 구현하면 되는 문제이다.

convex hull은 주어진 점에서 외곽선을 이루는 점들을 찾는 알고리즘인데 민코프스키의 합 또한 공간의 합을 계산하는 것이기 때문에 convex hull 알고리즘을 사용하여 구현하면 된다.

코드의 핵심적인 부분은 https://justicehui.github.io/ioi/2019/05/21/BOJ2244/ 에서 따왔다.

몇가지 람다식이라던지 auto와 같은 것들이 나에게 어려워서 for문으로 바꾸거나 주석을 달아서 진행해보았다. 기존의 다른곳에서 찾아서 convex hull을 구현해서 넣어보았는데 예제를 넣어보았을 때는 출력 결과가 잘나왔었다. 하지만 백준에서 테스트 할때마다 

이러한 런타임 에러나 출력 초과가 나와서 뭐가 문제인지 몰라서 다른 분 블로그를 보고 참고해서 해보았는데 아마 sorting하는 과정에서 에러가 난게 아닐까 싶다..

convex hull 알고리즘에 대한 글은 https://kbw1101.tistory.com/50 여기 블로그에 아주 친절하게 설명되어 있다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

입력 1

5 6
. . . . . .
. . X X . .
. . X . . .
. X X X X .
1
3

출력 1

. . . . . .
. . . . . .
. . X X . .
. . X X . .
. X X X X .

코드

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#define y first
#define x second
using namespace std;

//2933번 미네랄

//2차원 배열 선언
char arr[101][101];
int visited[101][101];      //dfs를 위한 방문 배열
int R, C;
vector<pair<int,int>> cluster;
int arrow[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

void DFS(int yIdx, int xIdx) {
    if (arr[yIdx][xIdx] == '.' || visited[yIdx][xIdx]) return;
    visited[yIdx][xIdx] = true;
    cluster.push_back({yIdx,xIdx});
    //좌우위아래 탐색
    for (int i = 0; i < 4; i++) {
        int ny = yIdx + arrow[i][0];
        int nx = xIdx + arrow[i][1];    
        if (nx >= 0 && nx < C && ny >= 0 && ny < R)
            DFS(ny, nx);
    }
}

void checkCluster() {
    memset(visited, 0, sizeof(visited));
    for (int a = 0; a < R; a++) {
        for (int b = 0; b < C; b++) {
            if (arr[a][b] == '.' || visited[a][b]) continue;
            cluster.clear();
            DFS(a,b);
            vector<int> low(C, -1);     //vector(컨테이너 크기, 각각 할당될 값)
            for (int z = 0; z < cluster.size(); z++) {
                pair<int, int> p= cluster[z];
                low[p.x] = max(low[p.x], p.y);
                arr[p.y][p.x] = '.';
            }

            //얼마나 밑으로 옮길지 i에 넣기
            int lowmove = R;
            for (int i, j = 0; j < C; j++) {
                if (low[j] == -1) continue;
                i = low[j];

                //'.'이 아닌경우, 탐색 높이가 높이보다 작은 경우
                while (i < R &&arr[i][j] == '.') {
                    i++;
                }
                lowmove = min(lowmove, i - low[j] - 1);
            }

            for (int i = 0; i < cluster.size(); i++) {
                pair<int, int> p = cluster[i];
                p.y += lowmove;
                arr[p.y][p.x] = 'x';
                visited[p.y][p.x] = true;
            }
        }
    }
    
}

void shoot(int orderNum,int height) {
    //왼쪽인지 오른쪽인지 판단
    height = R - height;
    if (orderNum % 2 == 0) {
        for (int i = 0; i < C; i++) {
            if (arr[height][i] == 'x') {
                arr[height][i] = '.';
                break;
            }
        }
    }
    else {
        for (int i = C-1; i >= 0; i--) {
            if (arr[height][i] == 'x') {
                arr[height][i] = '.';
                break;
            }
        }
    }
    
    checkCluster();
}

int main() {
    
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);


    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
        }
    }
    int N,height=0;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> height;
        shoot(i, height);
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << arr[i][j];
        }
        cout << "\n";
    }

    return 0;
}

*간단한 해설*

checkCluster() 함수 부분은 https://100100e.tistory.com/152 이 블로그 분의 글을 참고하여서 제작하였다. 제일 나랑 생각이 비슷하기도 했고 알기 쉽게 작성되어있어서 좋았다. checkCluster() 부분을 자세하게 설명해볼까 싶다.

 memset(visited, 0, sizeof(visited));
    for (int a = 0; a < R; a++) {
        for (int b = 0; b < C; b++) {

checkCluster는 부메랑을 던진 후에 떨어지는 클러스터들을 판단하기 위한 함수로써 실행된다. 따라서 DFS를 다시 사용하려면 visited 배열을 초기화 시켜줘야한다. 그를 위해 memset 함수를 이용하였다. 나머지 for문은 R x C 크기의 맵을 for문을 통해 돌린다.

if (arr[a][b] == '.' || visited[a][b]) continue;
cluster.clear();
DFS(a,b);

그 다음에는 해당 맵의 칸이 . 으로 비어있는 칸이거나 이미 방문한 배열일 경우 그대로 밑의 계산을 하지 않고 넘어간다. 그렇지 않은 경우 DFS 함수를 통해서 해당 클러스터를 기준으로 좌우위아래를 탐색해서 cluster 벡터에 넣는다.

vector<int> low(C, -1);     //vector(컨테이너 크기, 각각 할당될 값)
for (int z = 0; z < cluster.size(); z++) {
    pair<int, int> p= cluster[z];
    low[p.x] = max(low[p.x], p.y);
    arr[p.y][p.x] = '.';
}

그 후에  low 라는 땅에 가장 가까운 클러스터를 저장하는 벡터 배열을 선언한다. low(C,-1) 이렇게 선언하면 C 크기 만큼을 -1의 값으로 할당한다는 말이다. 그 다음 for문을 통해서 저장된 cluster만큼 돌려주고 만약 해당 클러스터의 높이 값인 p.y 값이 만약에 기존에 저장된 높이 값인 low[p.x]와 비교했을 때 큰 값을 low[p.x]에 저장해준다. 저장한 다음에는 해당 값은 나중에 다시 떨어진 클러스터 값으로 변경해줄 것임으로 미리 .으로 변경 시켜준다.

int lowmove = R;
for (int i, j = 0; j < C; j++) {
    if (low[j] == -1) continue;
    i = low[j];

    //'.'이 아닌경우, 탐색 높이가 높이보다 작은 경우
    while (i < R &&arr[i][j] == '.') {
        i++;
    }
    lowmove = min(lowmove, i - low[j] - 1);
}

얼만큼 밑으로 옮길지 계산하는 부분이다. lowmove 변수에는 가장 많이 내려갈 수 있는 값 높이 R값을 넣은 다음 비교해가면서 작으면 변경하는 형식이다. if(low[j]==-1) continue; 의 경우 땅에 가장 가까운 클러스터가 없는 경우에는 연산을 하지 않고 넘어간다. 그렇지 않을 경우 i = low[j];로 땅에 가장 가까운 클러스터의 높이를 넣는다. 그 후 while문을 통해서 만약 해당 좌표의 클러스터가 빈공간인 경우 내려가야할 칸의 값인 i를 ++해준다. 해당 while문이 긑나고 나면 min 함수를 통해 기존의 lowmove 값과 i-low[j]-1을 비교한다. arr[i][j]의 경우 아까 위에서 .으로 만들어놓았기 때문에 한개가 더 세어진다. 따라서 내려가야할 칸의 수 i 에서 -1을 한 다음 기존 높이인 low[j]를 빼주면 내려가야할 칸의 갯수가 나온다.

for (int i = 0; i < cluster.size(); i++) {
                pair<int, int> p = cluster[i];
                p.y += lowmove;
                arr[p.y][p.x] = 'x';
                visited[p.y][p.x] = true;
}

마지막으로 클러스터의 갯수 만큼 for문을 돌려서 lowmove 만큼 모든 클러스터를 옮겨준다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력 1

7
1
5
2
10
-99
7
5

출력 1

1
1
2
2
2
2
5

코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

//1655번 가운데를 말해요
//최소힙, 최대힙 사용
int main() {
    
    cin.tie(NULL);
    cout.tie(NULL);

    int N,temp;
    priority_queue<int> max;        //최대힙       우선순위 큐는 default로 less<in>를 사용
    priority_queue<int,vector<int>,greater<int>> min;       //최소힙
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> temp;

        (max.size() == min.size()) ? max.push(temp) : min.push(temp);

        if (!max.empty() && !min.empty()&& max.top() > min.top()) {
            //중간 값의 순서가 달라진다면 값 바꾸기
            int maxVal, minVal;
            maxVal = max.top();
            minVal = min.top();
            max.pop();
            min.pop();
            max.push(minVal);
            min.push(maxVal);
        }

        cout << max.top()<<"\n";
    }
    
    return 0;
}

*간단한 해설*

여러가지 알고리즘 중에서 무엇을 왜 쓰는지가 핵심인데 여기서는 최소힙, 최대힙을 사용한다.

그 이유는 힙은 여러개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르기 때문에 여기서 사용하면 빠른 연산이 가능하다.

힙은 일반적으로 완전 이진트리이므로 배열을 이용하여 구현한다.

최대 힙은 루트 노드로 올라갈수록 저장된 값이 커지는 구조이다. 

최소 힙은 루트 노드로 올라갈수록 값이 작아지는 구조이다.

이 문제의 경우 배열을 반틈으로 나누어서 한쪽은 최소 힙, 한쪽은 최대 힙을 사용하여 빠르게 연산하는 문제이다. 이 경우 priority_queue를 이용하여 구현할 수 있다. priority_queue는 힙을 이용하여 구현되어 있고 옵션을 이용하여 greater<int> 및 less<int>를 이용하여 위와같은 최소힙, 최대힙 구조를 만들 수 있다. 따라서 이를 통해서 중간값을 찾는 것이라 반틈을 나누어서 오름차순, 내림차순으로 정렬되는 최소힙, 최대힙을 이용하면 빠르게 통과하는 코드를 만들 수 있다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
2. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

*처음 봤을때 턴에 관한 개념이 잘 생성되지 않았는데 턴은 무조건 한번만 실행되는 시스템이다.

입력 1

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

출력 1

9

입력 2

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

출력 2

21

입력 3

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

출력 3

13

코드

#include<iostream>
//#include<Windows.h>
#include<deque>
#include<vector>

using namespace std;

int main() {
    
    int N, K,L;     //N : 보드의 크기, K : 다음 줄에 사과의 개수, L : 뱀의 방향 변환 횟수
    int column, row;
    int currentX=0, currentY=0;
    int arrIdx = 0, turnIdx=0;          //arrIdx : 방향배열 인덱스, turnIdx : 방향 회전배열 인덱스
    int arrow[4][2] = { {1,0},              //오른쪽
                        {0,1},              //아래
                        {-1,0},             //왼쪽
                        {0,-1} };           //위
    deque<vector<int>> body;

    cin >> N;

    //해당 배열만큼 2차원 행렬 만들기
    int** board = new int* [N];
    for (int i = 0; i < N; i++) {
        board[i] = new int[N];
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[i][j] = 0;
        }
    }

    board[0][0] = 1;
    vector<int> point;
    point.push_back(0);
    point.push_back(0);
    body.push_back(point);

    cin >> K;
    for (int i = 0; i < K; i++) {
        cin >> row >> column;
        board[row-1][column-1] = 2;
    }
    cin >> L;
    int* turn = new int[L];
    int* direction = new int[L];
    int lValue;
    char rValue;

    for (int i = 0; i < L; i++) {
        cin >> lValue >> rValue;
        turn[i] = lValue;
        direction[i] = rValue;
    }

    int time = 0;

    while (time < 10000) {
    
        /* {
            Sleep(1000);
            system("cls");

            cout << "Time :" << time+1 << endl;
            //출력해서 확인하기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    cout << board[i][j] << " ";
                }
                printf("\n");
            }
        }*/
        
        if (time == turn[turnIdx] && time != 0) {
            if (direction[turnIdx] == 'D') {
                arrIdx++;
            }
            if (direction[turnIdx] == 'L') {
                arrIdx--;
            }
            turnIdx++;
        }


        if (arrIdx > 3)
            arrIdx = arrIdx % 4;
        if (arrIdx < 0) {
            arrIdx = 4 + arrIdx;
        }

        //오른쪽으로 이동하는 것
        currentX += arrow[arrIdx][0];
        currentY += arrow[arrIdx][1];
       
        if ((currentX < 0 || currentX >= N) ||(currentY < 0 || currentY >= N))
            break;
        if (board[currentY][currentX] == 1)
            break;

        if (board[currentY][currentX] == 2) {
            //만약 사과가 있다면
            point.clear();
            point.push_back(currentY);
            point.push_back(currentX);
            body.push_front(point);

            for (size_t i = 0; i < body.size(); i++) {
                board[body[i][0]][body[i][1]] = 1;
            }
        }
        else {
            //맨끝의 값의 자리를 0으로 바꿔주기
            board[body.back()[0]][body.back()[1]] = 0;
            //처음의 값을 뒤로 밀어주기

            for (size_t  i = body.size() - 1; i >0 ; i--) {
                int temp = body[i-1][0];
                body[i][0] = temp;
                temp = body[i-1][1];
                body[i][1] = temp;
            }

            //첫번째 머리움직이기
            body[0][0]= currentY;
            body[0][1]= currentX;

            for (size_t i = 0; i < body.size(); i++) {
                board[body[i][0]][body[i][1]] = 1;
            }
        }

        time++;
    }

    cout << time + 1;

    //할당 해제
    for (int i = 0; i < N; i++)
        delete[] board[i];

    return 0;
}

*간단한 해설*

턴에 관한 개념이 처음에 잡히지 않아서 반복적으로 생성되는 줄 알고 시간을 많이 사용했다.

    Sleep(1000);
    system("cls");

    cout << "Time :" << time+1 << endl;
    //출력해서 확인하기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j] << " ";
        }
        printf("\n");
    }

이부분의 주석처리를 빼면 어떻게 실행되는지 확인해볼 수 있다.

예제의 3개의 출력 과정은 아래와 같다.

0이 빈칸이고 1은 뱀, 2는 사과이다.

사실 여기까지 와서 예제를 넣어보았을 때 제출을 하니까 틀린것으로 나왔었다.

테스트 케이스를 여러개 해보지 않아서 그런데 반례 케이스를 모아놓은 사이트를 찾았다.

https://www.acmicpc.net/board/view/56469

나의 경우 맨 처음 반례 케이스의 5번째까지 통과를 하니 통과를 할 수 있었다.

다른 분의 알고리즘을 찾아보니 이분꺼가 깔끔하게 정리되어 있었다.

내 코드는 for문을 많이 쓰는데 for문을 많이 쓰지 않도록 생각하는 힘을 좀 더 길러야겠다.

https://velog.io/@nacean/%EB%B0%B1%EC%A4%803190-%EB%B1%80-C-%ED%92%80%EC%9D%B4

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

1에서부터 6까지의 눈을 가진 3개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다.

1. 같은 눈이 3개가 나오면 10,000원+(같은 눈)×1,000원의 상금을 받게 된다. 
2. 같은 눈이 2개만 나오는 경우에는 1,000원+(같은 눈)×100원의 상금을 받게 된다. 
3. 모두 다른 눈이 나오는 경우에는 (그 중 가장 큰 눈)×100원의 상금을 받게 된다.  

예를 들어, 3개의 눈 3, 3, 6이 주어지면 상금은 1,000+3×100으로 계산되어 1,300원을 받게 된다. 또 3개의 눈이 2, 2, 2로 주어지면 10,000+2×1,000 으로 계산되어 12,000원을 받게 된다. 3개의 눈이 6, 2, 5로 주어지면 그중 가장 큰 값이 6이므로 6×100으로 계산되어 600원을 상금으로 받게 된다.

3개 주사위의 나온 눈이 주어질 때, 상금을 계산하는 프로그램을 작성 하시오.

입력 1

3 3 6

출력 2

1300

입력 2

2 2 2

출력 2

12000

입력 3

6 2 5

출력 3

600

코드

#include<iostream>

using namespace std;

bool equals(int rValue,int lValue, int* outValue) {
    if (rValue == lValue) {
        *outValue = rValue;
        return true;
    }
    else
        return false;
}

int main() {
    
    int firstDice, secondDice, thirdDice;
    int value=0;
    cin >> firstDice >> secondDice >> thirdDice;
    
    if (firstDice == secondDice&& secondDice == thirdDice) {     //만약 세개가 같은 값이면
        cout << 10000 + firstDice * 1000;
    }
    else if (equals(firstDice,secondDice,&value)
        || equals(secondDice, thirdDice, &value)
        || equals(firstDice, thirdDice, &value)) {     //만약 두개가 같은 값이면
        cout<<1000+ value *100;
    }
    else {
        //그 중 가장 큰눈
        value = max(max(firstDice, secondDice), thirdDice);
        cout << value * 100;
    }

    return 0;
}

*간단한 해설*

단계별로 풀어보기에서 if문 주제로 추가 분류된 문제여서 풀어보았다.

말그대로 간단하게 if-else if-else문을 통하여 총 3가지로 분류하면 된다.

 if (firstDice == secondDice&& secondDice == thirdDice)

이부분은 첫번째 주사위와 두번째 주사위의 숫자가 같고 두번째 주사위와 세번째 주사위의 숫자가 같을때, 'A와 B가 같고 B와 C가 같으면 A와 C는 같다'라는 공리를 통해 두가지의 원리가 true값을 반환한다면 자연스럽게 세 가지의 값이 모두 같음을 의미한다.

bool equals(int rValue,int lValue, int* outValue) {
    if (rValue == lValue) {
        *outValue = rValue;
        return true;
    }
    else
        return false;
}

equals()함수의 경우 else if문 안에서 만약 두개가 같은 값이면 value에 그 값을 집어넣어서 출력할때 쓸수 있게끔 제작하였다. 그중 outValue만 포인터를 사용한 이유는 rValue와 lValue의 경우 얕은 복사를 통해 숫자값만 들고와서 비교하면 되지만 outValue의 경우 해당 값을 넣어줘야하기때문에 깊은 복사가 필요해서 포인터를 사용하였다.

else {
        //그 중 가장 큰눈
        value = max(max(firstDice, secondDice), thirdDice);
        cout << value * 100;
    }

마지막으로 세개의 값이 모두 다른 경우 max()함수를 통해 먼저 첫번째 수와 두번째 수의 크기를 비교하고, 그 다음 비교한 큰 값과 세번째 수의 값을 비교하여 제일 큰 수를 value에 넣어서 출력하도록 하였다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

입력

4 5 1
1 2
1 3
1 4
2 4
3 4

출력

1 2 4 3
1 2 3 4

코드

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;

// 1260번 DFS와 BFS

//깊이 우선 탐색
void dfs(vector<int> inputGraph[], bool *visited,int index) {
	visited[index] = true;		//방문했음을 표시
	cout << index<<" ";
	//dfs 탐색 순서
	int grphSize = inputGraph[index].size();
	for (int i = 0; i < grphSize; i++) {
		int connectIdx = inputGraph[index][i];
		if (!visited[connectIdx])
			dfs(inputGraph, visited, connectIdx);
	}
}

//너비 우선 탐색
void bfs(vector<int> inputGraph[],bool *visited,int index) {
	queue<int> que;
	que.push(index);
	visited[index] = true;
	//bfs 탐색 순서
	while (!que.empty()) {
		int visitIdx = que.front();
		que.pop();
		cout << visitIdx<<" ";
		int grphSize = inputGraph[visitIdx].size();
		for (int i = 0; i < grphSize; i++) {
			//방문한 Idx와 연결된 원소들을 que에 넣기
			int connectIdx = inputGraph[visitIdx][i];
			if (!visited[connectIdx]) {		//만약 연결된 원소를 방문하지 않았다면
				que.push(connectIdx);		//방문할 노드로 선정
				visited[connectIdx] = true;
			}
		}
	}
	
	
}

int main() {

	int N, M, V;		//정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호

	cin >> N >> M >> V;

	int size = N + 1;
	//N개만큼의 배열 만들기
	bool* visited = new bool[size] {false, };			//방문 유무를 저장하는 배열
	vector<int>* graph = new vector<int>[size];
	graph->push_back(1);

	for (int i = 0; i < M; i++) {
		int origin, connect;
		cin >> origin >> connect;
		graph[origin].push_back(connect);
		graph[connect].push_back(origin);
	}

	//정렬
	for (int i = 0; i < size; i++) {
		sort(graph[i].begin(),graph[i].end());
	}

	dfs(graph,visited, V);
	cout << endl;
	visited = new bool[size]{ false, };		//방문유무를 다시 초기화해줌(재사용 위해)
	bfs(graph, visited,V);

	delete [] visited;		//메모리 해제 
	//vector 메모리 해제
	graph->clear();
	vector<int>().swap(*graph);

	return 0;
}

*간단한 해설*

DFS와 BFS를 구현하였다. DFS는 모든 노드를 탐색하도록 작성하였고, BFS는 연결된 노드를 통해서 해당 노드와 연결된 노드 중 방문하지 않은 노드만 다시 탐색해서 탐색이 끝나면 종료되도록 작성하였다. DFS와 BFS의 경우 

https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

해당 포스팅을 통해 자세하게 배울 수 있었다. DFS와 BFS에 대해 알고싶으면 위의 블로그를 참조하면 좋을듯하다.

for (int i = 0; i < M; i++) {
    int origin, connect;
    cin >> origin >> connect;
    graph[origin].push_back(connect);
    graph[connect].push_back(origin);
}

연결된 노드들을 입력받는 과정에서 연결된 2개를 입력 받을시 서로 각자의 노드에 연결 정보를 입력시키도록 한다.

//정렬
for (int i = 0; i < size; i++) {
    sort(graph[i].begin(),graph[i].end());
}

입력시킨 정보들을 sort를 통해 정렬을 시켜준다. 정렬을 하지 않으면 원하는대로 결과값이 나오지 않기 때문에 정렬을 꼭 해준다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

출력

1
2
2
0
1
2
-1
0
1
-1
0
3

코드

#include<iostream>
#include<string>
using namespace std;

// 10845번 큐

//큐 구현
class QueueS {
public:
	int front;
	int back;
	int size;
	int *values;		//모든 값들을 담은 배열을 가리키는 포인터

	//생성자
	QueueS() {
		size = 10001;		//큐의 사이즈 
		values = new int[size];
		front = 0;
		back=0;
	}
	//소멸자
	~QueueS() {
		delete[] values;
	}

	void push(int data) {
		if ((back+1)%size!=front) {
			values[back] = data;
			back = (back + 1) % size;
		}
	}

	void pop() {
		front = (front + 1) % size;
	}

	bool empty() {
		if (back == front)
			return true;
		else
			return false;
	}
};

QueueS st;

void getNumSize(string str) {
	int temp;

	if (str == "back") {
		if (st.back - st.front != 0) {
			cout << st.values[st.back - 1] << "\n";
		}
		else cout << "-1\n";
	}
	else if (str == "front") {
		if (st.back - st.front != 0) {
			cout << st.values[st.front] << "\n";
		}
		else cout << "-1\n";
	}
	else if (str == "size") {
		cout << st.back-st.front << "\n";
	}
	else if (str == "empty") {
		cout << ((st.back - st.front==0)?true:false) << "\n";
	}
	else if (str == "pop") {
		if (st.back - st.front!=0) {
			cout << st.values[st.front] << "\n";
			st.pop();
		}
		else {
			cout << "-1\n";
		}
	}
	else if (str == "push")
	{
		cin >> temp;
		st.push(temp);
	}
}

int main() {

	int n;
	string str;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str;
		getNumSize(str);
	}

	return 0;
}

*간단한 해설*

큐를 클래스를 이용하여 구현하였다. 큐 클래스의 front,back은 일종의 맨 앞의 index 번호를 말하는 것이고, back은 맨 뒤의 index번호를 말하는 것이다. 그리고 int* values를 통해서 입력 받은 값들을 back을 늘려가면서 저장하였다.

C 구조체와 C++의 queue 라이브러리를 이용하여 구현하신 분도 있었다.

https://blockdmask.tistory.com/119

내 코드는 헤더를 추가하지 않는데 시간이 너무 길어서.. 블로그 글을 참고하다 보니 아무래도 cout문제도 있을 것 같아서 printf로 한번 다 바꿔보았다.

그렇게까지 영향을 준건 아닌가보다 싶어서 좀 더 찾아보니

https://coding-insider.tistory.com/entry/cin-cout-%EC%9E%85%EC%B6%9C%EB%A0%A5-%EC%86%8D%EB%8F%84-%EB%B9%A0%EB%A5%B4%EA%B2%8C%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95

cin의 속도가 생각보다 엄청 느리다는것! 

ios_base :: sync_with_stdio(false); 
cin.tie(NULL); 
cout.tie(NULL);

이 코드를 추가해주면 빨라진다고는 하나 scanf,printf와 같이 사용하면 안되고 싱글쓰레드 영역에서만 사용 가능해서 실제 코드 영역에서는 사용하는 것을 지양하라고 한다.

일단 싱글 쓰레드 영역이니 쟤들을 추가해서 한번 돌려보았다.

속도는 빨라졌지만 메모리는 늘어났다.. 그러면 scanf,printf로 다 바꿔보겠다.

결과적으로는 메모리도 줄어들었다. 아무래도 scanf,printf로 출력하는 방식으로 앞으로도 써야겠다.

코드(scanf,printf)

#include<iostream>
#include<string.h>
using namespace std;

// 10845번 큐
//큐 구현
class QueueS {
public:
	int front;
	int back;
	int size;
	int *values;		//모든 값들을 담은 배열을 가리키는 포인터

	//생성자
	QueueS() {
		size = 10001;		//큐의 사이즈 
		values = new int[size];
		front = 0;
		back = 0;
	}
	//소멸자
	~QueueS() {
		delete[] values;
	}

	void push(int data) {
		if ((back + 1) % size != front) {
			values[back] = data;
			back = (back + 1) % size;
		}
	}

	void pop() {
		front = (front + 1) % size;
	}

	bool empty() {
		if (back == front)
			return true;
		else
			return false;
	}
};

QueueS st;

void getNumSize(char str[]) {
	int temp;

	if (!strcmp(str, "back")) {
		if (st.back - st.front != 0) {
			printf("%d\n", st.values[st.back - 1]);
		}
		else printf("-1\n");
	}
	else if (!strcmp(str,"front")) {
		if (st.back - st.front != 0) {
			printf("%d\n", st.values[st.front]);
		}
		else printf("-1\n");
	}
	else if (!strcmp(str ,"size")) {
		printf("%d\n", st.back - st.front);
	}
	else if (!strcmp(str,"empty")) {
		printf("%d\n", ((st.back - st.front == 0) ? true : false));
	}
	else if (!strcmp(str, "pop")) {
		if (st.back - st.front != 0) {
			printf("%d\n", st.values[st.front]);
			st.pop();
		}
		else {
			printf("-1\n");
		}
	}
	else if (!strcmp(str,"push"))
	{
		scanf("%d", &temp);
		st.push(temp);
	}
}

int main() {

	int n;
	char str[6];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", str);
		getNumSize(str);
	}

	return 0;
}

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*