Algorithm - Day 2

선생님개발이하고싶어요·2025년 6월 10일

Algorithm-Test

목록 보기

2/17

매일 알고리즘 3문제씩 풀기 챌린지 2일차 👊🏻

Q1. 각도기

https://school.programmers.co.kr/learn/courses/30/lessons/120829
각에서 0도 초과 90도 미만은 예각, 90도는 직각, 90도 초과 180도 미만은 둔각 180도는 평각으로 분류합니다. 각 angle이 매개변수로 주어질 때 예각일 때 1, 직각일 때 2, 둔각일 때 3, 평각일 때 4를 return하도록 solution 함수를 완성해주세요.

예각 : 0 < angle < 90
직각 : angle = 90
둔각 : 90 < angle < 180
평각 : angle = 180

내 풀이

어제 너무 어려운 문제를 풀어서 오늘은 좀 쉬운 거 하고 싶었다... 😇

function solution(angle) {
    let answer = 0;
    if (angle > 0 && angle < 90) answer = 1;
    else if ( angle === 90 ) answer = 2;
    else if ( angle < 180 ) answer = 3;
    else if ( angle === 180 ) answer = 4;
    else throw new Error('wrong angle');
    return answer;
}

오답노트

처음에 switch case 문을 쓰고 싶었는데 어떻게 조건을 줘야할 지 모르겠어서 if/else 문으로 바꿨는데, switch 문을 쓰신 분이 있어서 가져와봄
근데 값을 정확히 비교해야 하는 직각 / 평각이 있어서 가능했던 것 같다.

function solution(angle) {
    switch(angle) {
        case 90: return 2;
        case 180: return 4;
        default:
            return angle > 0 && angle < 90 ? 1 : 3;
    }
}

다른 접근 방식

? 연산자를 이용한 깔끔한 풀이

function solution(angle) {
    return angle < 90 ? 1 : angle === 90 ? 2 : angle < 180 ? 3 : 4;
}

return 1, 2, 3, 4 를 각각 주지 않고 answer++ 로 처리하는 방식

function solution(angle) {
    let answer = 1;

    if (angle >= 90) answer++;
    if (angle > 90) answer++;
    if (angle >= 180) answer++;
    if (angle > 180) answer++;

    return answer;
}

✏️ 주요 개념 공부

switch 문의 동작 : 값과 값의 “===” 비교를 통해 정확히 일치하는 값인 케이스만 실행

switch (x) {
  case value1:		  // x === 'value1'?
    // do ...
    break;
  case value2:
    // do ...
    break;
  ...
}

만약 굳이 조건절을 case로 주고 싶다면, 약간의 꼼수로 이렇게 쓸 수는 있음
(하지만 뭐... if 문이 있는데 굳이.. 알아보기 힘들게...)

switch (true) {
  case (a > 0 && a < 90):	//  true === (a > 0 && a < 90)?
    answer = 1;
    break;
  case (a === 90):
    answer = 2;
    break;
  default:
    console.log('기타');
}

Q2. 양꼬치

https://school.programmers.co.kr/learn/courses/30/lessons/120830
머쓱이네 양꼬치 가게는 10인분을 먹으면 음료수 하나를 서비스로 줍니다. 양꼬치는 1인분에 12,000원, 음료수는 2,000원입니다. 정수 n과 k가 매개변수로 주어졌을 때, 양꼬치 n인분과 음료수 k개를 먹었다면 총얼마를 지불해야 하는지 return 하도록 solution 함수를 완성해보세요.

0 < n < 1,000
n / 10 ≤ k < 1,000
서비스로 받은 음료수는 모두 마십니다.

내 풀이

~~솔직히 양꼬치에 칭따오🍺 먹고 싶어서 풀었음~~

function solution(n, k) {
    const yang = 12_000;
    const drink = 2_000;
    return payment = (yang * n) + (drink * (k - Math.trunc(n/10) ));
}

오답노트

아무 생각 없이 trunc() 썼는데, 문제의 특성 상 floor()가 더 적절했던 것 같음

다른 접근 방식

이중 틸드(~) 문법 처음 봐서 공부할 겸 가져옴

function solution(n, k) {
    k-=~~(n/10);
    if (k < 0) k = 0;
    return n*12000+k*2000;
}

✏️ 주요 개념 공부

[ 비트 연산자 ]

피연산자를 32bit 이진수 정수로 변환한 뒤 그 비트 하나하나를 대상으로 연산을 수행하는 연산자

& (AND 비트 연산) :두 개의 피연산자의 각 자리마다 대응하는 비트가 모두 1일 경우 1을 반환

const a = 5; // 00000000000000000000000000000101
const b = 3; // 00000000000000000000000000000011

console.log(a & b); // 00000000000000000000000000000001
// Expected output: 1

| (OR 비트 연산) :두 개의 피연산자의 각 자리마다 대응하는 비트가 하나라도 1일 경우 1을 반환

const a = 5; // 00000000000000000000000000000101
const b = 3; // 00000000000000000000000000000011

console.log(a | b); // 00000000000000000000000000000111
// Expected output: 7

^ (XOR 비트 연산) :두 개의 피연산자의 각 자리마다 대응하는 비트가 하나만 1일 경우 1을 반환, 둘 다 1이면 0을 반환

const a = 5; // 00000000000000000000000000000101
const b = 3; // 00000000000000000000000000000011

console.log(a ^ b); // 00000000000000000000000000000110
// Expected output: 6

~ (비트 NOT) : 피연산자의 비트를 반전

const a = 5; // 00000000000000000000000000000101
console.log(~a); // 11111111111111111111111111111010
// Expected output: -6

const b = -3; // 11111111111111111111111111111101
console.log(~b); // 00000000000000000000000000000010
// Expected output: 2

위 풀이에서, ~~(n/10)은 n/10을 이진수 정수로 변환(소수점 아래는 버림)
→ ~(n/10) 으로 보수 처리 (비트 반전)
→ ~(~(n/10)) 으로 다시 반전 = 원래 수로 되돌아옴
따라서 결국 소수점 아래를 버리고 정수 부분만 남는 trunc()와 같은 역할 수행

// 예시
~~3.9      // 3
~~(-3.9)   // -3
~~'123'    // 123 (문자열도 정수로 변환)
~~'hello'  // 0 (NaN → 0)

	`Math.trunc()`	`~~` (Double Tilde)
입력	숫자만 명확하게 처리	숫자/문자열 등 넓은 입력도 허용 (문자열이면 강제로 숫자로 변환)
가독성	명확 (`trunc`라는 이름 그대로 잘려서 직관적)	가독성 떨어짐 (의미를 한 번 더 해석해야 함)
용도	“정수부만 필요해!”를 명확히 표현	퍼포먼스 트릭처럼 간단하게 쓸 때 사용

Q3. 분수의 덧셈

https://school.programmers.co.kr/learn/courses/30/lessons/120808
첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

내 풀이

기약 분수가 뭔지 까먹어서 찾아봄... 그냥 다 약분한 거더라

function solution(numer1, denom1, numer2, denom2) {
	let numer = numer1 * denom2 + numer2 * denom1;
    let denom = denom1 * denom2
    
    for (let i = (numer >= denom) ? denom : numer; i >= 1 ; i--) {
        if (numer % i === 0 && denom % i === 0) {
            numer = numer / i;
            denom = denom / i;
        } 
    }
    return [numer, denom];

오답노트

최대공약수를 찾아서 한 번만 나누면 되는데 for 문을 계속 i--로 돌린 게 문제
최대공약수(GCD)는 유클리드 호제법으로 찾을 수 있음

✅ 따라서 getGcd(a,b)는 a%b = r 을 구하고, a = b; b = r; 으로 getGcd(b,r)을 구하고, ... 이걸 r = 0 이 될 때까지 반복해서, 그 때의 b 값을 return 해야 한다.

function sumFraction(numer1, denom1, numer2, denom2) {
    let numer = numer1 * denom2 + numer2 * denom1;
    let denom = denom1 * denom2;
    
    const getGcd = (a, b) => {
        let r = a % b;
        if (r === 0) return b;
        else return getGcd(b, r);
    }
    const g = getGcd(numer, denom); 
    return [ numer / g, denom / g]
}

// getGcd 를 간단히 쓰면 이렇게도 표현할 수 있다.
const _getGcd = (a, b) => ( b === 0 ) ? a : _getGcd(b, a % b);

다른 접근 방식

denom 을 곱해서 약분하지 않고, 최소공배수를 구하는 방식도 가능
최소공배수는, 약수를 제외한 나머지 서로소를 곱한 수이므로
$lcm(a,b)= (a×b) ÷ gcd(a,b)$ 의 관계를 가진다.

function getGcd(a, b) {
  return b === 0 ? a : getGcd(b, a % b);
}

function getLcm(a, b) {
  return (a * b) / getGcd(a, b);
}

function sumFraction(numer1, denom1, numer2, denom2) {
    const lcm = getLcm(denom1, denom2);
    return [ (numer1 * (lcm / denom1)) + 
            (numer2 * (lcm / denom2)), lcm ];
}

✏️ 주요 개념 공부

[ 유클리드 호제법 ]
두 양의 정수 a, b (a > b)에 대하여 a = bq + r이라 하면 a, b 의 최대공약수는 b, r의 최대공약수와 같다. 즉, gcd(a, b) === gcd(b, r) 이 성립한다. r = 0 일 때, a, b의 최대공약수는 b가 된다.
~~수학 공부까지 해야하다니...~~ 😇

$\gcd(a, b) = G,\gcd(b, r) = G'$ 라고 하자.
그럼 적당한 서로소 정수 ( A, B )에 대해 $a = GA, \quad b = GB$ 로 변환할 수 있다.
이 식을 $a = bq + r$ 에 대입하면

GA = GB \cdot q + r

이므로,

r = G (A - Bq)

여기서 G는 b와 r의 공약수임을 알 수 있다. b와 r의 최대공약수가 G' 이므로, G는 G'의 약수( $G' = mG$ )로 두자. 그러면 적당한 서로소 정수 k, l에 대해

b = G \cdot B = G' \cdot k = G \cdot m \cdot k \\ r = G (A - Bq) = G' \cdot l = G \cdot m \cdot l

각 변을 G로 나누면

B = m \cdot k \\ A - Bq = m \cdot l

따라서

A = ml + Bq = ml + mk \cdot q = m (l + kq)

여기서 $m$ 은 $A =m(l + kq)$ 와 $B = mk$ 가 공통으로 가지는 공약수인데, $A$ 와 $B$ 는 서로소이므로, $m = 1$ 이 항상 성립

G' = mG = G\\ ∴ gcd(a, b) = gcd(b, r)

선생님개발이하고싶어요

FE 개발자 지망생입니다..

이전 포스트

Algorithm - Day 1

다음 포스트

Algorithm - Day 2

Algorithm-Test

Q1. 각도기

내 풀이

오답노트

다른 접근 방식

✏️ 주요 개념 공부

Q2. 양꼬치

내 풀이

오답노트

다른 접근 방식

✏️ 주요 개념 공부

Q3. 분수의 덧셈

내 풀이

오답노트

다른 접근 방식

✏️ 주요 개념 공부

Algorithm - Day 1

Algorithm - Day 3

0개의 댓글