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은 말그대로 얼만큼 잃어버린 학생들의 공백을 메꿀수 있는지 나타내는 변수이다.

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