삼성전자 B형은 어떻게 취득하셨나요?

Notice

블로그의 첫글이며 앞으로 공부하는 내용을 포스팅 하려고 합니다 그러니 비방성 글은 정중히 사양합니다.

개인적으로 PS 및 컴퓨터를 공부하였기 때문에 왕도가 아님을 알려드립니다.
또, 필자는 Codeforce(민트), Boj, Swea 사이트의 랭커가 아님을 밝힙니다.
단 한번의 시험으로 취득하였기때문에 여러 B형의 유형을 알지 못하는 점 미리 양해부탁드립니다.
마지막으로 주관이 많이 섞여있고 자료에 대한 미흡한 점이 존재함으로 박트리님 블로그와 같이 참고하시기 바라며 알고리즘 빡공방에서 여러 정보를 얻을 수 있습니다.

짚고 넘어가기

• 링크드리스트, 스택, 큐, 힙, 체이닝 해시와 같은 자료구조를 구현 할 수 있는가?
• 구조체를 선언, 초기화, 재구성을 효율적으로 할 줄 아는가?
• Pointer를 잘 활용 할 수 있는가? -- 극히 드물게 출제가 됨
• STL 없이 문제를 풀 수 있는가?
  • Sorting, Binary search 등을 실행 할 수 있는가?
  • 위에 언급한 방법들을 할 줄아는가?
• 문제에 접근하기 전에 로직을 구현하고 정확하게 로직의 시간 복잡도를 계산 할 수 있는가?
• A 등급 이상을 취득하였는가?

개인적인 견해로 A형에서는 시간복잡도와 자료구조면에서 제약이 없는 것과 마찬가지이기에 이렇게 자세하게 짚고 넘어가는 경우는 없을 것으로 생각됩니다.
하지만 B형 시험에서 요구하는 부분은
'시간복잡도를 제대로 고려하여 O(NlogN)이내로 수행 할 수 있는 로직을 세울 수 있는가?',
'자료구조의 특성들을 제대로 이해하고 상황에 맞게 사용 할 수 있는가?'
를 파악하는 시험이기 때문에 위에 한 부분이라도 확실하다고 할 수 없다면 기초단계부터 차근차근 다시 공부하기를 추천합니다.

체감하기

B형은 STL을 사용할 수 없는 시험임을 인지하기 바랍니다.
대부분의 분들이 학교 강의, 독학, 인터넷 강의 등을 통해 어떠한 로직으로 작동하는지 공부하고 구현하는 경우는 과제 및 시험을 준비할 경우 외에 크게 신경쓰지 않고 이해하고 넘어 가는 부분이라고 생각합니다.
하지만 크게 다가 올 수 있는 하나의 예로 chaining hash table을 만들때 모든 면을 효율적으로 구현한다고 생각을 해보자

#define MOD 524287
struct node {
       node *next;
       unsigned long long num;
};
struct hnode {
       node *next;
       int cnt;
};
hnode myhash[MOD];
node input[1500000];

.....

위와 같은 코드가 있을때 어떻게하면 hash table을 초기화 하기위해 들어가는 시간은 O(input) 을 수행하여하는 방법을 생각 할 수도 있고 아래와 같이 O(MOD)의 방법을 생각하는 사람이 있다.

void init()
{
       size = 0;
       for (register int i = 0; i < MOD; i++) {
           myhash[i].cnt = 0;
       }
}

위의 설명을 보고 갑자기 자료구조에 대한 필요성을 느끼고 바로 당장 책 혹은 배웠던 강의 자료를 뒤적이고 있다면 반은 성공 한것이라고 본다.

하지만 위의 코드를 보면서 한가지를 더 캐치했기를 바란다. register int 의 존재와 pointer의 존재이다. 우리는 어떻게든 시간을 줄이고 제한시간안에 돌아가는 코드를 만드는 것을 목표로한다. 그렇기에 조금이라도 더 연산 속도를 높일 수 있는 register, inline등을 사용하는 것을 추천한다.

또 pointer는 data에 대한 접근을 자유롭게 해준다는 장점이 있으므로 꼬옥! 공부하기 바라며 어느 기업의 면접을 가든 단골로 나오는 부분이기 때문에 공부하는 것을 추천합니다.

이제는 기본적인 알고리즘에 대한 설명을 해볼까합니다.

B형을 준비하는 분들이 흔히 하는 질문이 있다. '어떠한 중요한 알고리즘이 필요로 할까요?', '꼭 알아야 하는게 있을까요?' 등의 질문이다. 이러한 질문을 받으면 역으로 '그런게 있으면 B형의 합격률이 A형 만큼 나오겠죠~?' 라고 반문하고 싶다.

우리는 보통적으로 쉬운 길, 정형화된 길을 걷고 싶어하지만 안타깝게 그런건 없다고 본다. 예를 들어 나는 quick sort기 쉬운거 같아서 merge sort는 공부 안했을때, 최악의 quick sort의 경우 test case가 O(N^2)의 경우라 제한시간안에 통과를 못하고 merge sort의 O(NlogN)만 통과가 될 수도 있다.

그러므로 내가 재미있어서 공부하는 것이라 생각을 하며 여러 공부를 하시기를 추천드립니다.
그리고 한 두번 치다보면 내가 아는게 나온다는게 여러번 시험 끝에 따신 분들의 정설입니다.

TIP

• 신분증은 꼭 잘 챙기자.
  • 실제 시험에 신분증 미지참으로 시험 못보고 퇴실하신 경우가 있습니다.
• 문제를 보자마자 키보드부터 두들기지 말것!
  • 4시간이라는 시간이 주어지기 때문에 로직을 정확하게 잡고 들어간다면 시간은 모자라지 않게 코딩 가능합니다.
• 전략을 수립하자.
  • 개인적인 경험으로 30분 ~ 1시간 로직 및 자료구조 설계, 1시간 반~2시간 반 구현, 30분 ~1시간 최적화 및 오류 체크.
  • 로직 설계가 잘 되지 않는 경우 화장실을 다녀오는 것을 추천한다. 인개원, 서울대 모두 다 화장실이 깨끗하고 좋다.
  • 코딩을 정확하게하고 로직을 정확하게 잡는데 모두의 개인차가 존재한다 고로 자신이 취약한 부분에 시간을 더 투자하자.
• 옆사람 신경쓰지 말자.
  • 실제 시험장에서 기세 등등하게 빠르게 퇴장하는 사람, 다리떠는 사람, 팬 튕기는 사람 등 여러 사람이 존재한다. 하지만 이 모든 사람들이 경쟁자가 아니다 나만 잘하면 붙는 시험이다.
• 앞서 말한 부분에서 공부의 정도가 없다고 말했지만 실제 빈출되는 유형은 있다.
  • sorting을 할 경우 merge sort, search를 진행 할 때도 binary search, 문자열을 만들때는 trie, 자료구조는 hash tabel, heap 그러니 이거라도 알고가자.
• 기도하자.
  • 종교 불문 , 무신론자 다 필요없다. 일단 기도하자 그래야 내가 아는 문제 나온다.