sw.md

삼성 SW 역량 테스트 대비 자료

Assembled by GimunLee

기본 Tip

1. cin/cout 대신에 scanf/printf 사용하자!

입출력 함수의 성능차이가 많이 나기 때문에 scanf/printf를 사용합시다.

2. C로 풀더라도 CPP 컴파일러를 사용하자!

CPP 컴파일러가 보다 자세한 오류 사유를 리턴해주는 경우가 많습니다.

3. 난이도가 올라갈수록 문제를 바로 푸는 것보다 어떻게 풀 것인지를 오래 고민하자!

B형 이상의 난이도의 경우에는 30분 ~ 1시간 이상을 생각하고 완전한 풀이 전략을 세우고 시작해야합니다.

4. Segmentation fault가 뜬다면 올바른 참조를 하고 있는지 확인하자!

Visual studio의 경우에는 올바르지 않은 메모리를 write 하더라도 넘어가는 경우가 많지만, 채점 컴파일러는 read만 하더라도 오류가 발생합니다.

A형 돌파 전략

1. A형에 나오는 문제

Intermediate에서 Advanced 사이 2문제가 출제되며, 2문제를 모두 풀면 A+(Advanced) 등급을 획득합니다.

A : 경우의 수 or 상태 관리

A+ : 경우의 수 and 상태 관리

2. A형 돌파를 위해 학습해야 하는 것

경우의 수를 만드는 것과 상태 관리를 학습합니다. 전체 경우의 수를 만들지 못하는 사람은 A+ 등급을 획득할 수 없습니다.

3. 경우의 수(재귀)

전체 경우의 수를 만드는 가장 쉬운 방법은 재귀함수를 이용하는 것입니다. 재귀를 이용한 방법은 매우 느리고 메모리를 많이 사용하지만 정답을 얻을 수 있는 가장 확정적인 방법입니다. 따라서 모든 학습자는 반드시 재귀 함수를 만드는 방법을 알아야 하며 재귀 함수를 이용한 완전 검색에서 출발하여 가지치기를 이용한 백트래킹의 기법으로 나아가는 것이 바람직합니다. 재귀 함수의 경우 가지치기나 메모이제이션을 추가하기 매우 쉽기 때문에 Advanced 난이도에서 필요한 최적화를 추가하기에 적합합니다.

재귀함수의 기본적인 구조, 자기 자신을 호출하기 전에 반드시 종료 조건이 있어야합니다.

void recursive(int n){
    //종료조건
    if(n == 10){
        return;
    }
    //자기 자신을 호출
    recursive(n + 1);
}

int main(){
    recursive(0);
    return 0;
}

4. 상태 관리

문제 풀이에 있어서 상태란 진행 상황을 특정 시점에서 바라본 모습입니다. 예를 들어, 2개의 주사위를 차례로 던지는데 1개를 던졌을 때라거나 2개의 파란공과 2개의 빨간공이 들어있는 주머니에서 1개의 빨간공을 꺼냈을 때와 같은 것들입니다. 이처럼 특정한 상태를 기록하고 기억하는 것을 상태 관리라고 합니다. 상태 관리만 존재하는 문제들은 여러 가지 유형이 있는데, 가장 대표적인 것이 원자 충돌과 같은 문제입니다.

상태 관리 문제 예시) 4방향으로 움직이고 있는 원자들이 있다. 이 원자들은 서로 충돌하면 사라지게 된다. 원자들의 움직임을 무한히 진행한다고 했을 때 최종적으로 남는 원자의 개수를 구하시오.

위와 같은 문제는 별도로 경우의 수를 생성할 필요가 없으며 상태 관리만 처리하게 되면 정답에 도달할 수 있습니다. A형의 경우 상태 관리만 존재하는 문제가 자주 출제되며, 상태 관리는 각 문제마다 다르기 때문에 여러 문제를 접하면 접할수록 상태 관리에 대한 실력이 늘게 됩니다.

5. 완전 검색

완전 검색은 그래프 문제를 풀 수 있는 가장 느린 방법이며, 주로 재귀를 이용하게 됩니다. 재귀를 이용한 완전 검색은 매우 느리고 비효율적인 방법이지만, 단 몇 라인 수준의 최적화 코드만 삽입하더라도 상당한 수준의 최적화가 가능하기 때문에 다음 단계로 나아가기 위한 징검다리로서 활용하는 것이 바람직합니다. 전체 경우의 수를 만들어낼 줄 알아야 하는 것은 B형 응시자에게도 공통적인 사항인데, 역설적으로 전체 경우의 수를 볼 수 없다면 최적화된 풀이도 불가능하기 때문입니다.

6. DFS(깊이우선탐색)

깊이우선탐색은 최소값 혹은 최단거리 문제에서 자주 사용되는 풀이 방법입니다. 한 지점에서 출발해서 도착지(혹은 그래프의 마지막 정점)에 도달할 때까지 이동하며, 재귀를 이용한 구현을 주로 사용합니다. 재귀를 이용해서 전체 경우의 수를 만드는 것이 쉽기 때문에 A형에서는 자주 사용되는 방법입니다.

7. BFS(너비우선탐색)

너비 우선 탐색은 우선순위 큐 등을 응용할 때 가끔 사용되지만 A형에서는 자주 쓰지 않습니다. for문과 큐를 이용하는 방법이 자주 사용됩니다.

8. backtracking(백트래킹)

백트래킹은 완전 검색에서 나아가 상당한 수준의 최적화를 이루는 방법입니다. 주로 가지치기(pruning)나 메모이제이션(memoization) 등의 방법을 활용하고, 두 가지 모두 활용하는 경우가 많습니다. 이 때문에 그래프 문제의 경우 많은 경우에서 BFS보다 DFS가 성능면에서 우수한 경우가 많습니다. 잘 짠 백트래킹은 다이나믹 프로그래밍(DP)보다 빠릅니다.

9. memoization(메모이제이션)

문제를 풀어나가면서 도출한 중간 값을 메모하면서 푸는 방법입니다. 중복 연산을 줄일 수 있기 때문에 모든 경우의 수를 봐야하는 문제에서 매우 높은 성능 향상이 있으며, 몇 줄의 코드 만으로도 엄청난 성능 향상을 가져올 수 있습니다. 메모리의 한계로 모든 경우의 수를 다 저장하지 못하는 경우에도 일부만 메모이제이션을 하더라도, 상당한 수준의 성능 향상이 가능합니다.

10. DP(다이나믹 프로그래밍)

잘 짠 백트래킹은 다이나믹 프로그래밍(DP)보다 빠릅니다.

B형 대비 알고리즘

기본

• LinkedList, Stack, Queue, Tree
• 이분탐색, MST, disjointset
• 해싱 : B형보는데 해싱을 모르고 응용할 줄 모르면 바로 혀 깨물어야됨
• 링크드리스트 구현
• 트리 구현 (자식 수 안 정해진 트리)
• 메모이제이션
• 비트마스킹
• 분할정복
• Sort (퀵, 계수, 기수, 머지)
• Heap (스케줄링)

추가

• Trie : 문자열 관련 문제
• LCA(Lowest Common Ancestor) (디렉토리 구조, 가계도)
• BST(Binary Search Tree)
• Segment Tree
• Sqrt Decompisition