꼬부기의 공대이야기

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

Algorithm

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

전설의꼬부기 2018. 4. 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
댓글쓰기 폼
Prev 1 2 3 4 5 6 7 Next