삼성 알고리즘 테스트 통과를 위한 기록(SW Certi Pro)

도움이 된 글 들

---
합격후기
https://dirmathfl.tistory.com/409
https://hjworks.tistory.com/31
https://lazyduo.github.io/SW-pro-review/
---
문제와 정리
https://github.com/yms218/Pro
---
expert
https://okky.kr/articles/669446

OKKY - 삼성 sw역량 테스트 관련 이야기

기본으로 구현할줄 알아야 되는 자료구조

시험보면서 필요한 최소한의 기초 지식은 다음과 같다.

1. 스택
2. 큐
3. 소트(quick, merge, heap)
4. 트라이
5. 유니온파인드
6. 이분탐색

핵심

• 해시(정적리스트 사용)

Pro등급의 핵심은 속도이다. A형과 다르게 B형부터는 절대평가에서 상대평가로 바뀌기 때문에 속도를 빠르게 하는게 굉장히 중요하다. 그렇기 때문에 정적리스트를 활용하여 미리 정적으로 배열을 선언해놓는게 malloc를 사용하는 것보다 5배이상 빠르다.

각 주차별 문제

PRO형은 자료구조를 복잡하고 많이 쓰는 문제를 직접 만들거나 풀어보는게 가장 중요하다. 문제를 풀면서 주의할 점은 1시간안에 최적의 설계를 하고 코드로 들어가는게 중요하다. 무작정 설계없이 코드부터 작성하는 것은 엄청난 실력자가 아니면 불가능하다. B형에서는 시간복잡도를 고려할 필요는 없고 O(N^2)처럼 무식하게 설계만 안하면 된다. 어째든 1시간 내에 설계를 끝내고 2시간동안 설계한대로 코드를 짜고 나머지 1시간을 테스트케이스를 맞춰보면서 디버깅하는 것이 가장 이상적이다.

1주차) : DB 문제

2주차) : 도서 추천 서비스 문제

3주차) : 엑셀 문제

문제 추천

1. 홍준이의 사전놀이 : 해시나 트라이로 풀 수 있으며 B형 문제처럼 구성되있고 STL을 사용하면 제출이 되지 않는다.
2. 카드 정렬하기 : STL 사용없이 힙을 직접 구현해본다.
3. 생태학 : 해시나 트라이로 풀 수 있으며 해시로 풀면 정렬까지 해야된다.
4. 듣보잡 : 해시나 트라이로 푼다.
5. 블록부품맞추기 : C형 예제라 그런지 많이 어렵다. 비트마스크, 큐, 해시 등 다양한 방법으로 풀 수 있으며 해시가 가장 빠르다.
6. 친구 네트워크 : 해시 + 유니온파인드 응용
7. 문자열 잘라내기 : 해시 + 이분탐색 응용
8. 수 찾기 : 해시 or 이분탐색
9. 회사에 있는 사람 : 해시나 트라이로 푼다.
10. (카카오 3차)자동완성 : 단순 트라이 구현

 

 

팁들

for

#include <list>

using namespace std;

int arr[5] = { 3, 4, 5, 6, 7 };

int main() {
    for (auto& value : arr)
        value++;
}

• `auto value : arr`로 하게 되면, 객체 크기만큼 복사가 발생하고 값을 수정할 수 없다.
• 기본 타입뿐 아니라 `Container`들도 사용가능하다.

 

memset

#include <cstring>

#define MAX_ARR    10000

int arr[MAX_ARR];

int main() {
    memset(arr, 0, sizeof(int) * MAX_ARR);
}

• init도 시간이 드는 작업이다. STL의 Container가 아니라면 memset을 활용하면 좋다.

 

set, map

#include <set>
#include <string>
#include <iostream>

using namespace std;

set<string> words;

int main() {
    char curWord[][5] = { "ABAA", "BBCC", "EFEE", "KFFF", "GSAA" };

    for (auto& w : curWord)
        words.insert(w);

    cout << "사전 순 정렬" << endl;
    cout << *words.begin() << endl;

    auto iter = words.find("BBCC");
    words.erase(iter);
    
    cout << "BBCC 삭제 확인" << endl;
    for (auto& w : words)
        cout << w << endl;
}

 set, map에서 사용하는 메서드들은 유사하다. 따라서 어떤 식으로 사용하는지 간략히 정리하면 위와 같다. `erase`의 return 값은 erase 되는 값의 next이다.

 

unordered_map

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<string, int> wordCntMap;

int main() {
    wordCntMap.clear(); // 초기화
    
    wordCntMap["BLUE"] = 100;
    
    if (wordCntMap.count("BLUE")) // key 값 확인
    	cout << "값 존재함" << endl;
    
    
    wordCntMap["BLUE"] = 50; // 값 갱신
    wordCntMap.erase("BLUE"); // 값 삭제
}

• unordered_map을 통해 key, value 값을 유지, 갱신할 수 있다.