'2021/02/24'에 해당되는 글 4건

www.acmicpc.net/problem/2839

문제 설명

설탕 3kg, 5kg 봉지가 있는데 특정 kg수를 봉지를 최대한 적게 사용하여 만드려고 할때 가장 적게 쓰는 봉지의 수를 구하는 문제입니다.

18kg를 3kg봉지와 5kg봉지를 사용하여 채우려면 3kg짜리 6개를 써서 18kg를 만들 수도 있습니다.

하지만 5kg 짜리 3개와 3kg짜리 1개를 사용하여 만들면 총 4개의 설탕봉지를 사용합니다. 그러니까 4가 답이되는 것입니다.

3kg와 5kg만 사용하므로 만들 수 없는 수도 존재합니다. 그럴때는 -1을 출력하는 문제입니다.

입력은 채우는 설탕의 kg수 N이 주어지고 N의 범위는 3이상 5000이하(3<= N <=5000)입니다.

몇가지 입력에 대한 출력을 먼저 보고 문제를 풀어보시고 풀이를 봐주세요.

풀이1 - DP

두가지 풀이가 있습니다. 전형적인 DP방식의 풀이와 그리디한 방식으로 푸는 방법이지요. 첫번째 풀이는 DP를 사용한 풀이입니다.

만약 현재 i kg를 달성하려면 이 전에 계산한 (i-3)kg와 (i-5)kg 중 작은 것에 1을 더하면 현재 i kg을 채울 수 있는 최소의 봉지수가 나오겠네요.

dp[i] = min(dp[i-3] + 1, dp[i-5] +1)

그런데 만들 수 없는 수는 0이겠죠? 예를 들면 4는 절대로 3과 5를 조합하여 만들 수가 없는데요.  그러면 항상 0이 최소의 수가 되니까 조건을 달아야합니다.

만약 dp[i-3]에 0보다 큰 값이 있을때, dp[i-5]일때 0보다 큰 값이 있을때 만 계산하게 만드는 것입니다.

코드는 아래와 같습니다.

#include <iostream>
using namespace std;
int dp[5001]; //global 변수이기때문에 0으로 초기화된 배열

int main() {
	int n;
	cin >> n;
	//3kg와 5kg를 만드는 가장 최소의 봉지수는 1
	//따라서 dp[3]과 dp[5]는 무조건 1
	dp[3] = dp[5] = 1;	

	//3과 5 다음인 6부터 for loop 순회
	for (int i = 6; i <= n; i++) {
		if (dp[i - 3]) dp[i] = dp[i - 3] + 1;

		//이미 dp[i-3]에 값이 존재할때 dp[i]가 업데이트 됐었을 수 있다.
		//만약 dp[i]에 값이 없다면 dp[i] = dp[i-5] +1 로 업데이트
		if (dp[i - 5]) dp[i] = dp[i] ? min(dp[i] , dp[i - 5] + 1) : dp[i - 5] + 1;
	}
	cout << (dp[n] == 0 ? -1 : dp[n]) << endl;
	return 0;
}

먼저 dp라는 배열을 0으로 셋팅해놓고 (전역변수이기 때문에 저절로 0으로 초기화됩니다.) dp[3] = dp[5]를 1로 만든 후에 앞서 설명한 것을 for문 안에 구현하면 됩니다.

풀이2 - Greedy

설탕이 25kg가 있다면 5kg로만 계속 사용하여 채우면 됩니다. 그러면 5개 봉지만 사용하면 되겠네요. 그렇다면 우리가 kg을 사용할 일이 굳이 있을까요? 우리가 5kg으로 모두 채울 수 있다는 것을 미리 알면 오히려 3kg를 사용하면 불리하다는 것을 알 수 있습니다. 그렇다면 5kg으로 나눠진다는 것만 알면 되지 않을까요? 이때 mod연산 %연산이 사용됩니다. %5 연산을 하여 0이 되지 않는다면 3kg를 봉지를 사용해야겠죠. 

그리고 난 후 다시 5kg로 나눠 떨어지는지 확인합니다. 만약 나눠떨어지면 나눈 몫만큼의 5kg봉지가 사용되고 프로그램을 바로 종료시키면 되는 아이디어입니다.

전체 C++ 소스코드는 아래와 같습니다.

#include <iostream>

using namespace std;

int N;
int main() {
	cin >> N;
	int ans = 0;
	while (N>=0) {
		if (N % 5 == 0) {	//가장 큰 수로 나누는게 가장 작은수랑 섞어서 나누는 것보다 유리
			ans += (N / 5);	//나눈 몫을 더한 것이 정답
			cout << ans << endl;
			return 0;
		}
		N -= 3;	//3kg을 빼고 
		ans++;	//가방 하나 늘어남
	}
	cout << -1 << endl;
}

두가지 방식의 풀이를 알아보았는데 저도 얼핏 dp만 생각하고 있었는데 다른 사람의 해답을 보니 이러한 방법이 있다는 것을 알았습니다. 역시 저빼고 다른 사람들은 똑똑한것 같습니다.

적성검사가 끝나고 난 후 약 2주후에 적성 검사 결과가 나온다. 적성검사 개판쳤던것에 비해 의외로 합격하니 의아했다.

LG전자 면접은 1차, 2차로 나뉘는데 1차 면접 전에 lg사이트에 TO-DO로 할 것이 생긴다.

5장 정도로 PPT를 주제에 맞게 채워야 하는데, 첫 번째 주제는 본인이 가장 좋아하는 전공을 5개 정도로 기재하고 왜 좋아하는지를 설명한다. 두 번째 주제는 장은 진행했던 프로젝트, 마지막 주제는 자신을 어필하는 주제였다.

이것을 ppt로 준비하여 기간내에 제출하여야 한다. ppt의 디자인에는 살짝만 신경쓰고 나머지는 내용에 치중하도록 하는 것이 좋을 것 같다. 그리고 ppt에 대한 장수는 중요하지 않다. 나는 5장만 채우지 않고 한 장 더 썼다.

면접 장소와 면접 가는 길

나 같은 경우 오후 1시 정도에 면접이었는데 면접 장소는 마곡 LG사이언스 파크 이다.

지하철이 급행 9호선을 타고 가야 한다. 일반 열차를 타고 가면 급행 열차를 보내기 위해 가양역에 한참 머물러있기 때문에 예상했던 것보다 시간이 더 걸린다.

일반 열차를 타고 가면 신논현에서 마곡나루역까지 약 40분이 걸린다. 그래서 난 지각할뻔했다. 급행은 약 25분정도면 도착한다.

면접 보기 전 손 코딩

도착하게 되면 인사팀 직원이 보안 문열고 들여보내준다. 면접을 지하 1층에서 보게 되는데 면접을 보기 전에 손 코딩 문제를 풀게 되는데 그렇게 어렵진 않은 수준으로 C언어를 쭉 잘 배웠다면 풀 수 있는 정도이다.

시간은 약 40분 정도이고 대략 10문제 정도이다. 시간이 다 되면 인사팀 직원이 푼 종이를 가져간다.

면접 복장

LG전자에서 면접 복장으로 자유로운 복장으로 착용하라고 하였는데, 주변 면접자들을 보니까 죄다 정장이었다. 물론 나도 정장입고 가는 것이 마음이 편했다.

정장을 입은 비율은 10명 중 8명으로 다 정장이라고 보면 된다.

PT면접

이제 면접장으로 가면 나에 경우에는 면접관 2명이 앉아있었고 내 자리에는 노트북이 놓여있었다. 면접관의 경우 프로젝트 리더 한명, HR 사람 한명이 있었다. 면접관의 경우에는 자신에게 관심있는 면접관이 들어온다고 하고, 다른 면접자들에게 물어보니 어던 사람은 4명이 있었다고 한다. 노트북 화면에는 내가 준비했던 ppt가 켜져있었다. 이제 그 ppt를 앉아서 발표하면 된다.

중간에 영어로 자기소개하라고 하는데, 준비해온 자기 소개 영어를 하면 되는데, 중간에 면접관이 끊었다.

그리고 중간에 내가 푼 손코딩 문제로 주제가 넘어갔다. 손코딩 면에서는 칭찬을 받았다. 불길했다.

마지막으로 면접이 끝나고 면접관이 내게 악수를 요청하면서 이런 말을 남겼다.

"행운을 빌어요"

불길했다.

PT면접에서 면접관은 2명이고 면접자는 1명이며 면접은 30분이 넘게 진행되었다. 

면접 분위기

면접 분위기는 전혀 딱딱하지 않다. PT 발표도 면접관이 성의있게 잘 들어주었다. 그리고 심지에 내가 대답을 못하니 면접관 자신이 웃으면서 설명해주기도 했다.

다른 면접자의 말도 들어보니 압박하는 면접은 없었다. 면접을 편한 분위기 속에서 진행되니 안심해도 될 것 같다.

면접이 끝나면 아까 그 인사팀 직원이 보안 게이트까지 데려다준다. 내쫓는다. 그 상태로 다시 집으로 가면 된다. 면접비는 그날 주는 것이 아니라 1~2주 후 계좌로 입금이 된다.

면접장까지 가는 길

코딩 테스트가 끝난 후 2~3주가 지나게 되면 면접을 보게 된다.

이전에는 코딩 테스트에서 만점을 받으면 가산점이 있다고 했지만 2018년 내가 면접을 볼 당시에는 그런 가산점 같은게 없다고 했다. 실제로 가산점이 있는지 없는지도 모르지만, 난 있으면 좋겠다고 생각했다.

왜 냐면 난 두 개 다 맞았다고 생각했기 때문이다.

워낙에 큰 회사다보니까 면접 날짜가 각 직무마다 다르고 최대 2주간에 걸쳐 모든 사람의 면접이 끝난다. 나같은 경우 삼성 SW DS쪽으로 지원하였고, 거의 마지막에 걸려있었으니 면접을 준비하는데에는 충분한 시간이다. 결국은 나가리

나는 2018년에 면접을 봤는데 새벽 6시 30분까지 양재역으로 총집합을 한다.  사실 6시 30분인지 확실하지는 않으나 엄청 일찍 가야하는 것은 맞다.

버스는 큰 버스로 5대 정도로 가는데 도착하는 순간 담배를 못핀다. 안그래도 면접이 하루에 3개를 몰아서 하는 면접이라 체력과 정신력이 중요하다. 버스 타기 전에 5대 정도 줄담배로 니코틴 충전하도록 하자.

도착하면 건물 안에서 이름표를 나눠주고 짐을 둔다. 그리고 조를 편성한다. 이제 밖으로 나갈 수 없다.

면접은 총 3개의 면접을 보는데, 순서는 각 사람마다 로테이션을 돌기 때문에 어떤 면접을 먼저 보는지는 알 수 없다.

나 같은 경우에는 첫 번째 창의력 면접, 두 번째 인성면접, 세 번째 직무면접이었다.

창의 면접

창의력 면접에서는 용지를 나눠주고 컴퓨터 앞에 앉아 화면에 주어진 문제에 대해서 50분 동안 아이디어를 생각해 컴퓨터에 쓰고 또 용지에도 그 아이디어를 써야한다. 그리고 그 아이디어를 가지고 면접관과 소통하며 발표한다. 약간 면접이라기 보다는 아이디어를 통해서 면접관하고 이야기하는 것으로 나머지 면접 보다는 분위기가 가볍다. 문제를 공개할 수는 없지만 키워드로는 대기 오염이었다.

면접관은 3명이고 면접자 1명이다.

인성면접

인성 면접 전에는 인성검사를 시작하는데 빨리 빨리 끝내야한다. 인성 면접 보기전에 면접실 문 앞에서 대기하는데 이때가 금단 현상과 함께 긴장이 극도로 심해져 사타구니에 땀이 찬다. 많은 사람들이 인성 면접이 가장 중요하다고 하는데 바로 최종 보스(높으신 분들,임원)들이 면접을 보기 때문이다. 다른 면접관들은 현직에 종사하는 사람이 면접관으로 나오는데 아무리 그 사람들이 점수를 좋게줘도 임원들이 거르면 면접 탈락이라는 소문이 많이 나돌았다. 면접관들은 인자한 척을 하면서 긴장을 풀어준다. 하지만 난 그런게 더 무서웠다. 말 한번 잘못하니 한 숨소리가 강풍이다. 면접 시간은 약 10~15분 정도로 면접 시간이 끝나면 밖에서 직원이 시간이 다 되었다고 문을 두드린다.

나 같은 경우에 존경하는 인물이 왜 "앨런 튜링"인지 물어보았다.

많은 면접 질문에 대비했다고 생각했지만 존경하는 인물을 물어볼지는 몰랐다. 왜냐면 구라쳤기 때문이다.

가장 어이도 없고 생각치도 못한 질문은 "앨런 튜링이 어떤 업적 두 가지를 말해보세요"

당연히 모른다. 그냥 이미테이션 게임에 주인공이라는 것밖에 모른다.

면접관은 3명이고 면접자는 1명이다.

그렇게 멘탈이 개박살나면서 나는 오전에 면접 2개를 마쳤다. 오후가 되면 이제 밥을 먹는데 역시 삼성전자 밥은 너무나도 맛있다. 오후 2시~3시정도가 되면 이제 가져온 서류와 면접비를 받게 된다.

직무 면접

직무 면접 같은 경우에는 현직에 있는 사람이 면접관이다. 문제는 공개할 수 없으나 대략적인 키워드는 반도체, 정렬 알고리즘, 보안 정도이다. 3개 정도의 문제가 주어지는데 그 문제를 A4용지에 풀고 들어가서 면접관 앞에서 발표하면 된다. 문제풀이시간은 대략 40분 정도이다.

의외로 면접관과 나의 거리가 되게 좁고 심지어 나는 인사하다가 넘어질뻔했다.

그리고 앞에는 칠판이 있는데 풀어온 것을 설명할 때 이 칠판에 그림이나 글을 써서 설명할 수 있다. 나는 신나게 설명하다가 보드마카를 들고 나와버렸다.

보드마카는 놓고 오도록 하자.

직무면접의 면접관은 4명이고 면접자는 1명이다.

이제 면접이 끝나면 약 5시 정도가 되는데 그대로 양재역에 내려준다. 맨탈이 박살 난 상태에서 양재역에서 집으로 버스타고 가면 된다.

면접 결과는 약 2주후에 발표하고 난 떨어졌다.

빌드 자동화 툴 Cmake에 관한 설명과 사용법을 알아보도록 하겠습니다.

Cmake를 사용하는 이유

Cmake는 Makefile을 만들어주는 툴입니다.

Cmake를 설명하기 전에 Makefile이 무엇이냐면 빌드를 편리하게 해주는 일종의 빌드 스크립트라고 보시면 됩니다. 이 스크립트를 make명령을 사용해서 실행시키기는 겁니다.

그냥 shell파일을 이용해서 빌드를 할 수 있겠지만 Makefile을 사용하는 이유는 Incremental build의 방식을 사용하기 때문입니다.

Incremental build란?

프로젝트의 규모가 커질수록 수많은 소스 파일들이 생겨날테고,  빌드하는 시간도 오래걸리게 됩니다. 우리가 대학교에서 프로젝트하는 수준은 그냥 강아지 애교 수준이고 정말 회사에서 일하게 될 경우에는 빌드하는 것도 시간이 꽤 걸립니다.

그래서 우선 처음에는 모두 빌드를 해놓고, 그 이후 수정된 파일에 대해서는 그 소스파일과 연관된 것들만 빌드하여 시간을 줄여주는 빌드 방식이라고 생각하시면 됩니다.

이러한 편리성이 존재하지만 Make는 의존성에 관한 기술을 일일이 기재해야 되기 때문에 관리측면에서 번거롭습니다.

Cmake는 이런 귀찮은 점을 해결해주는 툴로서 Makefile 생성해내는 역할을 합니다.

간단하게 Cmake를 사용하는 방법을 알아보도록 하겠습니다.

a.c

int add(int a,int b){

    return a+b;

}

a.h

int add(int,int);

b.c

#include <stdio.h>

#include "a.h"



int main(){

    printf("%d+%d=%d\n",5,6,add(5,6));

    return 0;

}

a.c는 add라는 함수가 존재하고 단지 두 수를 더해서 결과를 return하는 함수입니다.

a.h는 a.c의 함수를 선언한 헤더파일이고 b.c는 a.h의 함수를 사용하는 실제 프로그램입니다.

이 간단한 프로그램을 빌드하는 CMakeLists.txt 작성은 단 한 줄이면 됩니다.

CMakeLists.txt

ADD_EXECUTABLE(a.out a.c b.c)

ADD_EXECUTABLE은 실행할 파일을 생성하는 명령으로 첫 번째 기재할 내용은 실행파일 이름이고 나머지는 그 실행파일을 생성하기 위한 source파일입니다.

이제 아래의 명령을 통해서 실행해보도록 합시다.

cmake CMakeLists.txt

그러면 소스파일 외에도 Cmake와 관련된 파일이 생성되는데, Makefile도 추가로 포함되었음을 알 수 있습니다.

만약 cmake가 없었다면 Makefile의 내용은 여러분들이 작성했어야하겠죠?

Cmake를 이용하면 간단하게 한 줄이면 되니까 무척이나 편리합니다.

이제 실제 make를 실행하면 우리가 만들어내고 싶은 a.out이라는 실행파일이 만들어집니다.

Cmake는 변수 선언도 가능하며 다양한 명령어가 존재합니다. 이런 명령어들은 대, 소문자를 구분하지 않지만 보편적으로 대문자를 사용합니다.

CMAKE_MINIMUM_REQUIRED()

Cmake빌드를 실행할 최소 버전을 명시합니다. 보통 맨 위에 사용하며 기재된 버전보다 낮다면 오류를 보여주고 빌드를 종료합니다.

사용법은 아래와 같습니다.

CMAKE_MINIMUM_REQUIRED( VERSION 3.4.3 )

SET() 변수 정의

SET명령어는 변수를 정의하며 다음과 같이 사용됩니다.

SET(변수명 값)

어렵지 않죠? 뿐만 아니라 List형식으로도 변수를 정의할 수도 있습니다.

SET(변수명 값1 값2 값3)

이렇게 정의된 변수는 $변수, 혹는 "{}"를 써서 ${변수}로 사용할 수 있습니다.

앞의 CMakeLists.txt를 변수를 통해 바꿔본다면 이렇게 바꿀 수 있습니다.

SET(SRC_FILES a.c b.c)

SET(BIN_NAME a.out)

ADD_EXECUTABLE(${BIN_NAME} ${SRC_FILES})

PROJECT() 프로젝트명 정의

PROJECT(프로젝트 명)으로 쓰이게 되고 프로젝트의 이름을 정해주는 명령어로 CMAKE_PROJECT_NAME이라는 변수에 저장이 됩니다.

MESSAGE() 메시지 출력

혹시 변수에 들어있는 값이라던가 오류 메시지를 표시하려면 MESSAGE라는 명령어를 사용하여 출력하면 됩니다.

MESSAGE( TYPE MESSAGE)

메시지 종류는 생략가능하며 5가지의 종류가 있습니다. STATUS가 가장 심각도가 약한 단계이고 FATAL_ERROR가 심각도가 가장 심합니다.

ADD_LIBRARY()

ADD_LIBRARY는 실행파일이 아닌 library파일을 생성할 때 쓰이는 명령입니다. 아래와 같이 쓰이게 되죠.

ADD_LIBRARY( library이름 TYPE 파일1 파일2 …)

처음에는 라이브러리 이름이 쓰이고 두번째는 라이브러리의 종류를 나타냅니다. Default로 STATIC이 쓰이며 아래와 같이 3개의 종류 중 하나를 지정할 수 있습니다.

STATIC, SHARED, MODULE

그리고 난 후에는 사용될 파일을 쭉 나열하면 됩니다.

위의 CMakeLists.txt를 수정하여 소스파일 a의 공유 라이브러리를 만든다면 아래와 같이 수정하시면 됩니다.

SET(SRC_FILES a.c)

SET(LIB_NAME a)

ADD_LIBRARY(${LIB_NAME} SHARED ${SRC_FILES})

후에 빌드하면 lib(라이브러리 이름).so 파일이 생기는 것을 확인할 수 있습니다. 

ADD_DEFINITIONS()

전처리시에 정의할 매크로를 의미합니다. 앞에 -D를 쓰고 나서 매크로명을 써야하며 #define 의 구문의 역할을 한다고 보시면 됩니다. 2가지 사용법이 있습니다. 컴파일시에 -D매크로명 옵션과 같습니다.

ADD_DEFINITIONS(-D매크로명) : 단순 define으로 매크로를 정의할때 사용합니다.

ADD_DEFINITIONS(-D매크로명=값) : 매크로에 값을 집어넣습니다.

INCLUDE_DIRECTORIES()

#include에서 사용할 디렉토리를 명시합니다. 만약 inc 디렉토리에 헤더파일이 존재하는 경우 아래와 같이 사용하면 됩니다.

INCLUDE_DIRECTORIES(inc)

이상 간단하게 CMake의 개념과 사용법을 알아보았습니다. 다음에는 더 심도있게 알아보도록 하겠습니다.