삼성전자 DX에서 진행한 S/W 알고리즘 특강을 이수했다. 사전 코딩테스트를 합격한 인원을 대상으로 진행되었다.
주요 활동
- 삼성전자 현직자 멘토링
- 알고리즘 전문가 문제 풀이 및 해설
- 삼성(SWEA) 역량테스트 B형 기출 풀이 및 시험
성과
- 수강생 200명 대상 중간 코드배틀 Java부문 1등
- 삼성 B형 검정 합격
배운 점
코딩테스트 준비는 어떻게 해야할까?
- 문제 조건을 추상화 하기(여러 문제들 사이의 공통점 찾기)
- 다양한 접근법 시도하기
- 다른 사람 코드 분석해보기 (다양한 접근법)
새로 배운 알고리즘
- Trie
- Segment Tree (Lazy, Dynamic 변형)
- 제곱근 분할법
- 롤링 해싱(라빈 카프 알고리즘)
직접 배우진 않았지만 언급된 알고리즘
알고리즘과 관련된 지식
최적화 해볼 수 있는 부분
- 캐시(L1, L2, L3)를 활용하기 위해 배열을 애용하라.
- 해싱의 경우 롤링 해싱을 고려해라. (직접 해쉬함수 구현)
- 레드블랙트리의 경우
O(log2 n)정도로 매우 느리다. - 객체 생성과 삭제를 최소화하라.
- 동적배열의 더블링으로 인한 내부 단편화를 고려하라.(크기 미리 할당)
시간복잡도의 함정
시간복잡도를 계산해보다가 시간이 없다면 이를 그냥 구현하고 최적화를 고려해보자.
B형 검정 조언
B형 검정 보시는 분들이 계실거 같아 조언도 남겨봅니다.
- 정해 시간복잡도가 1억을 넘기도 한다. (최적화가 중요한 이유)
- 완전 랜덤 테스트케이스이다. (확실하진 않지만 저격 케이스가 없기에 빅오자료형으로 계산시 과하게 비관적일 수 있다.)
CS/Software Engineer