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

지난주 일요일 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로 풀면 될 것 같은데 하실 수 있으시겠어요?

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

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

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

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