[코드트리 조별과제] 2주차

MNA·2024년 7월 22일

코드트리 조별과제

목록 보기

2/5

코드트리를 하는 김에 푸는 문제 중 재밌게 풀었거나 헷갈린 문제는 정리하고자 한다.

007

유형	문제 경험치	난이도
Novice Mid / 정렬 / 객체	10xp

작성 코드

#include <iostream>
#include <string>
#include <tuple>

using namespace std;

// class Spy{
//     public:
//         string s;
//         char c;
//         int n;

//     Spy(string s, char c, int n) : s(s), c(c), n(n) {};
// };

// int main() {
//     string s;
//     char c;
//     int n;
//     cin >> s >> c >> n;

//     Spy spy(s, c, n);
//     cout << "secret code : " << spy.s << endl;
//     cout << "meeting point : " << spy.c << endl;
//     cout << "time : " << spy.n << endl;

//     return 0;
// }

int main(void){
    string s;
    char c;
    int t;

    cin >> s >> c >> t;
    tuple<string, char, int> tup = make_tuple(s, c, t);
    cout << "secret code : " << get<0>(tup) << endl;
    cout << "meeting point : " << get<1>(tup) << endl;
    cout << "time : " << get<2>(tup) << endl;

    return 0;
}

해설 코드 1 :Class

#include <iostream>
#include <string>

using namespace std;

// Spy 정보를 나타내는 클래스 선언
class Spy {
    public:
        string secret_code;
        char meeting_point;
        int time;
        Spy(string secret_code, char meeting_point, int time) {
            this->secret_code = secret_code;
            this->meeting_point = meeting_point;
            this->time = time;
        }
};

int main(){
    // 변수 선언 및 입력
    string s_code;
    char m_point;
    int time;
    cin >> s_code >> m_point >> time;
    
    // Spy 객체를 만들어 줍니다.
    Spy s = Spy(s_code, m_point, time);

    // 결과를 출력합니다.
    cout << "secret code : " << s.secret_code << endl;
    cout << "meeting point : " << s.meeting_point << endl;
    cout << "time : " << s.time << endl;
    return 0;
}

해설 코드 2 :Tuple

#include <iostream>
#include <string>
#include <tuple>

using namespace std;

// Spy 정보를 나타내는 tuple 선언
tuple<string, char, int> spy;

int main(){
    // 변수 선언 및 입력
    string s_code;
    char m_point;
    int given_time;
    cin >> s_code >> m_point >> given_time;
    
    // tuple type의 데이터를 하나 만들어 줍니다.
    spy = make_tuple(s_code, m_point, given_time);

    // tuple 값들을 변수에 대입
    string secret_code;
    char meeting_point;
    int time;
    tie(secret_code, meeting_point, time) = spy;
    
    // 결과를 출력합니다.
    cout << "secret code : " << secret_code << endl;
    cout << "meeting point : " << meeting_point << endl;
    cout << "time : " << time << endl;
    return 0;
}

첨언

문제 자체는 매우 쉬운 문제이다. / 정리한 이유 -> tuple, pair 개념을 처음 접했다.
1. <tuple>을 include해서 사용, 아래와 같이 정의, 생성할 수 있다.
  tuple<type, type, type> t = make_tuple(v1, v2, v3);
2. get<index>t; 이와 같이 값에 인덱스로 접근 할 수 있다.
3. tie(v4, v5, v6) = t; tie 함수를 사용해 내부 값을 한번에 전달할 수 있다.
1. <utility>을 include해서 사용, 아래와 같이 정의, 생성할 수 있다.
  pair형은 값이 무조건 쌍을 이룬다. - 2개
  pair<type, type> p = make_pair(v1, v2);
2. p.first; p.second; 이와 같이 값에 접근 할 수 있다.

비오는 날

유형	문제 경험치	난이도
Novice Mid / 정렬 / 객체	30xp

작성 코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Rain{
public:
    string y, m, d;
    string days;
    Rain(){};
    Rain(string y, string m, string d, string days) : y(y), m(m), d(d), days(days) {};
};

bool comp(const Rain& r1, const Rain& r2){ // 날짜가 빠른 순대로 정렬되도록 함
    if (r1.y.compare(r2.y) < 0) return true;
    else if (r1.y.compare(r2.y) == 0 && r1.m.compare(r2.m) < 0) return true;
    else if (r1.y.compare(r2.y) == 0 && r1.m.compare(r2.m) == 0 && r1.d.compare(r2.d) < 0) return true;
    return false;
}

int main() {
    int n;
    Rain r[100];
    
    cin >> n;
    for (int i = 0; i < n; i++){
        string s1, s2, s3;
        string year, month, day;
        cin >> s1 >> s2 >> s3;
        if (s3.compare("Rain")) { // Rain 중에서 가장 빠른 날을 판단하는 문제니
            i--;                  // Rain이 아니라면 넣어주지 않아도 문제 푸는데는 지장없음.
            n--;
            continue;
        }

        year = s1.substr(0, 4);   // 날짜 포맷이 yyyy-mm-dd로 고정되어있으니 가능
        month = s1.substr(5, 2);
        day = s1.substr(8, 2);

        r[i] = Rain(year, month, day, s2);
    }
    sort(r, r + n, comp);
    cout << r[0].y << "-" << r[0].m << "-" << r[0].d << " " << r[0].days << " Rain";

    return 0;
}

해설 코드

#include <iostream>
#include <string>

using namespace std;

// Forecast 정보를 나타내는 클래스 선언
class Forecast {
    public:
        string date, day, weather;
        Forecast(string date, string day, string weather) {
            this->date = date;
            this->day = day;
            this->weather = weather;
        }
};

Forecast ans = Forecast("9999-99-99", "", "");

int main(){
    // 변수 선언 및 입력
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) {
        string date, day, weather;
        cin >> date >> day >> weather;

        // Forecast 객체를 만들어 줍니다.
        Forecast f = Forecast(date, day, weather);
        if(weather == "Rain")
            // 비가 오는 경우 가장 최근인지 확인하고,
            // 가장 최근일 경우 정답을 업데이트합니다.
            if(ans.date >= f.date)
                ans = f;
    }

    // 결과를 출력합니다.
    cout << ans.date << " " << ans.day << " " << ans.weather;
    return 0;
}

첨언

굳이 날짜를 나눠서 비교해줄 필요없이 date 통째로 비교해도 된다는 생각에 미치지못했지만 덕분에 sort에서 비교함수를 쓰는 방법을 알았으니 럭키비키다.
1. sort(start, end, compare) 시작, 끝, 비교 함수를 인자로 가진다.
2. 정렬 함수의 반환형은 bool 이며, 기왕이면 const type&로 인자를 받는다.
3. a가 b보다 먼저 정렬되었으면하는 조건을 true 로 한다.
  a > b 일 경우, 오름차순 / a < b 일 경우, 내림차순이다.
```
 
```

개인정보

유형	문제 경험치	난이도
Novice Mid / 정렬 / 객체 정렬	20xp

작성 코드

#include <iostream>
#include <tuple>
#include <string>
#include <algorithm>

using namespace std;

bool compare(const tuple<string, int, double>& t1, const tuple<string, int, double>& t2){
    return get<1>(t1) > get<1>(t2);
}

int main() {
    tuple<string, int, double> t[5];
    string name;
    int height;
    double weight;

    for (int i = 0; i < 5; i++){
        cin >> name >> height >> weight;
        t[i] = make_tuple(name, height, weight);
    }
    sort(t, t+5); // 이름 순 정렬
    cout << "name" << endl;

    for (int i = 0; i < 5; i++){
        tie(name, height, weight) = t[i];
        cout << name << " " << height << " ";
        printf("%.1lf\n", weight);
    }
    sort(t, t+5, compare); // 키 순 정렬
    cout << endl;
    cout << "height" << endl;
    for (int i = 0; i < 5; i++){
        tie(name, height, weight) = t[i];
        cout << name << " " << height << " ";
        printf("%.1lf\n", weight);
    }

    return 0;
}

해설 코드

#include <iostream>
#include <algorithm>
#include <string>

#define MAXN 5

using namespace std;

// 학생들의 정보를 나타내는 클래스 선언
class Student{
    public:
        string name;
        int height;
        double weight;
        Student(string name, int height, double weight) {
            this->name = name;
            this->height = height;
            this->weight = weight;
        }
		Student(){}
};

// Custom Comparator
bool Cmp1(Student a, Student b) {
    // 이름을 기준으로 오름차순으로 정렬합니다.
    return a.name < b.name;
}

bool Cmp2(Student a, Student b) {
    // 키를 기준으로 내림차순으로 정렬합니다.
    return a.height > b.height;
}

Student students[MAXN];

int main(){
    for (int i = 0; i < MAXN; i++){
        string name;
        int height;
		double weight;
        cin >> name >> height >> weight;
        // Student 객체를 생성해 리스트에 추가합니다.
		students[i] = Student(name, height, weight);
    }
	
	cout << fixed;
	cout.precision(1);

    // custom comparator를 활용한 정렬 (이름순으로 정렬)
    sort(students, students + MAXN, Cmp1);

    // 이름순으로 정렬한 결과를 출력합니다.
	cout << "name" << endl;
    for (int i = 0; i < MAXN; i++){
        cout << students[i].name << " ";
        cout << students[i].height << " ";
        cout << students[i].weight << endl;
    }
	
	cout << endl;
	
	// custom comparator를 활용한 정렬 (키순으로 정렬)
    sort(students, students + MAXN, Cmp2);

    // 키순으로 정렬한 결과를 출력합니다.
	cout << "height" << endl;
    for (int i = 0; i < MAXN; i++){
        cout << students[i].name << " ";
        cout << students[i].height << " ";
        cout << students[i].weight << endl;
    }

    return 0;
}

첨언

복잡하지 않은 대부분의 경우(간단한 문제) tuple을 이용하는 것이 쉽다고 느껴진다.
90.0과 같은 값이 실수형 변수에 저장될 경우, 90으로 저장한다. -> 고려 안해 한번 틀림
printf("%.nlf", value); 로 푸는 것도 문제는 없어보이지만..
cout << fixed; cout.precision(n); 을 이용하는 것이 좋아보인다.

cout.precision(n); n자리수까지만 출력한다.
cout << fixed; precision(n)에서 지정하는 n이 소수점 아래 자리수가 된다.

// cout.precision(n), cout << fixed 예문
#include <iostream>

using namespace std;

int main(void){
  cout << fixed;
  cout.precision(1);
  
  int ai(1), bi(2), ci(3);
  float af(1), bf(2), cf(3);
  double ad(1.06), bd(2.06), cd(3.06);
  
  cout << ai << " " << bi << " " << ci << endl; // 정수형은 소수점 아래 자리수 1까지 출력으로 설정해도 소수점은 출력 X
  cout << af << " " << bf << " " << cf << endl; // 실수형은 소수점 아래 자리수 1까지 출력을 확인할 수 있다.  
  cout << ad << " " << bd << " " << cd << endl; // 소수점 아래 자리수 1까지 출력의 경우, 
                                                // 알아서 소수점 아래 자리수 2에서 반올림을 적용해준다.                             
  ad = 1.05; bd = 2.05; cd = 3.05;
  cout << ad << " " << bd << " " << cd << endl; // 부동 소수점 오류에 의해 반올림이 되기도 안되기도 하는걸 확인할 수 있다.
  
  /* 출력 결과
  1 2 3
  1.0 2.0 3.0
  1.1 2.1 3.1
  1.1 2.0 3.0
  */
  
  return 0;
}

원점으로부터의 거리

유형	문제 경험치	난이도
Novice Mid / 정렬 / 객체 정렬	30xp

작성 코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <tuple>

using namespace std;

int main() {
    int n, num(1), x, y, dis;
    tuple<int, int>* t;
    
    cin >> n;
    t = new tuple<int, int>[n];

    for (int i = 0; i < n; i++){
        cin >> x >> y;
        dis = abs(x - 0) + abs(y - 0);

        t[i] = make_tuple(dis, num++);
    }
    sort(t, t+n); // tuple은 인자값을 순차적으로 따져서 오름차순으로 만들어준다. 
                  // 만약 v1이 같은 값일 경우 v2를 따지고 v2도 같을 경우 v3를 따지고 ..
    for (int i = 0; i < n; i++){
        tie(ignore, num) = t[i];
        cout << num << endl;
    }

    delete[] t;
    return 0;
}

해설 코드

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>

#define MAXN 1000

using namespace std;

// 원점과의 거리를 계산하는 함수입니다.
int GetDistFromOrigin(int x, int y) {
    return abs(x) + abs(y);
}

pair<int, int> distances[MAXN];

int main(){
    int n;
    cin >> n;
	
    int x, y;
    for(int i = 0; i < n; i++) {
        cin >> x >> y;
        // 원점과의 거리와 index를 저장합니다.
       distances[i] = make_pair(GetDistFromOrigin(x, y), i + 1);
    }

    sort(distances, distances + n);

    for(int i = 0; i < n; i++)
        cout << distances[i].second << endl;

    return 0;
}

첨언

저장할 값이 2개밖에 없는 경우에는 pair<type, type>을 이용해보자
물론 푸는데 상관은 없지만 알맞게 쓰면 기분이 좋다.
pair, tuple의 경우에는 객체 정렬시 앞에 있는 인자부터 순차적으로 따져 오름차순으로 정렬해준다.
인자값 1을 기준으로 오름차순 -> 만약 인자값 1이 같다면 인자값 2 기준으로 -> 만약 인자값 2도 같다면 인자값 3 기준으로 -> ...

정렬된 숫자 위치 알아내기

유형	문제 경험치	난이도
Novice Mid / 정렬 / 객체 정렬	50xp

작성 코드

#include <iostream>
#include <algorithm>

using namespace std;

class Array{
public:
    int key;
    int num;

    Array(){};
    Array(int key, int num) : key(key), num(num) {};
};

bool compare(const Array& arr1, const Array& arr2){
    if (arr1.num == arr2.num) return arr1.key < arr2.key; // 값이 같은 경우
    return arr1.num < arr2.num;                           // 먼저 입력된 순으로 정렬
}

int main() {
    int n, key(0), num;
    Array* array;

    cin >> n;
    array = new Array[n];

    for (int i = 0; i < n; i++){
        cin >> num;
        array[i] = Array(key++, num);
    }
    sort(array, array + n, compare);

    for (int i = 0; i < n; i++){ // key가 i인 Array 객체의 위치 + 1을 출력하면 된다. 
        for (int j = 0; j < n; j++){
            if (array[j].key == i) { // key가 i와 같다면, 
                cout << j + 1 << " "; // 현재 위치 + 1 출력 
                break;
            }
        }
    }

    delete[] array;
    return 0;
}

해설 코드 :Class

#include <iostream>
#include <algorithm>

#define MAX_NUM 1000

using namespace std;

// 클래스 선언: 
class Number{
    public:
        int number;
        int index;
        Number(int number, int index) {
            this->number = number;
            this->index = index;
        }
		Number(){}
};

// Custom Comparator
bool Cmp(Number a, Number b) {
    if(a.number != b.number)
        return a.number < b.number;
    return a.index < b.index;
}

Number numbers[MAX_NUM];

int main() {
    // 변수 선언:
    int n, num_cache;
    int answer[MAX_NUM];

    // 입력:
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> num_cache;
        numbers[i] = Number(num_cache, i);
    }

    // Custom Comparator를 활용한 정렬:
    sort(numbers, numbers + n, Cmp);

    // 정렬된 숫자들의 원래 인덱스를 활용한 정답 배열 저장:
    for(int i = 0; i < n; i++) 
        answer[numbers[i].index] = i + 1; // 인덱스 보정

    // 출력:
    for(int i = 0; i < n; i++){
        cout << answer[i] << " ";
    }

    return 0;
}

해설 코드 :Pair

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_NUM 1000

using namespace std;

int main() {
    // 변수 선언:
    int n, num_cache;
    int answer[MAX_NUM];
    vector<pair<int, int> > numbers;

    // 입력:
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> num_cache;
        numbers.push_back(make_pair(num_cache, i));
    }

    // 정렬:
    sort(numbers.begin(), numbers.end());

    // 정렬된 숫자들의 원래 인덱스를 활용한 정답 배열 저장:
    for(int i = 0; i < n; i++) 
        answer[numbers[i].second] = i + 1; // 인덱스 보정

    // 출력:
    for(int i = 0; i < n; i++){
        cout << answer[i] << " ";
    }

    return 0;
}

첨언

이중 for문을 만들지 않고 아래와 같이 int형 배열을 하나 만들어서 쉽게 해결할 수 있었다.
array[i].key는 입력받은 순서이고, array는 지금 정렬되었으니 간단히 원래 순서대로 정렬 후 변경 된 위치를 출력할 수 있다.


    for (int i = 0; i < n; i++){
        solve[array[i].key] = i + 1;
    }
    for (int i = 0; i < n; i++){
        cout << solve[i] << " ";
    }

구현됐으니, 원하는 답이 나왔으니 끝! 이 아니라 좀 더 나은 알고리즘이 있는지 생각해보는게 좋을 것 같다.

요일 맞추기

유형	문제 경험치	난이도
Novice Mid / 시뮬레이션 I / 날짜와 시간 계산	50xp

작성 코드

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

int Func(int m1, int m2, int d1, int d2, bool reverse){
    int elapse_day(0);
    int month_day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    // m1 d1 ~ m2 d2일때 elapse_day는 아래와 같이 구할 수 있다. 
    // 1. d1을 뺀다.
    // 2. m1 ~ m2-1 까지 해당 월의 일수를 다 더한다.
    // 3. d2를 더한다. 
    elapse_day = d2 - d1;
    for (int i = m1; i < m2; i++){
        elapse_day += month_day[i-1];
    }

    if (reverse) return 7 - (elapse_day % 7); // 입력받은 순과 순서가 달라졌다면 거꾸로 찾아야하니 
    return elapse_day % 7;
}

int GuessDay(int m1, int m2, int d1, int d2){ 
    pair<int, int> day1 = make_pair(m1, d1);
    pair<int, int> day2 = make_pair(m2, d2);
    if (day1 > day2) return Func(m2, m1, d2, d1, true); // pair의 크기 비교는 알아서 인수를 차례대로 따져준다는 것을 이용
    else return Func(m1, m2, d1, d2, false);            // 무조건 elapse_day >= 0이 되도록
}

int main() {
    int m1, m2, d1, d2;
    string day_of_week[7] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};
    cin >> m1 >> d1 >> m2 >> d2;
    cout << day_of_week[GuessDay(m1, m2, d1, d2)];
    return 0;
}

해설 코드

#include <iostream>
#include <string>

using namespace std;

int NumOfDays(int m, int d) {
    // 계산 편의를 위해 월마다 몇 일이 있는지를 적어줍니다. 
    int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int total_days = 0;
    
    // 1월부터 (m - 1)월 까지는 전부 꽉 채워져 있습니다.
    for(int i = 1; i < m; i++)
        total_days += days[i];
    
    // m월의 경우에는 정확이 d일만 있습니다.
    total_days += d;
    
    return total_days;
}

int main() {
    // 변수 선언 및 입력
    int m1, m2, d1, d2;
    cin >> m1 >> d1 >> m2 >> d2;
    
    // 두 날짜간의 차이가 몇 일인지를 구합니다.
    int diff = NumOfDays(m2, d2) - NumOfDays(m1, d1);
    
    // 음수인 경우에는, 양수로 넘겨 계산해주면 올바르게 계산이 됩니다. 
    while(diff < 0)
        diff += 7;
    
    // 알맞은 요일의 이름을 출력합니다.
    string day_of_week[] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};
    cout << day_of_week[diff % 7];
    return 0;
}

첨언

A부터 B까지 총 시간, 총 일수 등등을 구하는 식이 내 안에서 정립된 기분이다.
(작성 코드의 elapse_day 구하는 식)
tuple, pair의 인수별 오름차순 비교는 너무 좋은 기능같다.

그 요일은

유형	문제 경험치	난이도
Novice Mid / 시뮬레이션 I / 날짜와 시간 계산	50xp

작성 코드

#include <iostream>
#include <string>

using namespace std;

int Func(int m1, int d1, int m2, int d2, int d_w_n){
    int elapse_day(0);
    int day_times(0);
    int month_day[12] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    elapse_day = d2 - d1;
    for (int i = m1; i < m2; i++) elapse_day += month_day[i-1];
    day_times = elapse_day / 7; // 어떤 요일인지 상관없이 적어도 몫만큼은 등장했다.  
    if (elapse_day % 7 < d_w_n) return day_times;  
    else return day_times + 1; // 주어진 요일(월요일 = 0, 화요일 = 1...)보다 나머지가 크거나 같다면 +1 
}


int main() {
    int m1, d1, m2, d2, day_week_num;
    string day_week;
    string day_weeks[7] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};
    cin >> m1 >> d1 >> m2 >> d2 >> day_week;
    for (int i = 0; i < 7; i++){
        if (!day_weeks[i].compare(day_week)){
            day_week_num = i; // 사용하기 편하게 숫자로 치환 
            break;
        }
    }
    cout << Func(m1, d1, m2, d2, day_week_num);

    return 0;
}

해설 코드

#include <iostream>

using namespace std;

int NumOfDays(int m, int d) {
    // 계산 편의를 위해 월마다 몇 일이 있는지를 적어줍니다. 
    int days[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int total_days = 0;
    
    // 1월부터 (m - 1)월 까지는 전부 꽉 채워져 있습니다.
    for(int i = 1; i < m; i++)
        total_days += days[i];
    
    // m월의 경우에는 정확이 d일만 있습니다.
    total_days += d;
    
    return total_days;
}

int NumOfDay(string s) {
    // 간단한 비교를 위해 요일을 숫자로 나타내줍니다.
    if(s == "Mon") return 0;
    else if(s == "Tue") return 1;
    else if(s == "Wed") return 2;
    else if(s == "Thu") return 3;
    else if(s == "Fri") return 4;
    else if(s == "Sat") return 5;
    return 6;
}

int ans;

int main() {
    // 변수 선언 및 입력
    int m1, m2, d1, d2;
    string A;
    cin >> m1 >> d1 >> m2 >> d2;
    cin >> A;

    int start_date = NumOfDays(m1, d1);
    int end_date = NumOfDays(m2, d2);
    int cur_day = NumOfDay("Mon");

    for(int date = start_date; date <= end_date; date++) {
        // 오늘의 요일이 A요일과 같다면 정답에 추가합니다.
        if(cur_day == NumOfDay(A)) ans++;
        cur_day = (cur_day + 1) % 7;
    }
    
    // 출력
    cout << ans;
    return 0;
}

첨언

해설보다 맘에 드는 방식의 풀이를 한 것같아 기분이 좋음 (개인적 의견)

십진수와 이진수 2

유형	문제 경험치	난이도
Novice Mid / 시뮬레이션 I / Notation	10xp

작성코드

#include <iostream>
#include <string>

using namespace std;

int BinToDec(string s){
    int num(0);
    for (int i = 0; i < s.length(); i++) num = num * 2 + (s[i] -'0');
    return num;
}

void DecToBin(int d1, string& result){
    int cnt(0), max_size(0);
    int d;
    
    for (d = d1; d >= 2; d/=2){
        max_size++;
    }
    result.resize(max_size); // result를 max_size로 만듬 
    for (d = d1; d >= 2; d/=2){
        result[cnt++] = d % 2 + '0';
    }
    
    result[cnt] = d + '0';
}

int main() {
    string bin, result;
    int dec;
    cin >> bin;

    dec = BinToDec(bin);
    dec *= 17;
    DecToBin(dec, result);

    for (int i = result.length(); i>=0; i--) cout << result[i];
    return 0;
}

해설코드

#include <iostream>
#include <algorithm>

#define MAX_DIGIT 20

using namespace std;

int main() {
    // 변수 선언 및 입력
    string binary;
    cin >> binary;
    
    // 십진수로 변환합니다.
    int num = 0;
    for(int i = 0; i < (int) binary.size(); i++)
        num = num * 2 + (binary[i] - '0');
    
	// 십진수에 17을 곱합니다.
	num *= 17;
	
	// 이진수로 변환합니다.
	int digits[MAX_DIGIT] = {};
	int cnt = 0;
	
	while(true) {
        if(num < 2) {
            digits[cnt++] = num;
            break;
        }
        
        digits[cnt++] = num % 2;
        num /= 2;
    }
    
    // 배열의 순서를 뒤집어 이진수를 출력합니다.
    for(int i = cnt - 1; i >= 0; i--)
        cout << digits[i];

    return 0;
}

첨언

이진수 1101이 주어졌을 때 이를 십진수로 바꾸는 방법은 아래와 같다.
for (int i = 0; i < 자리수; i++) num = num * 2 + bin[i]
이진수는 한자리가 늘어날때마다 2배가 되는 것을 이용(가중치)
십진수를 이진수로 바꾸는 법은 bin[cnt++] = dec % 2; dec /= 2;
이후 bin를 거꾸로 출력해주면 된다.
(코드에서는 bin[cnt] = dec를 해줬는데, 이유는 for 루프에서는 나머지를 못 넣었기때문)
어려운 문제는 아니었다, 구하는 방식도 다 알려줬고... 그런데 정리한 이유는 아래 코드 때문이다.
result.resize(max_size); -> result를 max_size로 만든다. (빈공간)
당연한 얘기지만 공간할당을 하지 않으면 cout << string을 할 수 없다.
특이한 점은 공간할당을 해주지 않아도 인덱스로 접근하여 출력은 할 수 있다. -> 주소접근이기에

최대로 겹치는 구간

유형	문제 경험치	난이도
Novice Mid / 시뮬레이션 I / 구간 칠하기	30xp

작성 코드

#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

int main() {
    int n, x1, x2, offset(100);
    int result[201] = {0,};

    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> x1 >> x2;
        x1 += offset; 
        x2 += offset;
        for (int k = x1; k < x2; k++) {
            result[k]++;
        }
    }
    sort(result, result + 201, greater<int>());
    cout << result[0];
    return 0;
}

해설 코드

#include <iostream>

#define MAX_N 100
#define MAX_R 200
#define OFFSET 100

using namespace std;

int n;
int x1[MAX_N], x2[MAX_N];

int checked[MAX_R + 1];

int main() {
    // 입력
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> x1[i] >> x2[i];
        
        // OFFSET을 더해줍니다.
        x1[i] += OFFSET;
        x2[i] += OFFSET;
    }
    
    // 구간을 칠해줍니다.
    // 구간 단위로 진행하는 문제이므로
    // x2[i]에 등호가 들어가지 않음에 유의합니다.
    for(int i = 0; i < n; i++)
        for(int j = x1[i]; j < x2[i]; j++)
            checked[j]++;
    
    // 최댓값을 구합니다.
    int max = 0;
    for(int i = 0; i <= MAX_R; i++)
        if(checked[i] > max)
            max = checked[i];
    
    cout << max;
    return 0;
}

첨언

겹치는 지점은 1차원 배열에 x1부터 x2까지 칠해주고
겹치는 구간은 1차원 배열에 x1부터 x2-1까지 칠해준다.
구간의 경우 x1, x1 + 1.. 과 같은 인덱스가 구간의 시작점으로 생각하는 것이다.
음수의 구간의 경우 오프셋을 정해서 양수 인덱스를 이용할 수 있도록 한다.

왔다 갔던 구역 2

유형	문제 경험치	난이도
Novice Mid / 시뮬레이션 I / 구간 칠하기	40xp

작성 코드

//OFFSET 이용이 아니라 plus 배열 따로 minus 배열 따로 구현해보고자 함
#include <iostream>
using namespace std;

class Area{
public:
    int plus[1001] = {0,};
    int minus[1001] = {0, };
    int cur_pos = 0;
    int cnt = 0;
    Area(){};

    void plusDir(int x){
        int tmp = cur_pos + x;
        for (cur_pos; cur_pos < tmp; cur_pos++){
            if (cur_pos >= 0) { // cur_pos == 0일때는 plus 배열에서 정함
                plus[cur_pos]++;
            }
            else if (cur_pos < 0) {
                minus[abs(cur_pos)]++;
            }
        }
    }
    void minusDir(int x){
        int tmp = cur_pos - x;
        for (cur_pos; cur_pos > tmp; cur_pos--){
            if (cur_pos > 0) {
                plus[cur_pos - 1]++; // 구간을 보는 문제이므로 거꾸로 갈 경우 -1을 해줘야한다.
            }
            else if (cur_pos < 0) {
                minus[abs(cur_pos - 1)]++;
            }
            else {
                minus[1]++; // cur_pos == 0일 경우에는 plus 배열에서 처리하도록 정함
            }
        }
    }
    void PrintAreaNumOver2(){
        for (int i = 0; i < 1001; i++) {
            if (plus[i] > 1) cnt++; // 2번 이상 지나간 구간 수 세기
        }
        for (int i = 1; i < 1001; i++) {
            if (minus[i] > 1) cnt++;
        }
        cout << cnt;
    }
};

int main() {
    int n, x;
    char dir;
    Area area;

    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> x >> dir;
        if (dir == 'R'){
            area.plusDir(x);
        }
        else {
            area.minusDir(x);
        }
    }
    area.PrintAreaNumOver2();
    
    return 0;
}

해설 코드

#include <iostream>

#define MAX_N 100
#define MAX_R 2000
#define OFFSET 1000

using namespace std;

int n;
int x1[MAX_N], x2[MAX_N];

int checked[MAX_R + 1];

int main() {
    // 입력
    cin >> n;
    
	// 현재 위치
	int cur = 0;
	
    for(int i = 0; i < n; i++) {
		int distance;
		char direction;
        cin >> distance >> direction;
		
		if(direction == 'L') {
			// 왼쪽으로 이동할 경우 : cur - distance ~ cur까지 경로 이동
			x1[i] = cur - distance;
			x2[i] = cur;
			cur -= distance;
		}
		else {
			// 오른쪽으로 이동할 경우 : cur ~ cur + distance까지 경로 이동
			x1[i] = cur;
			x2[i] = cur + distance;
			cur += distance;
		}
        
        // OFFSET을 더해줍니다.
        x1[i] += OFFSET;
        x2[i] += OFFSET;
    }
    
    // 구간을 칠해줍니다.
    // 구간 단위로 진행하는 문제이므로
    // x2[i]에 등호가 들어가지 않음에 유의합니다.
    for(int i = 0; i < n; i++)
        for(int j = x1[i]; j < x2[i]; j++)
            checked[j]++;
    
    // 2번 이상 지나간 영역의 크기를 구합니다.
    int cnt = 0;
    for(int i = 0; i <= MAX_R; i++)
        if(checked[i] >= 2)
            cnt++;
    
    cout << cnt;
    return 0;
}

흰검 칠하기

유형	문제 경험치	난이도
Novice Mid / 시뮬레이션 I / 구간 칠하기	70xp

작성 코드

#include <iostream>

#define BLACK 1
#define WHITE 2
#define OFFSET 100000

using namespace std;

class Tile{ // black과 white로 몇번 바뀌었고, 가장 최근에 바뀐 색이 뭔지 저장하는 클래스
public:
    int black_count;
    int white_count;
    int last; // 가장 최근에 바뀐 색
    Tile() : black_count(0), white_count(0), last(0) {};
};

void BlackDir(Tile* area, int x, int& cur_pos){
    for (int i = 0; i < x; i++){ // 구간이니 x-1까지 
        if (!(area[cur_pos].black_count >= 2 && area[cur_pos].white_count >= 2)) { // grey가 아닌 경우 
            area[cur_pos].black_count++;
            area[cur_pos].last = BLACK;
        }
        cur_pos++;
    }
    cur_pos--; // 구간이니 x-1까지 되어야하므로
}

void WhiteDir(Tile* area, int x, int& cur_pos){
    for (int i = 0; i < x; i++){
        if (!(area[cur_pos].black_count >= 2 && area[cur_pos].white_count >= 2)) {
            area[cur_pos].white_count++;
            area[cur_pos].last = WHITE;
        }
        cur_pos--;
    }
    cur_pos++;
}

void PrintNumberOfColor(Tile* area){
    int black(0), white(0), grey(0);
    for (int i = 0; i < 200001; i++){
        if (area[i].black_count >= 2 && area[i].white_count >= 2) {
            grey++;
            continue;
        }
        if (area[i].last == WHITE) white++;
        else if (area[i].last == BLACK) black++;
        else continue;
    }
    cout << white << " " << black << " " << grey;
}


int main() {
    Tile area [200001];
    int n, x, cur_pos(OFFSET);
    char dir;

    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> x >> dir;
        if (dir == 'R') BlackDir(area, x, cur_pos);
        else if (dir == 'L') WhiteDir(area, x, cur_pos);
    }   
    PrintNumberOfColor(area);

    return 0;
}

해설 코드

#include <iostream>

using namespace std;

#define MAX_K 100000

int n;
int a[2 * MAX_K + 1];
int cnt_b[2 * MAX_K + 1];
int cnt_w[2 * MAX_K + 1];
int b, w, g;

int main() {
    // 변수 입력
    cin >> n;

    int cur = MAX_K;

    for(int i = 1; i <= n; i++) {
        int x;
        char c;
        cin >> x >> c;
        if(c == 'L') {
            // x칸 왼쪽으로 칠합니다.
            while(x--) {
                a[cur] = 1;
                cnt_w[cur]++;
                if(x) cur--;
            }
        }
        else {
            // x칸 오른쪽으로 칠합니다.
            while(x--) {
                a[cur] = 2;
                cnt_b[cur]++;
                if(x) cur++;
            }
        }
    }

    for(int i = 0; i <= 2 * MAX_K; i++) {
        // 검은색과 흰색으로 두 번 이상 칠해진 타일은 회색입니다.
        if(cnt_b[i] >= 2 && cnt_w[i] >= 2) g++;
        // 그렇지 않으면 현재 칠해진 색깔이 곧 타일의 색깔입니다.
        else if(a[i] == 1) w++;
        else if(a[i] == 2) b++;
    }

    // 정답을 출력합니다.
    cout << w << " " << b << " " << g;
    return 0;
}

첨언

각 색의 바뀐 횟수, 최근에 바뀐 색을 멤버변수로 가지는 클래스를 만들어 해결하였다.

잔해물을 덮기 위한 사각형의 최소 넓이

유형	문제 경험치	난이도
Novice Mid / 시뮬레이션 I / 사각형 칠하기	40xp

작성 코드

#include <iostream>
#include <algorithm>

#define OFFSET 1000

using namespace std;

int cord[2001][2001] = {{0,},};

void Area(int x1, int y1, int x2, int y2, int input){
    for (int i = x1; i < x2; i++){
        for (int j = y1; j < y2; j++){
            cord[i][j] = input;
        }
    }
}

int main() {
    int x1, y1, x2, y2;
    int max_raw(-1), min_raw(2001);
    int max_col(-1), min_col(2001);
    int area(0);
    bool already_covered = true; // 사각형1이 사각형2에 의해 완전히 가려진 경우 

    for (int i = 1; i >= 0; i--){
        cin >> x1 >> y1 >> x2 >> y2;
        x1 += OFFSET;
        y1 += OFFSET;
        x2 += OFFSET;
        y2 += OFFSET;
        Area(x1, y1, x2, y2, i); // 사각형1의 가려지고 남은 부분만 1이고 나머지는 0이 된다.
    }

    for (int i = 0; i < 2001; i++){
        for (int j = 0; j < 2001; j++){
            if (cord[i][j] == 1){ // 최소, 최대 행/열을 구한다.
                already_covered = false;
                max_raw = max(max_raw, i);
                min_raw = min(min_raw, i);
                max_col = max(max_col, j);
                min_col = min(min_col, j);
            }
        }
    }
    if (!already_covered) 
        area = (max_raw - min_raw + 1) * (max_col - min_col + 1); 
        // 넓이니 구간을 구하는 방식으로 구했기 때문에 (x ~ x-1)
        // 값을 구할때는 +1을 해준다. 
        // ex) [0][1] ~ [0][3]일 경우에 길이는 2가 아니라 3이다. 
    cout << area;

    return 0;
}

해설 코드

#include <iostream>
#include <algorithm>

#define N 2
#define MAX_R 2000
#define OFFSET 1000

using namespace std;

int x1[N], y1[N];
int x2[N], y2[N];

int checked[MAX_R + 1][MAX_R + 1];

int main() {
    // 입력
    for(int i = 0; i < N; i++) {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
        
        // OFFSET을 더해줍니다.
        x1[i] += OFFSET;
        y1[i] += OFFSET;
        x2[i] += OFFSET;
        y2[i] += OFFSET;
    }
    
    // 직사각형에 주어진 순으로 1, 2 번호를 붙여줍니다.
    // 격자 단위로 진행하는 문제이므로
    // x2, y2에 등호가 들어가지 않음에 유의합니다.
    for(int i = 0; i < N; i++)
        for(int x = x1[i]; x < x2[i]; x++)
            for(int y = y1[i]; y < y2[i]; y++)
                checked[x][y] = i + 1;
    
    // 1, 2 순으로 붙였는데도
    // 아직 숫자 1로 남아있는 곳들 중 최대 최소 x, y 값을 전부 계산합니다.
    int min_x = MAX_R, max_x = 0, min_y = MAX_R, max_y = 0;
    bool first_rect_exist = false;
    for(int x = 0; x <= MAX_R; x++)
        for(int y = 0; y <= MAX_R; y++)
            if(checked[x][y] == 1) {
                first_rect_exist = true;
                min_x = min(min_x, x);
                max_x = max(max_x, x);
                min_y = min(min_y, y);
                max_y = max(max_y, y);
            }
    
    // 넓이를 계산합니다.
    int area;
    // Case 1. 첫 번째 직사각형이 전혀 남아있지 않다면 넓이는 0입니다.
    if(!first_rect_exist)
        area = 0;
    // Case 2. 첫 번째 직사각형이 남아있다면, 넓이를 계산합니다.
    else
        area = (max_x - min_x + 1) * (max_y - min_y + 1);

    cout << area;
    return 0;
}

첨언

넓이를 구할때도 배열에 구간을 구할때처럼 x ~ x-1 해주면된다.
남은 구역을 덮는 사각형은 최소, 최대 행/열을 구하면 간단하다.
사각형1이 사각형2에 의해 완전히 가려지는 경우를 생각하지않아 한번 틀렸다.
문제를 보고 여러 케이스를 고려하고 문제를 푸는 연습이 필요하다고 느낌

선두를 지켜라

유형	문제 경험치	난이도
Novice Mid / 시뮬레이션 II / 배열 기록	30xp

작성 코드

#include <iostream>

#define A 0
#define B 1

using namespace std;

int main() {
    int n, m, v, t;
    int time(0), result(0), lead(-1);
    int time_pos[2][1000001] = {{0,},};

    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> v >> t;
        for (int i = 0; i < t; i++) {
            time_pos[A][time + 1] = time_pos[A][time] + v; // 현재 이동거리는 1시간 전 이동 거리 + v 이다.  
            time++;                                      
        }
    }
    time = 0;
    for (int i = 0; i < m; i++){
        cin >> v >> t;
        for (int i = 0; i < t; i++) {
            time_pos[B][time + 1] = time_pos[B][time] + v;
            time++;
        }
    }
    for (int i = 0; i <= time; i++){
    	// 가장 처음 리드하는 사람을 정한다. 
        if (lead == -1){ 
            if (time_pos[A][i] > time_pos[B][i]) lead = A;
            else if (time_pos[A][i] < time_pos[B][i]) lead = B;
            continue;
        }
        
		// 기존에 리드하던 사람과 시간이 i일때 리드하고 있는 사람이 다를경우 
        // 리드하는 사람을 바꿔주고 선두가 바뀐 횟수(result)을 1 더해준다. 
        if (lead == B && time_pos[A][i] > time_pos[B][i]) {
            lead = A;
            result++;
        }
        else if (lead == A && time_pos[A][i] < time_pos[B][i]){
            lead = B;
            result++;
        }
    }

    cout << result;
    return 0;
}

해설 코드

#include <iostream>

#define MAX_T 1000000

using namespace std;

int n, m;
int pos_a[MAX_T + 1], pos_b[MAX_T + 1];

int main() {
    // 입력
    cin >> n >> m;
    
    // A가 매 초마다 서있는 위치를 기록
    int time_a = 1;
    for(int i = 0; i < n; i++) {
        int v, t;
        cin >> v >> t;
        
        while(t--) {
            pos_a[time_a] = pos_a[time_a - 1] + v;
            time_a++;
        }
    }
    
    // B가 매 초마다 서있는 위치를 기록
    int time_b = 1;
    for(int i = 0; i < m; i++) {
        int v, t;
        cin >> v >> t;
        
        while(t--) {
            pos_b[time_b] = pos_b[time_b - 1] + v;
            time_b++;
        }
    }
    
    // A와 B 중 더 앞서 있는 경우를 확인합니다.
    // A가 리더면 1, B가 리더면 2로 관리합니다.
    int leader = 0, ans = 0;
    for(int i = 1; i < time_a; i++) {
        if(pos_a[i] > pos_b[i]) {
            // 기존 리더가 B였다면
            // 답을 갱신합니다.
            if(leader == 2)
                ans++;
            
            // 리더를 A로 변경합니다.
            leader = 1; 
        }
        else if(pos_a[i] < pos_b[i]) {
            // 기존 리더가 A였다면
            // 답을 갱신합니다.
            if(leader == 1)
                ans++;
            
            // 리더를 B로 변경합니다.
            leader = 2; 
        }
    }
    
    cout << ans;
    return 0;
}

첨언

배열에 A와 B의 시간에 따른 위치를 구한 뒤, 둘을 비교하여 선두가 몇번 바뀌는지 구했다.
알고리즘은 해설과 동일하나 가장 처음 리드하는 사람을 따로 조건걸어 구할 필요가 없었구나 싶다.
중요한 내용 : unsequenced modification and access to 'val'
time_pos[A][time] = time_pos[A][time++] + v;
우리가 배웠던 이론상으로는 time이 0이라면 아래처럼 생각할 것이다.
time_pos[A][1] = time_pos[A][0] + v;
그런데 이는 컴파일러마다 다른 값을 출력하기에 경고가 발생하는 경우가 있다.
이렇게 컴파일마다 다른 값을 출력하는 것을
-> unspeified behavior(불특정 동작)라고 한다.

아래와 같이 어떤 컴파일러를 사용하는가에 따라 값이 달라지기 않게끔 사용하는 편이 좋다.
time_pos[A][time + 1] = time_pos[A][time] + v; time++;
실제로 헷갈리기도 하니, 기왕이면 직관적으로 알 수 있는 코드를 작성하도록 노력하자.

[240722] https://github.com/mna11/codetree-TILs/tree/main/240722
[240723] https://github.com/mna11/codetree-TILs/tree/main/240723
[240724] https://github.com/mna11/codetree-TILs/tree/main/240724
[240725] https://github.com/mna11/codetree-TILs/tree/main/240725
[240726] https://github.com/mna11/codetree-TILs/tree/main/240726
[240727] https://github.com/mna11/codetree-TILs/tree/main/240727
[240728] https://github.com/mna11/codetree-TILs/tree/main/240728

MNA

개발자 지망생

이전 포스트

[코드트리 조별과제] 1주차

다음 포스트

[코드트리 조별과제] 2주차

작성 코드

해설 코드 1 :Class

해설 코드 2 :Tuple

첨언

작성 코드

해설 코드

첨언

작성 코드

해설 코드

첨언

작성 코드

해설 코드

첨언

작성 코드

해설 코드 :Class

해설 코드 :Pair

첨언

작성 코드

해설 코드

첨언

작성 코드

해설 코드

첨언

작성코드

해설코드

첨언

작성 코드

해설 코드

첨언

작성 코드

해설 코드

작성 코드

해설 코드

첨언

작성 코드

해설 코드

첨언

작성 코드

해설 코드

첨언

[코드트리 조별과제] 1주차

[코드트리 조별과제] 3주차

0개의 댓글