초보와 고수사이 넘사벽 중간쯤

그 동안 삼성 SW 직군 시험 공부를 위해서 책을 사보거나 유료 강좌를 많이 들으시기도 하고

여러 Online Judge 사이트에서 공부하셨을텐데 너무 수준이 높아서 도움이 안되거나 좌절하신 분들도 있는데

수능에는 EBS 강의 처럼 삼성에서 비슷한 수준의 문제의 Online Judge 시스템과 강의를 일반인들에게 공개하였습니다.

역량 테스트를 목표로 하시는 분들은 하루에 한문제씩만 풀어봐도 좋을 결과가 있을것 같습니다.

강의도 있으니 따로 책을 사보실 필요가 없고 커뮤니티도 있으니 문의하면 메토링도 받을 수 있을 것 같습니다.

https://www.swexpertacademy.com

#삼성_소프트웨어_역량_테스트

그 동안 회사일이 바빠서 글을 못썼습니다.

일단 최근 시험이 오전 오후 2문제씩 4문제였는데 지난번에 2문제만 살펴봤고

오늘 나머지 2문제 중 1개를 생각해 보겠습니다.

시험을 보신분 들이 이 글을 보실것 같지는 않은데 재수?나 다음 시험을 준비하시는 분은

꼭 기출문제를 구해보세요. 모든 시험의 기본은 기출문제입니다.

남은 2문제 중 바이러스 관련 문제가 있었지요?

이 문제는 전형적인 BFS문제 였습니다.

바이러스를 시작점으로 BFS를 돌려서 더 이상 갈 수 없는 때 까지 돌리면 되고

바이러스가 복수 개이니 각각 돌리면 되는 문제입니다.

하지만 이 문제는 벽을 쌓을 수 있으니 그 벽의 위치에 따라 바이러스가 퍼질 수 있는

범위가 달라지게 됩니다.

여기서 많이 실수를 하는 것이 현재의 바이러스 위치를 보고 벽을 쌓을려고 하면 너무 어려운 문제가 됩니다.

판의 크기가 최대 8x8 인것도 그렇게 하지 않아도 된다는 것을 알려주는 것입니다.

현재의 바이러스 갯수나 벽의 위치에 따라 달라지겠지만

(8x8)C3 = 약 4만가지경우, 각 위치에서 벽을 쌓을 위치를 3개를 고르고 (조합이겠지요?)

그 경우에 각각 BFS로 바이러스를 퍼뜨려서 보고 남은 위치가 가장 많은 것이 답입니다.

바이러스 위치에 따라 바둑두는 것 처럼 벽을 쌓아 보려고 하면 너무 어렵게 접근하는 하는 것입니다.

일단 위처럼 풀고 시간 초과가 되면 Memoization을 이용하여 시간을 줄이는 방법을 생각하면 됩니다.

여러가지 아이디어가 생각이 나지만 이 시험은 이렇게만 해도 Pass가 되었을 것입니다.

#삼성_소프트웨어_역량_테스트

지난주 시험 잘 보신 분들은 면접이 있지요?

기사 보니 코어 과목 위주로 질문은 한다고 한다던데

컴퓨터 구조, OS, 소프트웨어 공학, 네트워크, DB 이런 것일텐데

그냥 읽어보지 말고 물어볼만한 것을 찍어서 적어 놓고 반복해서 읽어보는 것이 중요합니다.

그리고 답변할때 ~ 하는 것 이라고 하지 말고 ~ 하는 시스템, ~ 하는 알고리즘, ~ 하는 방법

이렇게 답변하는 것이 좀 더 좋습니다.

지난주 시험 4문제 중 보험설명 문제가 있었지요?

문제는 찾아서 보세요.

예전에 2차원 문제 설명할때 겹치는 도형 설명한것 기억 나시나요?

그것과 유사하게 풀면 되는데

1. 먼저 최대 설명 건 수 가 N 이라고 하면 NCN 부터 NC1 까지 모든 경우를 찾은 후에

2. 겹치지 않는 것을 구하고

3. 겹치지 않는 것에 대해 건당 보수를 더 해서 가장 큰 것이 답이었지요.

여기서  2. 겹치지 않는 것을 구하는 방법이 예전에

2차원 상에서 여러 사각형의 겹치게 그리고 그 넓이는 구하는 것이 있었지요?

그때 원래는 플레인 스위핑이라는 알고리즘을 쓰는 것인데 사각형의 면적이 작으면

사각형의 내부를 1씩 채우고 그 수를 세면 된다고 했는데

이 문제가 그것과 아주 유사합니다.

1. 에서 구한 모든 조합의 경우에서 각 경우를 1씩 채워 보면 겹치는 것을 쉽게 알 수 있습니다.

플레인 스위핑 처럼 수식으로 하면 기간이 아무리 길어도 같은 시간에 결과가 나오지만

이렇게 채우는 것은 기간이 길면 길수록 채우는 시간이 많아지기 때문에 시간이 많이 걸리나

이 문제 처럼 짧은 기간에 대한 것은 쉽게 풀 수 있습니다.

이 문제가 조금 더 어렵게 나오려면 하루에 2건을 처리 할 수 있다 라고 하면 채울때 2까지는

허용하면 쉽게 문제가 풀리게 됩니다. 이때는 오히려 플레인 스위핑 방법이 더 어려울 수 도 있습니다.

완전탐색인데 겹치는 것을 구하는 팁만 알면 쉽게 구할 수 있는 문제였습니다.

#삼성_소프트웨어_역량_테스트

지난주 일요일 4월 16일이 S사 시험이었지요?

시험을 다들 잘 보셨나요? 재수?를 하지 않으면 1번만 보는 시험이니 시험을 보시고 나면 다시 이걸 보실 필요는 없을 것 같기는 하지만 하반기도 있으니 기출 문제는 잘 정리를 해두어야지요.

모든 시험의 기본은 기출문제이니 기출문제를 잘 찾아보세요.

구글과 네이버에서 검색하면서 날짜를 조정을 잘하면 쉽게 찾아 보실 수 도 있습니다. 잘 정리된 곳도 있구요.

이게 그룹공채는 없어진다고 하고 회사별로 수시로 본다고 하는데 그러면 여러번 보시는 분들도 생길 것 같습니다.

시험 바뀐지 얼마 안되었기 때문에 쉽게 바뀔 것 같지 않고 회사에 안에서 화이트 보드에 알고리즘을 물어볼 수 있는

분을 모든 응시생에게 붙일 수 도 없고

몇개의 후기를 봤는데 이번 시험 후기를 보면서 알게 된 것이 아래와 같습니다.

1) STL 라이브러리를 사용할 수 있다.

   STL를 쓰게되면 기본 코드를 외울 필요가 없고 사용법만 익히면 됩니다.

2) 1번과 2번 문제의 구분이 없어졌다.

    지난번 까지는 1번은 간단한 게임류 2번은 알고리즘에 가까운 문제 였는데 이번 시험에는

    모두 예전 2번과 같은 형태의 문제였습니다.

3) 대부분 최대/최소 문제였지요. 경우의 수도 완전탐색으로 풀수 있을 정도였구요.

    DP로 풀었다고 된 것도 그냥 완전 탐색으로 풀 수 있을 것이지만 간단한 DP까지는

    공부해 두는 것이 좋습니다. 너무 명확하나 것을 완전탐색으로 풀면 시간도 많이 걸리고

4) 작년 후기에는 잘?본사람은 나중에 다시 불러서 한번 더 보게 한다고 합니다.

    (더 어려운 문제인가요?)

후기는 구글과 네이버에서 날짜를 잘 맞추면서 찾으면 쉽게 찾을 수 있습니다. 잘 정리된 곳도 있고요.

그 중 문제 하나를 생각해보면 오전인지 오후였는지 모르곘는데 여기에 자세히 쓸 수 는 없지만 찾아서 풀어보시고 나서

아래는 읽어보세요.

후기중에 2차원 배열중에서 4개의 면이 이어진 도형이 차지하는 부분의 숫자 합의 최대값을 물어본 것이 있었는데.

접근하는 생각의 흐름이 이럴 수 있을 것 같습니다. 

1) 큰 숫자들이 모여있는 곳을 찾아서 큰 숫자들을 연결하여 이어진 도형이면 그것을 답으로 하자

    > 사람이라면 보통 이렇게 하겠죠, 전체 숫자들을 보고 큰 수들을 이어보고 모두 연결되어 있으면 선택하 수 있습니다.

       그것이 최대값인지는 알 수 없는 것이지요.

2) 전체 탐색을 해야 한다면 (NxM)C4를 뽑아서 뽑힌 4개가 서로 연결되어 있는지 확인하고 연결되어 있으면 4개의 좌표

     에 해당하는 수를 더해서 가장 큰값을 구함

     이 경우 NxM 이 작은 수이면 가능합니다. 또한 서로 연결되어 있는지에 대한 판단방법은 생각해 봐야 겠지요.

3) 4개가 붙어 있는 테트리스 같은 모양을 미리 구해 놓고 그 도형을 모든 지점에 놓아 보고 값을 구해 최대값을 구함

   주의 할 것은 도형의 모양이 0도 90도 180도 270도 돌린 것 처럼 4배가 나오는 것이 있기도 하고

   어떤 것은 돌릴 필요가 없는 것도 있고 90 돌린 것도 있는데 이렇게 어려가지를 생각할 수 있도 있지만

   경우의 수를 구하는 것이 아니라 최대값을 구하는 것이므로 모든 도형을 0 90 180 270 도 돌린다고 생각하면 더 쉬울 수 도 있고

   미리 돌린 모든 좌표의 경우를 구한 테이블을 움직이면 쉽게 구할 수 있음

4) 이런 종류의 문제는 NxM 배열을 잡는 것 보다 (N+4)x(M+4) 배열을 잡는 것이 더 쉽게 풀릴 수 있습니다.

    NxM 밖의 부분은 -1000 씩 채워두고

이 문제는 STL 같은 라이브러리 도움을 받거나 기본 코드도 필요없는 앞에서 했던 2차원 배열의 완전탐색의 변형으로 볼 수 있을 것 같습니다.

#삼성_소프트웨어_역량_테스트

이번 주 일요일이 역량 테스트 시험이지요?

시험대비 겸 리마인드 하려고 글을 씁니다.

당연히 준비를 많이 하셨겠지만 학교 과제등으로 못했다면

1. 아직도 안늦었습니다. 1편 글의 올림피아드 사이트의 강의를 들어보세요.

    편 당길지 않으니 이런 시험에 익숙하지 않는 분은 꼭 해보세요.

2. 글 중에 있는데 온라인 저지 사이트에 가서 쉬운 문제라도 풀어보세요.

    온라인 저지 사이트에 익숙해져야 합니다.

3. 입력변수의 개수가 중요합니다. 완전탐색으로 될 만한 것인지 확인 후

    가능하면 완전탐색 아니면 DP등으로 풀어야 하는데 꼭 DP로 풀어야 하는

    문제는 나오면 맞추는 분이 많이 없을 거에요.

4. 부분점수가 있다는 것을 명심하고 포기하지 마세요.

    맞춘 TC의 갯술로 점수를 줄 수 있고 다 못맞추었는데도 합격했다는 후기도 있습니다.

5. 2문제 중 차례로 풀어야 하는지 쉬운것 부터 풀어도 되는지 확인하세요.

    어떤 때는 1번을 풀어야 2번을 풀 수 있다고 했던 적도 있다는데 아닌 경우도 있으니

    꼭 1번 부터 풀려고 하지 마세요.

6. 4.번에 해당하는 것인데 최대 갯수는? 백지?로 내지 말고 이런 문제가 있으면 객관식 처럼

    무조건 가능성이 있는 아무 숫자나 찍어보세요. 부분점수가 있으니 재수 좋으면 TC중

    몇개는 맞을 거에요.

7. DFS, BFS, 순열/조합, 코드는 지금 부터 하루에 몇번씩 쳐보세요.

   특히 DFS는 아주 유용하게 쓰입니다. 하지만 어떻게 쓰는지 모르고 외우기만 하면 아무 소용 없으니

   DFS로 되는 문제는 몇개 찾아서 풀어봐야죠.

8. 고등학교 확률 통계 바로 전에 나오는 경우의 수를 한번 찾아 보세요.

    위 3번 계산에 도움이 됩니다. 그리고 순열로 풀어야 하는지 조합으로 풀어야 하는지 도움이 됩니다.

9. 끝까지 남아계세요. 가끔 문제나 TC 정정이 있을 수 있습니다. 힌트를 더 줄 수 도 있고

10. 최대값/최소값이면 무조건 완전탐색으로 보시고 ~ 이상/~ 이하로 나오면 그리드로 볼 수 도 있지만

    그리드 알고리즘이 더 어려워요.

11. 같은 완전 탐색이라도 순서를 보세요. 1~10개 까지 최대값을 찾는데 1부터 해보면 안되겠지요?

     최대값이면 큰 것 부터 해봐야 합니다. 10P10... 10P9...  10P1 이런식으로

12. 종이를 잘 활용하세요. 일단 그림을 그려보는 것이 가장 좋습니다. 그래서 종이를 주는 것이고

13. 미리 공지가 없었으면 C의 경우 stdio.h 만 있다고 생각하세요. STL 라이브러리에 의존해다가 가서 못쓰면 맨붕

14. 움직임이 있는 경우를 구할때 수식으로 표현되는지 확인하세요.

      예를 들어 어떤 물체가 1초이 1칸씩 이동하여 좌우 벽에 튕긴다고 할때 한번씩 해볼 것이 아니라 수식으로 몇초후의

      위치를 안다면 답은 아주 빨리 나옵니다.   

15. 코드의 빼대는 있고 알고리즘을 넣어 채우는 부분이 있을거에요.  #include... 부터 치실 필요가 없어요.

16. 일찍 가세요. 늦으면 택시타고도 못들어갈 수 있고 입장이 안됩니다. 

17. 시험이라 모든 나올 수 있겠지만 보통 특정 알고리즘이나 데이터 구조를 몰라도 풀수 있는 문제가 나옵니다.

    구조체, 포인터 이런것 모르고 배열만 알아도 풀수 있는 경우가 많아요.   

18. SW 과제등을 많이 해보신 분은 1번에 집중, 알고리즘을 좀 공부하신 분은 2번에 집중하세요.

     물론 둘다 풀어야 하겠지만

제 주위에 시험 보는 사람도 없는데 괜히 제가 떨리네요..

시험 잘 보시고 도움이 되셧으면 댓글 남겨주세요.

#삼성_소프트웨어_역량_테스트

일상에서 많이 보던것과 연관시킬 수 있는 문제가 뭐가 있을까를 자주 생각하는데

생각난 것이 "워드크로스", 우리 말로 "십자말"입니다.

https://ko.wikipedia.org/wiki/%EC%8B%AD%EC%9E%90%EB%A7%90

실제 십자말을 맞추는 것이 아니고

입력으로는

1) 십자말의 칸의 번호와 위치

 예를 편의상 1~10까지는 세로 11부터 20까지는 세로라고 했을때

 1번은 0,0, 0,3

 .....

 이런 식으로 빈칸의 위치를 알려주고

2) 정답인 십자말의 답들을 주고

   위스키, 백과사전..... 등을 알려주면

출력으로 정답을 쓰는 것입니다.

1) 어느 번호에 어느 단어

   #1 위키백과

   ......

DFS로 풀면 될 것 같은데 하실 수 있으시겠어요?

먼저 세로와 가로가 교차하는 점을 찾아 별도의 배열에 넣는 것이 먼저되어야 할 거 같습니다.

실제 문제를 드리지 못하니 도움이 될까 싶지만 이런 문제가 나오면 어떻게 풀어야지

하고 생각하는 것도 도움이 될 것 같아서 써봤습니다.

#삼성_소프트웨어_역량_테스트

한동안 글을 안썼더니 머리에 고인 것이 있어서 연속해서 써봅니다.

길찾기 문제 많이 보셨지요?

10x10 배열에 중간 중간에 숫자가 있고

S에서 시작 E에서 끝날때 최대값은?

이동은 아래와 우측 방향 밖에 움직일 수 없음

S000000600

0007000000

0000004000

0900000000

0000000800

0000100000

0900040000

0000000000

0003000000

000000070E

이것을 푸는 방법은 어떤 것이 있을까요?

정말 알고리즘을 배우지 않은 사람은 눈으로 봐서 어떻게 하든 큰값을 연결하려고 합니다.

사람은 보통 그리디 방법으로 생각하지요.

직관이 그런것 같기도 하지만 바둑에서 수 읽기를 한다고 하니 어느 정도는 탐색을 하는 것 같고

일단 사람이 하는 방법은 항상은 최선의 방법이라는 보장은 없습니다.

우리가 배운 DFS, BFS, 중복조합 그리고 DP가 있을 수 있을 것 같습니다.

여기의 DP는 정말 간단한 기초 중에 기초이니 여기까지는 해보세요.

(정말 한 문제를 여러가지 방법으로 풀어보세요.)

그리고 중복조합을 특별히 이야기 하는 것은 모든 조합을 다 구하고 빼는 것이 훨씬 더 쉽기 때문입니다.

위의 경우 이동은 18번 (9+9) 이므로

우측과 하측츨 섞어서 9번씩만 조합으로 뽑기가 쉽지 않습니다. 

차라리 아래처럼 많이 뽑은 후에 고르는 것이 훨씬 쉽습니다.

00000 00000 00000 000 > 11111 11111 11111 111 까지 선택할 수 있는데

이 경로는 아래와 우측을 9개씩만 선택해야 하기 때문에 갯수를 세서 0이 9개가 아니면 경로 계산을 하지 않으면 됩니다.

시작에서 0은 좌측 1은 아래로 경우의 수가 시키는 대로만 따라가면서 점수를 더하여 최대의 값이 답이 됩니다.

물론 DP가 비교도 할 수 없게 빠르고 보통 DFS로 풀지만

고등학교때 수학처럼 푸는 방법은 다양하고 하다 보면 점점 좋은 방법을 생각할 수 있는 것 같습니다.

이렇게 쉬운 문제를 묻지는 않겠지만 문제를 보면 다양한 방법으로 생각해 보시라고 써봤습니다.

#삼성_소프트웨어_역량_테스트

1. 많이 써서 했던 말인지 아닌지도 헤갈리는데 했다면 한번 더 했다고 생각하세요.

쉬운 온라인 시험에서는 완전탐색으로 풀라고 했는데

다 완전 탐색으로 풀 수 있다고 한 것은 아닙니다.

O(n^3) 처럼 표시된 Big-O Notation 도 좋은데

완전 탐색이라면 순열/조합등의 경우를 따져서 100만가지 정도 나온다면

완전 탐색으로 할만하고 그 이상이면 분명 다른 방법을 물어보고 있는 것입니다.

한가지 100만가지가 넘더라도 가지치기가 되어서 빨리 경우의 수가 줄어든다면

완전 탐색으로도 해볼만 합니다.

제가 한달도 전 쯤에 툭쳐도 완전탐색은 코드는 나와야 한다고 했는데 거기까지는 하신 것이지요?

이게 그 때가서 해야지 하면 절대 안됩니다.

매일 매일 외워서 5분안에 치는 연습을 하고 나머지 시간에는 생각을 하는데 써야지

코드를 치는데 30분 걸리면 생각할 시간이 없어서 계속 조바심 나서 붙을 사람도 떨어집니다.

(중복)순열/(중복)조합/DFS/BFS

2. 온라인 시험은 제출횟수가 있어서 제출한 것 중 가장 잘한 것을 채점하는 것이 아니라

마지막 것을 채점하니 제출할때 마다 복사해 두세요. 제출한 것을 부르는 기능이 있는지 없는지 모르겠네요.

3. PC에서 실행 시키면 DOS창으로 결과가 나오는데 값이 크면 선이 넘어서 잘 안보이는 경우가 있는데

이럴때는 도스창에서 실행시키고 test.exe > test.txt 이런식으로 파이프 라인을 쓰고

test.txt를 열면 결과를 작은 창에서 보지 않고 넓게도 볼 수 있습니다.

4. 조건의 조합을 다 해봐야 합니다.

TC를 다 보여주지 않습니다. 값이 일부만 맞으면 빼먹은 조건이 있을 수 있으니 여러 가지를 해봐야 합니다.

a조건의 가장 작은 값, 큰 값

b조건의 가장 작은 값, 큰 값

a조건의 가장 작은 값과 b조건의 가장 큰 값

a조건의 가장 큰 값과 b조건의 가장 작은 값

최소한 위의 것은 TC를 만들어 해보야 합니다.

#삼성_소프트웨어_역량_테스트

요즘 아이들과 포켓몬Go를 하는데

이 게임과 알고리즘 문제를 어떻게 합쳐볼까 고민하다가 아래와 같이 생각해 봤습니다.

1) 지도상(보통 2차원 격자, 1간 이동에 1분 소요)에 여러 포켓몬의 위치, 해당 포켓몬의 CP, 사라지는 시간을 알고 있을때,

    얻을 수 있는 포켓폰의 CP의 최대합은 얼마인가?

    (포켓몬 잡는 시간은 무시)

    일반적인 TSP 문제 ( https://en.wikipedia.org/wiki/Travelling_salesman_problem ) 와 유사하지만

    도달 할 때 이미 포켓몬이 없어지는 경우가 있으니 그것도 고려해야 합니다.

2) 지도 포켓스탑이 위치가 나와 있고 한번 돌리면 5분마다 다시 활성화가 된다고 할때

    지도상의 어느 경로로 돌아야 포켓스탑을 가장 효율적으로 사용할 수 있는가?

    (1시간 동안 포켓스탑 노가다를 한다고 가정)

이런 종류의 문제를 만들 수 있을 것 같습니다.

저도 실제 문제로 만들거나 풀어본 것은 아니지만 충분히 문제로 만들 수 있을 것 같습니다.

게임만 하지 마시고 이런 게임을 어떻게 만들 수 있을까? 아니면 어떤 알고리즘과 연결될 수 있을까?

를 생각해 보면 나중에 비슷한 문제를 만났을때 당황하지 않을 것 같습니다.

#삼성_소프트웨어_역량_테스트

오늘은 출근을 하면서 어떤 문제가 S사 역량 테스트 1번 유형으로 나올 수 있을까를 생각해봤습니다.

기출 문제가 예전 도스시절이나 혹은 그 이전의 게임 형태였었습니다.

그래서 생각한 것이 포트리스입니다.

기억하시는 분들이 있는지 모르겠는데

대포를 쏴서 서로 잡는 게임인데 각도와 초기 속도를 조절하여 적을 맞추는 것입니다.

1) 옆에서 보는 모습으로 구현

대포는 항상 포물선 운동을 하고 있어 2개정도의 상수만 결정해 주면 경로가 나오게 됩니다.

나와 적, 혹은 나와 목표물을 직선으로 표시하고

대포의 경로가 직선을 지나가면 폭파시키는 것이고 지나가지 못하면 불발입니다.

(두 점사이로 포물선이 지나가는 것 계산할 수 있으시죠? 예전 수학시간에 배운 것인데)

입력변수로 위의 상수를 번갈아 주면

출력값으로 폭파 여부를 출력

(그래픽은 생략)

예전에 공학용 계산기 EL9300에서 제공하는 (유사)베이직 프로그램으로 짜서 수업시간에 놀았던 것이 기억나네요.

2) 위에서 보는 모습으로 구현

2차원 평면에 사각형으로 나와 적의 탱크들이 4각형으로 표시되고

입력 변수로 후방에서 쏜 포의 떨어지는 x,y 좌표와 범위

출력값으로 쏘았을때 마다 남아 있는 탱크와 피해량

떨어진 대포의 유효 범위를 4각형, 마름모, 원형으로 표현할 수 있고

원형이라면 4각형인 탱크의 전체가 포함되면 피해량 100%, 조금이라도 걸치면 50%씩 줄어듬

중심점과 반지름이 있을때 주변의 사각형이 안에 들어오는지 걸치는지 밖에 있는지

판단할 수 있으시지요? 1)번의 확장입니다.

그림이 없어 이해를 하실지 모르겠는데 간단히 게임을 구현하는 것이 S사 1번 유형이라면

이 정도면 기출과 비슷한 정도이지 않을까 생각합니다.

#삼성_소프트웨어_역량_테스트