[백준] 2839번 설탕 배달, 파이썬과 C(C++) 메모리/시간 차이 비교

개요

알고리즘, 자료구조에 관심이 있는 사람이라면 백준을 다 알고 계실 것이라고 생각합니다.

자료구조를 복습하고 있고, 알고리즘은 아직 배우지 않은 상태인데요.

이렇게 알고리즘에 대한 배경지식이 전무한 상태로 문제를 풀 기회가 생겨서 한 번 풀어봤습니다.

 

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

 

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

 

예제

입력	출력
18	4
4	-1
6	2
11	3

 

문제 정보

▲2839번 문제정보

 

풀이

저는 3과 5로 입력한 N을 표현하는 식 중에 5가 가장 많이 쓰이는 것을 고르면 된다고 생각했습니다.

예를 들어, 30을 5로 나타내면 6번만 사용하면 되지만 3으로 나타내면 10번이나 사용해야하기 때문입니다.

그래서 반복문을 이용해서 큰 수부터 아래로 조건에 맞는 숫자를 찾으면 되겠다고 생각했습니다.

조건이 맞는 숫자를 찾으면 출력하고 그대로 프로그램을 종료시켰습니다.

그러면 조건에 맞지 않는 숫자를 따로 찾을 필요가 없기 때문입니다.

만약, 조건에 맞지 않는다면 반복문을 빠져 나올 것이고 그때 -1을 출력하게 했습니다.

 

큰 수에서 아래로 내려가면서 찾는 구조로 이중 for문을 이용해서 해결했습니다. 코드로 확인해보겠습니다.

▲C언어 코드

이렇게 작성해서 제출했더니 컴파일 에러가 뜨더군요.

아무래도 비주얼스튜디오에서는 scanf나 fopen과 같은 함수들은 _s를 붙여서 사용하는 것을 권장하고 있는데

백준에서는 이를 컴파일 에러라고 판단하는 것 같습니다. 그냥 scanf를 사용하니 정답처리가 되었습니다.

 

이렇게 문제를 해결하고 조금 더 생각을 해봤습니다.

지금 5와3 둘 다 최대 값에서 0까지 다 확인하는데, 전부 확인하지 않아도 되는 코드가 분명 존재할 것 같았습니다.

하지만, 제 수준에서는 더 확인을 할지 말지 결정하는 것이 다 확인하는 것보다 낭비를 일으킬 수 있다고 판단했습니다. 실제로 조금조금 바꿔보니 오히려 시간만 길어지고, 복잡해졌습니다.

이건 나중에 알고리즘을 공부하고 Greedy(탐욕) 알고리즘에 대해 정확히 알게 되면 다시 생각해 볼 예정입니다.

Greedy 알고리즘은 최적해를 구하는 알고리즘입니다. 자세한 내용은 자료구조 게시판에서 다루도록 하겠습니다.

 

Python3 VS C(C++) 비교하기

기존에는 코딩 테스트를 응시하는 인원의 대부분이 알고리즘의 원조인 C++을 대부분 사용했다고 하는데요.

지금은 많은 사람들이 파이썬을 사용한다고 합니다.

아무래도 파이썬이 배우기 쉽고 다양한 라이브러리가 존재하기 때문에 비전공자도 쉽게 접할 수 있다는 장점이 있어서 그런 것 같습니다.

 

파이썬은 빠르고 비교적 쉽게 문제를 해결할 수 있다는 점에서 유리하기 때문에 코딩테스트에서 많이 사용됩니다.

C++은 알고리즘 대회같이 컴파일 시간, 메모리 관리가 중요한 상황에서 많이 쓰입니다.

 

실제로 얼마나 차이가 나는지 위의 코드를 파이썬에서 똑같이 구현해보도록 하겠습니다.

▲파이썬 코드

파이썬의 for in range 의 경우 리스트로 만들어서 반복하는 것이기 때문에 while문으로 구현했습니다.

오히려 코드의 수가 줄어들고 가독성이 좋아진 것을 확인할 수 있습니다.

 

실제 사용된 메모리와 컴파일 시간, 코드 길이를 확인해보겠습니다.

 

▲파이썬(위), C언어(아래) 의 차이

 

보시는 것처럼 많은 차이가 나는 것을 육안으로 확인할 수 있습니다.

 

같은 알고리즘의 코드이지만 엄청나게 많은 차이가 나는 것을 확인할 수 있습니다.

제가 아는 선에서 C언어는 변수에 값을 저장하면 지정된 주소공간을 할당해서 값을 저장하지만, 파이썬은 변수에 값을 저장하면 그 값이 저장되어 있는 객체의 주소를 담습니다.(C언어의 포인터와 비슷한 개념입니다.) 

이런 작은 차이들이 메모리나 시간에서 많은 차이를 보이는 것이 아닐까 생각합니다.

 

작고 간단한 프로그램이어서 큰 상관은 없지만, 큰 프로그램을 설계한다면 이런 부분도 잘 고려할 필요가 있습니다.

무조건 시간이 빠르고 메모리 효율이 좋은 것보단, 상황과 여건을 고려해서 언어를 선택하는 것이 중요하겠습니다.

 

정리

처음으로 백준의 코딩테스트 문제를 풀어봤습니다. 

아무래도 문제에 대한 경험이 별로 없기 때문에 컴파일 시간을 줄여야된다는 압박도 상당했던 것 같습니다.

자료구조와 알고리즘을 더 공부해서 더욱 효율적이고 빠르게 문제를 해결하는 것을 목표로 삼겠습니다!