JArchive 프로그래밍 일기

문제

최대공약수와 최소공배수 프로그래머스 level1

리뷰

최대공약수는 유클리드 호제법으로 구할 수 있다.

유클리드 호제법은 나머지를 구하는 MOD 연산을 이용한다.

MOD 연산

// MOD 연산 : 나머지를 구하는 연산 
5 % 3 = 2 
// 5를 3으로 나눈 몫은 1 이다. 나머지는 2. 

유클리드 호제법 (Euclidean algorithm)

2개의 자연수에 대해서. a 를 b로 나눈 나머지를 r 이라고 한다면. ( 단, a > b )

a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라 b를 r로 나눈 나머지를 구하는 과정을 반복하여.

나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대 공약수다.

예시를 읽으면 금방 이해된다. 위키백과 유클리드호제법

14와 24의 최대공약수(GCD, Greatest Common Divisor)

// 24와 14의 최대 공약수 구하기.  주의할 점은 a > b 

24 % 14 = 10 
14 % 10 = 4
10 % 4  = 2
4  % 2  = 0

// MOD 연산 결과가 0 이 되면 종료된다. -->  24와 14의 최대공약수는 2 

나머지가 0 일 때, 나누는 수 2가 최대공약수다.

재귀 코드

// 나머지가 0이 나올 때 종료.
int GCD(int a, int b)   // 단, a > b
{
    if (b == 0) return a;
    else return GCD(b, a%b);
}

반복문 코드

int GCD(int a, int b){  // 단, a > b
    int temp = 0;

    while(b){
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

최소공배수 (LCM, Least Common Multiple)

a 와 b의 최소공배수는 최대공약수를 구하면 계산할 수 있다.

LCM =  a * b * GCD(a, b);

코드

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

int gcd(int a, int b) 
{
    if (b == 0) return a;
    else return gcd(b, a%b);

}

vector<int> solution(int n, int m) {
    vector<int> answer;

    // 큰 값을 앞에, 작은 값을 뒤에.
    int gcd_num = gcd(max(n, m), min(n, m));

    answer.push_back(gcd_num);
    answer.push_back((n*m)/gcd_num);

    return answer;
}

Angry Professor

HackerRank Algorithm

교수님은 최소 k명의 학생이 수업 시작 시간에 도착해야 화가나지 않는다.

음수 는 일찍온 학생. 0은 제시간에 온 학생. 양수는 지각한 학생이다.

음수와 0 의 개수가 k명보다 작거나 같은지 판단하는 문제다.

내 코드

string angryProfessor(int k, vector<int> a) {

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

    int cnt = 0;
    string answer = "NO";

    for (int i = 0; i < a.size() && cnt < k; i++) {
        if (a[i] <= 0) {
            cnt++;
        }
    }

    if (cnt < k) answer = "YES"; // 화남 

    return answer;
}

Operators

HackerRank Coding Chanllenge Day2

double, int 자료형을 계산하여 실수형이 나오는데.

가장 가까운 int로 답을 출력하는 문제다.

중요한 건 반올림 함수 round() . 가장 가까운 int 로 출력해야 하기 때문이다.

#include <cmath>

//  round(12.62)  -> 12 가 반환된다 
double round(double num);
long double round(long double num);

참고] 버림 함수 trunc()

소수점 아래 수는 정수로 바꾼다.

#include <cmath>

float trunc(float num);
double trunc(double num);
long double trunc(long double num);

// trunc(3.97)  -> 3

truncate 단어를 줄여서 만들었나보다.

내 코드

void solve(double meal_cost, int tip_percent, int tax_percent) {

    double total = meal_cost;
    double tip = (double)tip_percent * meal_cost / 100;
    double tax = (double)tax_percent * meal_cost / 100;

    cout << round(total + tip + tax);

    return;
}

문제

멀쩡한 사각형 프로그래머스 level2

리뷰

가로 W, 세로 H가 1억 이하의 자연수로 들어오기 때문에, 변수들을 long long 형으로 처리해줘야 한다.

넓이를 구할 때 얘네를 곱셈을 하니까 int 표현 범위를 넘어설 수 있기 때문이다.

가로, 세로 비율에 따라서 사용불가한 종이의 개수가 일정하다.

최대공약수가 필요하겠다 싶어서 gcd 함수를 만들었다.

// 재귀 형태 GCD
long long gcd(long long a, long long b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

// 반복문 형태 GCD 
int GCD(int a, int b){

    int i = 1;
    for(i = (a<b)? a:b; i > 0; i--){ // 작은 수를 i로 두고 시작 
        if( (a%i == 0 ) && (b%i == 0) ){ // 둘 다 나누어 떨어지는 숫자를 구하면 탈출 ! 
            break;
        }
    }
    return i;
}

너비 W를 gcd 로 나눈 길이와 높이 H를 gcd로 나눈 길이로 된 사각형에서 규칙성이 발견된다.

예를 들어, 가로 8, 세로 12 라면, 최대공약수 gcd가 4이다.

가로 2, 세로 3 사각형 단위로 종이가 총 6칸이다. 여기서 사용불가 종이가 4개씩 발생한다.

사용불가 종이가 가로2 + 세로3 - 1개 씩 발생한다. ( 4 == 2+3-1)

직사각형 종이의 가로 8, 세로12 에서도 최대공약수 만큼 사용불가 종이가 발생한다.

사용불가 16개 == 8 + 12 - 4

총 넓이 (W * H) 에서 16개를 빼면 답이 나온다.

이 때 W, H를 곱한 수가 int 표현범위를 초과할 수 있으니까 전부 long long 으로 처리한다.

코드

using namespace std;

long long gcd(long long a, long long b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

long long solution(int w,int h) {
    long long answer = 1;
    long long total =(long long)w * h; // 직사각형의 총 넓이  
    long long gcd_num = gcd((long long)w, (long long)h); // W, H의 GCD 

    answer = total - (w + h - gcd_num);

    return answer;
}

처음 짰던 코드

using namespace std;

long long gcd(long long a, long long b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

long long solution(int w,int h) {
    long long answer = 1;
    long long total = (long long)w*h;

    long long gcd_num = gcd((long long)w, (long long)h); // GCD

    long long temp_w = (long long)w / gcd_num; // w를 GCD로 나눈 길이
    long long temp_h = (long long)h / gcd_num; // h를 GCD로 나눈 길이 

    // 사용 불가 종이의 개수  == (temp_w + temp_h -1)
    long long block_cnt = w / temp_w; 
    answer = total - (block_cnt * (temp_w + temp_h -1) );

    return answer;
}

Birthday Cake Candles

HackerRank Algorithm Warmup

벡터에서 최대값 원소를 찾는다.

최대값 원소가 총 몇개인지 리턴하는 문제다.

내 코드

int birthdayCakeCandles(vector<int> a) {
    // 최대 원소 값 
    int max_one = *max_element(a.begin(), a.end());
    // 개수 
    int cnt = count(a.begin(), a.end(), max_one);

    return cnt;
}

Staircase

HackerRank Algorithm Warmup

계단처럼 '#'을 찍는 문제다. 별찍기 문제랑 비슷하다.

line 0 : ' ' space 3개 + '#' 1개

line 1 : ' ' space 2개 + '#' 2개

line 2 : ' ' space 1개 + '#' 3개

내코드는 for문을 3개 써서 풀었는데. 다른 분 코드가 인상깊어서 덧붙인다.

내 코드

void staircase(int n) {

    int len = n;

    for (int i = len-1; i >=0; i--) {

        for (int j = 0; j < i; j++) {
            cout << ' ';
        }

        for (int k = 0; k < len - i; k++) {
            cout << '#';
        }
        cout << '\n';
    }

}

다른 분 코드

void staircase(int n) {
    for(int i = 1 ; i <= n ; i++){
        string h(i, '#');
        string s(n-i, ' ');
        cout << s << h <<'\n';
 }

문제

정수 제곱근 판별 프로그래머스 level1

리뷰

양의 정수 x의 제곱이 아니라면, sqrt() 결과가 실수가 된다.

따라서 정수로 나오는지 실수로 나오는지 구분해야 한다.

// 제곱근을 long long 으로 형변환 한 것과 비교  
sqrt(n) - (long long)sqrt(n)

제곱할 때는 pow() , 제곱근 구하는 sqrt() 가 있다.

pow 도 자료형에 따라 몇 개 더 있으니 정리했다.

#include <cmath>

// x의 y승을 계산하는 pow() 

double pow(double x, double y); // 밑수x, 멱수y 순으로 매개변수 넣기 
float powf(float x, float y);
long double powl(long double x, long double y);

/*
float 4bytes, double 8bytes, long double 8bytes 
*/

내 코드

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

long long solution(long long n) {
    long long answer = -1;  // 양의 정수 x의 제곱이 아니라면 -1 

    if ( (sqrt(n) - (long long)sqrt(n)) == 0) {
        answer = pow(sqrt(n) + 1, 2);
    }

    return answer;
}

다른 사람의 코드

#include <string>
#include <vector>
#include <math.h>
using namespace std;

long long solution(long long n) {
    long long answer = sqrt(n);

    return powl(answer, 2) == n ? powl(answer + 1, 2) : -1;
}