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인경우는 소수가 아니기 떄문에 제외합니다.