ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 삼성 SDS 대학생 동계 알고리즘 특강 후기
    백준 2021. 2. 8. 23:50

    삼성 SDS에서는 방학별로 대학생을 대상으로 2주 알고리즘 특강을 진행합니다. 별다른 자기소개서나 면접 없이 구글 폼으로 신청을 받고, 졸업예정자를 위주로 160명 정도를 선발합니다.

     

    폼에는 간단히, 대학교, 학점, SCPC 수상 여부, 졸업예정여부등을 기재하게 되어 있습니다.

     

    별다른 정보가 없었으나, 2주간 알고리즘 특강을 진행하기 위한 목적으로 신청하게 되었습니다.

    그 결과, 2주차에 배정되어서 특강을 듣게 되었습니다.

     

    비대면 수업의 진행

     

    동계 알고리즘 특강은 SDS 채용과도 연계가 되어 있습니다.

    출석률이 80% 이상인 수료자가 삼성 SDS Pro 시험을 1회 응시할 수 있는데,

    시험을 통과하면 삼성SDS에 임원 면접만 남는 특채가 열리게 됩니다.

    수업은 2주간 9시부터 6시까지 진행되었습니다. 비대면임에도 불구하고, 출석이 엄격한 편이었습니다.

    여담입니다만, 사용하는 원격강좌 프로그램이 맥에서 지원이 안 되어 초기 진행에 저는 어려움을 겪었습니다.

    예년 같았으면 사옥에 가서 직접 강의를 들었다고 하므로, 학습 환경이 더 좋았을 것 같습니다.

    수업강좌의 진행

    수업이 진행되기 전에 교재가 왔는데, 너무 기초적인 알고리즘 내용만 설명해 주는지라, 졸업을 앞둔 전공자에게는 너무 평이한 수업이 진행될 것을 우려하는 마음이 있었습니다.

    수업 첫 날, 이런 우려는 기우였음이 밝혀졌는데요.

    교재는 어디까지나 오전에 가볍게 훑고 넘어가는 선을 넘어가지 않고, 백준의 문제들을 풀어보는 것으로 진행되었기 때문입니다.

    따라서 이론 위주의 대학 강의보다는, 구현과 기술적 풀이에 좀더 맞춰졌습니다.

    특강에 활용했던 문제셋

     

    하루에 백준 플랫폼에서 12문제~13문제 정도를 풀어 보았는데요.

    첫날부터 스도쿠, N-Queen 같은 난이도가 낮지 않은 문제가 나와서 개인적으론 놀란 마음이었습니다.

    난이도는 조금씩 높아지면서, solved.ac 랭킹 기준으로 실버 세네 문제, 골드 세네 문제, 플래티넘 하위 세내 문제 정도가 셋으로 구성되어서

    매번 풀거나, 못 풀어서 해설을 듣는 방법으로 수강을 했습니다.

    저는 백준 플랫폼을 애용했기 때문에, 실버나 골드 랭킹 문제는 기존에 풀어본 문제가 많았는데요.

    대부분 각 섹션별로 대표격인 문제들을 모아 둔 느낌이 강했습니다.

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

     

    11438번: LCA 2

    첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정

    www.acmicpc.net

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

     

    14003번: 가장 긴 증가하는 부분 수열 5

    첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

    www.acmicpc.net

    인덱스 트리와 확장 유클리드 호제법의 학습

    2년 정도 알고리즘을 풀었는데, 제 연습은 골드 난이도의 문제 및

    코드포스 DIV 2 초반 문제에 집중되었습니다.

    이런 문제들은 비교적 간단한 프로그래밍 능력과 통찰을 요구합니다.

    이번 특강의 문제셋에는 일부 비교적 복잡한 자료구조를 사용할 것을 요구했습니다.

    평소에는 그다지 연습해 보지 않았던 '세그먼트 트리' 류의 문제를 풀기 위한 인덱스 트리 및, 정수론의 일부 문제를 해결하기 위한 확장 유클리드 호제법을 연습할 수 있었습니다.

     

    연습 문제중에 초고난이도는 다이아 한 문제였는데요.

    한번도 풀지 했던 다이아 등급의 문제가 하나 있어서, 설명을 듣고 코드를 작성하여 AC를 받아낼 수 있습니다.

    www.acmicpc.net/problem/1626

     

    1626번: 두 번째로 작은 스패닝 트리

    첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100,

    www.acmicpc.net

     

    삼성SDS PRO 응시

    삼성SDS Pro는 SDS 내부 임직원을 위한 응시 세트를 활용한다고 합니다.

    주변의 말을 들어보니, 굉장히 유명한 삼성전자 Pro 와는 난도면에서도 별개의 시험으로 여겨졌습니다.

    삼성전자 Pro는 라이브러리를 쓸 수 없는데 반해, 삼성SDS Pro는 라이브러리를 쓸 수 있습니다.

    언어제한은 C++, C, Java로 동일하며, 한 문제로 4시간이 주어집니다.

    특이한 점은 검색이 일체 금지된다는 점입니다. C++ 레퍼런스 문서도 확인할 수 없기에, 기본적인 문법이나 알고리즘을 검색할 수는 없습니다.

    응시했던 시험 문제의 난이도는 실버 5 정도 난이도라고 여겨졌습니다. 시험 입실 후 20분만에 최악의 시간복잡도일 경우 10^7. n^2 에 해당하는 코드를 작성해낼 수 있었습니다.

    문제는 테스트케이스가 최대 40개가 되므로, 모든 테스트케이스가 최악의 경우로 주어질 경우, 시간 초과가 난다는 점이었습니다.

    응시 종료까지 AC임을 확인할 수 없었기 때문에, n^2가 정해임을 확신할 수 없어서, nlogn 정도의 풀이가 있을지 고민하다가 결국 n^2로 제출하고 퇴실했습니다.

    이후 Pro 합격 대상자라는 문자가 왔습니다. 원래 생각했던 n^2 풀이가 정해였던 모양입니다.

    누가 이 특강을 들으면 좋을까

    삼성 SDS 입사에 관심이 있는 분이 특강을 수강한다면 유익할 것은, 누구나 알 수 있는 사실입니다.

    하지만 삼성 SDS 에 관심이 없는 분들을 대상으로 생각했을 때, 대학생의 귀중한 방학 2주를 소모한다는 것은 적지 않은 기회비용입니다.

    그래서 이 특강을 수강을 어느 정도 수준의 분이 들어야 하는지 사견을 달았습니다.

    이 알고리즘 특강을 들으면 좋을 분들

    알고리즘에 대해서 1년 이하의 숙련도를 가진 분들이고, solved.ac 랭크 기준으로 골드 문항을 해결함에 어려움을 겪는 분이시면 특강을 들으시면 크게 도움이 될 것 같습니다. 골드와 플래티넘 하위 랭크 문제 중에서, 대표적인 문제들을 연습해 볼 수 있는 기회가 될 것입니다.

    이 알고리즘 특강을 듣지 않아도 될 분들

    백준에서 푼 문제가 거의 없거나, 자신이 생각하기에 자신의 코딩 실력이 전공자 2학년 수준 정도에 머무른다고 생각하면, 난이도가 높아서 들을 필요가 없다고 생각합니다. 트리나 스택 같은 기초 구현은 개론만 훑고 넘어가고, 단순 구현을 넘어선 실무적인 구현으로 넘어가기 떄문에 이해에 어려움이 있다고 생각이 듭니다.

    한편, 알고리즘을 평소에 즐겨서 푸신 분이라면, 굳이 신청을 하지 않아도 될 것이라고 생각합니다. 골드 난이도에서 대표성을 높게 띈 문제들을 푼 탓에, 기존에 풀었던 문제를 복기하는 수준에 머무를 정도라고 생각이 듭니다.

    코드포스로 치면, 민트 상위의 랭크를 가진 분에게는 그다지 도움이 되지 않을 것입니다.

    N-Queen 과 스도쿠를 무난하게 그 자리에서 풀어내실 수 있는 역량 정도가 기준이 될 것입니다.

Designed by Tistory.