근진이의 알고리즘 시간

하반기에 공채 안했고, 이제 공채 안한단 썰이있어 쓸모없을 후기지만 상반기 경험을 기록해보겠따.

인적성은 인프라 직군을 지원했기 때문에 기사스타일의 시험을 봤다.

온라인으로 객관심을 시험보고, 난이도는 높지 않으나 다소 지엽적인 편이고, 

메모장과 종이를 사용할 수 없기에 계산문제에서 암산을 좀 필요로 했다.

과목은 운영체제, 네트워크, 디비,  정보보호, WAS 

개발직군은 코테 봣다고한다.

1차 기술면접은 꽤 후덜덜 했다. 5:7(면접자:면접관)이었고,  같은 팀에 중고신입이 두 명있었는데, 둘이 한 프로젝트가 꽤 괜찮았다.

난 병풍처럼 있다가 왔는데, 자소서 보니깐 개발직군을 쓰지 왜 인프라를 썼냐고 혼났다.

면접장에서 혼나보긴 첨이라 당황 =_=

도커를 사용해본 경험이랑 마지막 한마디에 긴장해서 제대로 말못했다., 원래 이런 사람 아니다 이 두 마디가 제일 컸던것 같다.

PT면접은 모르는 주제였으면 꽤 곤란할 뻔했다.

회사내에 ~한 상황있고 A,B 두 안이 있는데

어떤게 타당한가?

하고 수치랑 문제상황에 대해 자세히 줬고 커다란 포스트잇에 작성했다.

30분 준비 8분발표 7분 질의응답.  A,B안 중에 하나 고르는 것이지만, 내 생각에 제일 좋은 답은

A를 기각하고 B안의 일부만 적용+문제내에 있는 힌트(Cache 서버)를 적용해서 답하는 것이었기에 대답했고

꽤 좋은 평가와 호응을 얻었다.

기술면접을 거진 병풍수준으로 있다가 와서 개 조졌다고 생각했는데 뜬금었이 합격했다고 해서 얼떨떨하게 면접갔다.

같은 면접조의 중고들은 떨어졌다.

최종면접은 다음번에.

작년이었나 재작년 까지만해도 1, 2차 나눠서 보았다는 것 같은데

이젠 한번에 끝을 내는 모양이다.

보안서약서를 쓴 관계로 내용을 여기에 쓰진 못하겠지만,

SK C&C에  갔다온 걸 느낌만 말하면,

취준생을 위해 정말 노력을 많이 하는게 보인다는것 정도 쓰고 말하고 싶다.

인사팀 직원들은 인솔할 때를 제외하곤 보통 방관자이기 마련인데,

면접 대기소에서 계속 긴장을 풀어주려하고, 궁금한것에 대해 성심것 답변해주려고 노력했다.

면접도 깊이 파고들기는 한다만,

공격적인 어조로 진행되진  않았다.

내가 대답을 잘 못해서 그렇지...

회사에서 뭔가 긍정적이고 밝은 느낌이 강했기 때문에 면접을 보고나니 SK에 정말 가고 싶어졌다.

근래 출제된 삼성 문제의 특징 중 하나는, 대단한 알고리즘을 요구하는 것보다도

독해력을 많이 보는 것이 아닐까 한다.

아기상어는 std::priority_queue가 사용가능하다면 금방 풀수 있고

나무재테크는 알고리즘이랄게 아예 없다.

다만 둘다 문장 하나하나에 조건이 조그마하게 숨어있어서 처음 문제 파악할 떄

제대로 읽지않는다면 낭패를 보거나 풀이 자체가 불가능하다.

예를 들어, 나무재테크 문제는 이동방향이 대각선 포함 8방향이다.

처음에 문제를 제대로 안읽으면 4방향이라 어림짐작하고 덤비기 쉽상이다.

일단 돌아와서 문제의 포인트는 정렬, 그리고 문제를 봄,여름,가을,겨울에서 봄+여름,가을,겨울 로 나눠 생각하는거다.

또 최초영양분이 모든칸에서 5라는 사실을 잊어선 안된다.

죽음과 삶이란 상태가 있는것 처럼 보이지만 그렇지 않다.

사실상 봄에 나이먹는과정+양분 부족해서 시체로 만드는과정을 합친게 한 칸에서 한번에 이루어지기 떄문이다.

자료구조는 vector들의 2차원배열 vector<int> land[11][11]->  land[r][c]->(r,c)는 나무 나이 벡터로 충분해보인다.

그러므로 봄이 시작하기전에

1. 나이순으로 정렬을 하고

2. 나이를 먹이면서 영양을 빼고(나이먹은 나무는 따로 aging벡터에 저장한다)

3. 영양이 부족하면 나이/2를 시체로 만든다.

4. 백업해둔 aging벡터로 기존 나이를  덮는다.

가을 겨울은 너무 쉬워서 패스. 

시간초과가 많이난다는 평이 있는데, 개인적으론 시뮬레이션 문제는 정말 특이한 경우가 아니면  C++로 푸는게 좋다고 본다.

Python list 만큼은 아니지만 STL만 해도 알고리즘구현하는데 충분한 유연성을 제공해줄수있고,

로직이 다소 개판이어도 빠른 성능으로 커버할 수 있다.

조지아는 알려졌다면 알려졌고 그렇지 않다면 그렇지 않지만, 한국사람 엄청나게 많고, 볼것도 꽤 있었다.

LG한테 두들겨 맞은 데미지를 회복하기도 전에 다음날 바로 시험보러갔다.

8:40분까지 한성대에 입실하라고했는데, 결시가 다소 많았다. 한투(?) 신한카드랑 겹치는 사람들이 많은 것같다.

SKCT를 본 분들은 9:10 까지 오라고 했던 것 같은데, C&C는 8:40분 넘어가니까 건물 입장을 금지시켰다.

2019년 상반기 수시채용 때 코딩 테스트를  했다더니, 이번에도 코딩테스트였다.

프로그래머스로 알고리즘 3문제가 나왔고, SQL 한문제 나왔다.

SQL은 단순 JOIN문제였지만, 중복된 열이 나와서 잘 제거해 줘야했다.

전반적으로 3문제다 어렵진 않았는데, 문제는 테스트케이스가 엄청나게 커서

효율성에서 갈릴 것이란 생각이 들었다. 

Python in 키워드로 리스트를 검색하는게  O(N)인데, 리스트 자체가 10만 정도까지가 범위였다.

아예 못푼 사람은 거의 없을 것 같고, 아마 시간초과를 누가 덜났냐 싸움일 것 같다. 물론 난 자신없다. ㅋㅋ 스크도 기대안한다.

단톡방에서들어보니, 데이터분석은 프로그래머스에서 쥬피터로 했다고하고

인프라 직군은 코딩테스트를 SW랑 다른 문제로 두 문제만 봤다고 한다.

팩토리얼 얘기나오는거보니 간단한 동적계획법 문제였던듯?

간식은 얘네가 엄청나게 잘줬다. LG는 닥터유 초코바+무슨 비싸 보이는 생수+비타민워터였는데,

SK는 작은 상자에다가 수입과자들을 가득 채워줬다. 심지어 인성검사랑 코딩테스트 보는중에 먹을 수도 있었다.

생각보다 글이 핫해서 추가.

코테는 조합 한 문제, 순열(또는 정렬) 한 문제, 브루트포스 한 문제 나왔다.

=============================================================================

2019.10.21. 13:30

코딩테스트에 합격했다. 이제 면접을 준비해야지.

인프라직군은 거의 안뽑았다. 오카방에 살아남은 자가 없다...

LG, SK, 국은 서류합격의 기쁨도 잠시, 곧 이어서 인적성의 쓴맛을 보러갔다왔다.

국민은행, LG(CNS, 유플러스)가 겹쳐서 LG를 선택했다.

토요일이 빅매치였는데, LG, 국민은행, KT가 같은 날 같은 시간이었다.

나도 LG랑 국은중 하나를 골라야했는데, 아쉽게도 NCS를 공부해놓은게 없어서 빠르게 포기하고 LG를 봤다 ㅠ

오픈톡방에 들리는 말을 보니, 유플러스와 KT가 결시가 꽤 많았다고 한다. 눈치게임의 승자는 KT...

10월 12일 LG

무려 11:45분 안내방송 시작부터 시험종료 5:20분까지 붙잡혀있었다.

LG CNS와 전자는 각기 테스트가 따로 더 있기 때문에 그렇고, 유플러스 같은데는 4시 20분정도에 끝났다.

전반적으로 난이도가 높았다. 시중의 문제집은 소용이없었다. ㅋㅋㅋㅋ

그나마 위포트께 좀 유형이 비슷했던것 같다.

CNS만의 인적성 중에 ITQ테스트란게 있었는데 정보가 거의 없었다.

쉽게 말하면 순열, 조합, 확통이 섞여나오고, 점화식 증명에서 틀린부분 찾기, 알고리즘과 순서도 같은게 나왔다.

난 틀딱이라 알고리즘과 순서도란게 모의고사, 수능에 꼭 한문제씩 나오던거라 걱정없었지만, 요즘은 또 안배운다나 그랬던것같다.

인성문항은 도전, 인화 위주의 키워드가 굉장히 많았다. 이거 너무 편향되게 찍은것 같아 걱정이다.

크게 기대 안한다 ㅋㅋ

============================================

2019.10.21 17:00

유플러스는 탈락ㅜㅜ

유플 떨어졌는데 CNS가 붙을리가 없지.

기대하지말고 있어야겠다.

============================================

2019.10.22 17:00

CNS도 탈락

상반기엔 전자도 탈락했는데... LG는 나랑 아닌것 같다.

원래 예전에 풀었던 문제들 중에 오답률 높은 것, 기억에 남는 것 위주로 포스팅하고 요즘 풀고있는 문제들을 올리려 하였으나

이건 풀다가 승질이 뻗쳐서 먼저 정리한다.

익은 토마토(1)은 주변 4방향으로 전파가 되고 안익은 0을 1로 바꿀 수 있다.

그리고 -1은 비어있는 토마토 이기 때문에 미로에서의 벽과 같은 역할을 한다.

다시말해 그냥 미로찾기 문제고, "모든 곳이 다 익었는지"는 모든 미로를 전부 탐험했는지랑 같다.

다음과 같은 과정을 거쳐야한다.

1. 모든 위치를 방문해야하고(방문해야 토마토가 익은 거니까)

2. 방문하고 났으면 얼마만에 방문한건지(며칠만에 익은건지 확인하기 위해서)

3. 가장 마지막에 방문한 노드의 방문 순서가 계산가능한 최소 시간이다.

즉 BFS를 이용하여 최단 경로를 계산하는 문제라고 생각했다만...

낮은 정답률에서 알 수 있듯이 문제는 그게 아니다.

일단 방문 할 수 없는 위치가 존재 할 수도있다.

위와 같은 경우 외곽의 토마토는 우상단의 토마토를 통해 다 익을 수 있지만

좌상단의 토마토는 가까운 익은 토마토가 위치 할 수 없어 모든 토마토가 익지 않게된다.

.... 정도면 쉬운 문제였을 거고,

해결해야 하는 경우가 더 통수의 통수의 통수가 있다.

시작 위치가 여러개인 경우인데,

map상에서 익은 토마토가 map[0][0]과 map[3][5]에 있으니

map[1][0]과 map[3][4] 는 둘다 1이어야 하지만 섣불리 탐색을 시작하면 둘 중 한개는 1이아니라 10이 되어 버린다.

이런 반례가 있을 거라곤 예제에서 주지 않았더라면 상상도 못 했을거다. 

말로는 양쪽에서 동시에 출발하면된다고 하지만 어떻게 할지는 생각해내는데 꽤 오랜 시간이 걸렸다.

답은 의외로 간단했는데, 그냥 1(익은 토마토)의 위치를 BFS 돌리기전에 전부 큐에다가 넣어 놓는 것이었다.

그럼 BFS가 운영하는 큐는 아주 손쉽게 양쪽의 시작위치를 번갈아가면서 큐에다가 값을 넣고 탐색하기 때문에 쉽게 해결이 가능했다.

이거 생각 해내는데 한시간이 넘게 걸렸다.

좀더 문제를 바라보는 눈을 키워야겠다.

이유는 알 수 없지만 진법 변환하는 쉬운 문제임에도 정답율이 매우 낮다.

통계를 보니 시간초과로 틀린 분들이 많은 걸 알 수있었다.

그 말은 즉 통상적인 방법인,

1. 나눈다.

2. 나머지를 모은다.

3. 뒤집는다.

로는 어려울 수 있다는 뜻이다.

그래서 조금 다르게 풀었다.

8진수를 2진수로 각 자리를 변환하면 0~7까지 000, 001, 010, 011, 100, 101, 111로 표현 할 수 있다.

저걸 배열에 저장해서 입력된 문자열의 각 자리를 그대로 인덱스로 사용해서 꺼내오면 된다.

유사 코드로 작성하면, 다음과 같다.

=========================

oct2bin[] = {000, 001, 010, 011, 100, 101, 111}

cin>>oct

// 앞자리는 1로만 시작해야함

if oct[0] ==3 or 2 then print(oct2bin[oct[0]-'0'][1]) print(oct2bin[oct[0]-'0'][2])

if oct[1] == 1 then print(oct2bin[oct[0]-'0'][2])

loop : oct i 1->len

start

print(oct2bin[oct[i]-'0'])

end

print("\n")

=========================

단, C++기준으로 매번 cout을 하면 퍼포먼스가 떨어지므로 stringstream에 모아서 나중에 한번에 출력한다.

두 가지 모두 해봤는데, 매번 cout을 하는 것보다 stringstream으로 한번에 출력하는 것은 메모리를 1.5배정도 더 썼다.

하지만 속도는 1/1.5 배였다.

끝으로 문제에 함정 카드가 하나 있긴한데, 그건 소스코드 보시면서 확인해보시거나, 직접 한번 생각 해보시는 것도 좋을 것 같다.

그것 때매 한번 틀리고 고민좀 했었다.