꼬부기의 공대이야기

백준 baekjoon 단계별로 풀어보기 - 2. 사칙연산 도전하기 본문

Algorithm

백준 baekjoon 단계별로 풀어보기 - 2. 사칙연산 도전하기

전설의꼬부기 2018.04.22 13:07

안녕하세요! 꼬부기입니다.

이번 포스팅은 백준 단계별로 풀어보기의 문제집 2번인 '사칙연산 도전하기'에 대해서 풀이를 적으려고 합니다.
이번 문제집 또한 저번 풀이집이었던 '1번 - 입/출력 받아보기'처럼 기본기를 다지는 문제들로 이루어져 있습니다.
각자가 선택한 언어에 대해서 기본 연산자를 사용하는 방법을 익힐 수 있는 문제들을 지금부터 풀어보시겠습니다.

1. 백준 1000번 - A+B

이 문제는 두 개의 정수를 입력받아 덧셈 결과를 출력하는 문제입니다.
그 뒤에 이어지는 1001번, 10998번, 1008번도 마찬가지로 사칙연산 중 하나인 뺄셈, 곱셈, 나눗셈 결과를 출력하는 문제입니다. 1008번 나눗셈 문제는 C언어 같은 경우에 자료형이 달라지면서 생기는 문제점이 있기 때문에 아래에서 설명을 하고, 나머지 1001번, 10998번, 1008번은 코드만 작성하겠습니다.

#덧셈 코드보기

#뺄셈 코드보기

#곱셈 코드보기

4. 백준 1008번 - A/B

1008번 같은 경우에는 정수 자료형 int만으로는 해결 할 수 없는 문제입니다.
C언어에는 소수를 다루는 자료형에 float형과 double형이 있는데, 이 문제에서 절대/상대 오차는 10^-9까지 허용한다는 조건 때문에 double형 자료형을 사용해야 합니다. float은 소수점 유효 자리수가 6, double은 15개까지 가능하기 때문입니다.

이 문제를 int 자료형만으로 해결하고자 하면 다음과 같은 문제가 생깁니다.
예를 들어 10 / 4 = 2.5 가 우리가 생각하는 정상적인 결과이지만, int형 만을 사용한다면 말 그대로 정수형 이기 때문에 10 / 4 = 2 라는 결과가 나오게 됩니다. 소수점이 사라지기 때문입니다. 따라서 입력은 정수로 받되, 결과는 정수가 아닌 실수(double)형을 사용해야 합니다.

#나눗셈 코드보기

5. 백준 10869번 - 사칙연산

이 문제는 위에서 풀었던 결과를 한 번에 출력하는 문제입니다. 따라서 입력 두 개를 받았을 때 덧셈, 뺄셈, 곱셈, 나눗셈, 그리고 나머지를 출력하면 됩니다. 마지막에 A%B는 module 연산이라고 해서 나머지를 구하는 연산자입니다. 이 나머지를 이용해서 해결하는 문제가 종종 나오니 익혀두시면 유용하게 쓰일 것입니다.

#사칙연산 코드보기

6. 백준 10430번 - 나머지

이 문제는 모듈러 연산을 연습하는, 즉 나머지를 구하는 연산에 대해서 연습할 수 있는 문제입니다.
문제에서 주어진 (A+B)%C, (A%C + B%C)%C, (A*B)%C, (A%C * B%C)%C의 결과를 출력하면 됩니다.

#나머지 코드보기

문제집 7번인 백준 2558번 A+B - 2또한 위의 문제들과 비슷하므로 마지막 문제인 설탕 배달 문제로 넘어가겠습니다.

8. 백준 2839번 - 설탕 배달

이 문제는 주어진 설탕 무게에 대해서 5kg과 3kg봉지로 나누어 배달할 때, 가장 적게 봉지를 나누는 경우 그 개수를 출력하는 문제입니다. 그래서 저는 처음에 다음과 같이 접근 방식을 취했습니다.

- 5kg으로 최대한 담는다.
- 3kg으로 최대한 담는다.
- 만약 남는 설탕이 있으면 -1을 출력한다.

#그리디 코드보기

이러한 접근 방법을 '그리디 알고리즘', 혹은 '탐욕 알고리즘' 방식이라고 합니다. 크게 담을 수 있는 것을 먼저 담고 나서, 작은 용량으로 봉지를 담을 경우가 최선일 경우라고 가정한 상태로 결과를 구하는 방법입니다. 나중에 그리디 알고리즘에 대해서 자세하게 포스팅하겠습니다.

하지만 이 문제에서는 그리디 알고리즘으로 접근하면 틀리다고 결과를 얻게 됩니다. 예를 들어 N = 11일 경우 제가 짠 알고리즘대로 가자면 5kg으로 2개 담고 1kg이 남아 -1을 출력하게 되는데, 답은 5kg 1개와 3kg 2개, 즉 3이라는 숫자를 출력해야 합니다. 따라서 잘못된 코드입니다.

따라서 5kg과 3kg봉지로 나눌 수 있는 모든 경우에 대해서 알아보는 코드를 작성해서 문제를 해결했습니다.

#설탕배달 코드보기

다음은 'for문 사용해보기'에 대해서 포스팅하겠습니다.
이 글을 읽는 많은 분들 즐코!

2 Comments
댓글쓰기 폼