삼성 SW 역량 테스트 B형 Reference 코드

삼성 B형 전체 링크

 

swexpertacademy.com/main/main.do

 

상단의 LEARN -> Visual Reference Code에 참조 코드가 있다.

 

Data Structure, Algorithm에 대한 reference code가 실제 시험에도 제공된다.

(문제 왼쪽 상단에 Reference 탭 제공)

필요한 코드를 정리해보면.

 

Data Structure

1) Stack

    - 배열로 간단히 만들 수 있다. 참조 코드처럼 만들면 느리다. (스택 예시 참고)

 

2) Queue 

    - 배열로 간단히 만들 수 있다. 참조 코드처럼 만들면 느리다. (큐 예시 참고)

 

3) Priority Queue

    - B형 필수, 못 외우겠다면 참조 코드도 나쁘진 않지만, 자기만의 코드를 만들도록 하자.

    - 특히 참조 코드의 push, pop에서 size 체크를 하는 코드는 실제 응용할 때 불필요할 수 있다.

    - 개념 설명 : 링크 참고

  

4) Tree

    - B형에 꽤 나오는 편이지만, 공부량도 많아지고, 구현도 어렵고, 응용도 어렵다.

    - 포기하고 다음 시험을 노리자!

 

5) Graph

    - A형 때 처럼, Graph를 직접 만드는 경우는 거의 없다.

 

6) Linked List

    - B형 필수, 자신만의 링크드 리스트를 만들도록 하자.

    - 해시 테이블을 만들 때, 체이닝 방식으로 만드는 것이 유리하기 때문에 꼭 익혀둬야 한다.

    - 링크 참고 

 

7) Hash 

    - B형 필수, Open Address vs Chaining 방법이 있다.

    - 참조 코드는 Open Address인데 절대 쓰지말고 Chaining 기법을 익혀두자.

    - Open Address 방법은 B형에서 수 많은 충돌을 관리하기 어렵다.

    - 참조 코드에서는 hash key 변환 코드만 이용하자.

    - 링크 참고

 

Algorithm

1) Insertion Sort

    - Merge Sort를 사용하도록 하자.

    - 하지만, 5~10개 이하의 정렬은 Insertion이 빠를 순 있다.

 

2) Counting Sort

    - Merge Sort를 사용하도록 하자.

    - 메모리 제한이 큰 문제에서 사용해야할 순 있지만, 보통 C형에서 사용한다.

 

3) Binary Search

    - 이분 탐색은 틀은 비슷하지만, 문제 유형에 따라 구현 방법이 다르다.

    - B형에서 정렬이 나온다면, Binary Search를 사용해야할 가능성이 높다.

    - 다양한 이분 탐색 문제를 풀어두도록 하자.

 

4) DFS Search

    - B형 특이 유형에서 가끔 사용한다. 삼성 A형 유형을 풀 정도면 충분하다.

 

5) BFS Search

    - 4)와 동일.

 

6) Dynamic Programming 

    - 연습할 필요는 없지만, Memoization 관련 테크닉은 익혀두도록 하자.

 

7) Minimum Spanning Tree - Kruskal

8) Topological Sort

9) Bipartite Match

10) Dijkstra

    - 현재까지 본 적이 없다.

 

11) Quick Sort

    - Merge Sort를 사용하자. 참조 코드의 quick은 최악의 경우 O(N²)이다.

    - 숨겨진 tc가 Quick을 O(N²)으로 만들 수 있다.

    - 문제를 푸는데, 정렬에 시간을 뺏기기 싫다면 참조 코드의 Quick을 이용하고, 시간이 남으면 Merge로 대체하자.

 

12) Floyd Warshall

    - 현재까지 본 적이 없다.

 

 

B형에서는 특정 알고리즘을 알아야 풀 수 있는 문제는 거의 없다.

따라서 7) ~ 10), 12) 같은 대놓고 알고리즘 유형은 B형에서 보기 힘들다.

혹시나 저런 유형이 보이더라도 분명 Hash나 Priority Queue로 풀 수 있다.

---

수 많은 참조 코드 중, 실제로 사용하는 코드는 아래 정도.

 

1) Hash의 hashing 함수

5381은 prime number이다. 5381인 이유는 많은 소수 중 성능이 괜찮기 때문이라고 한다.

실제 시험에서 5381보다 큰 소수를 사용해야 할 수 있으므로, prime number를 구하는 방법은 익혀두자.  

그리고 아래 Hash 함수를 실제로 백준에서도 사용해보자.

unsigned long hash(const char *str)
{
	unsigned long hash = 5381;
	int c;

	while (c = *str++)
	{
		hash = (((hash << 5) + hash) + c) % MAX_TABLE;
	}

	return hash % MAX_TABLE;
}

 

2) Quick Sort

위에서 말했듯이, 문제를 풀 때, 정렬이 필요하면 당장 쓰되, 시간이 나면 Merge Sort로 바꾸자.

제공하는 tc가 통과되더라도, 실제 숨겨진 tc가 있다는 것을 잊지 말자.

#include <stdio.h>

#define MAX_NUM 100

int input[MAX_NUM];
int num;

void quickSort(int first, int last)
{
	int pivot;
	int i;
	int j;
	int temp;
	
	if (first < last)
	{
		pivot = first;
		i = first;
		j = last;

		while (i < j)
		{
			while (input[i] <= input[pivot] && i < last)
			{
				i++;
			}
			while (input[j] > input[pivot])
			{
				j--;
			}
			if (i < j)
			{
				temp = input[i];
				input[i] = input[j];
				input[j] = temp;
			}
		}

		temp = input[pivot];
		input[pivot] = input[j];
		input[j] = temp;

		quickSort(first, j - 1);
		quickSort(j + 1, last);
	}
}

void printResult(void)
{
	int i;

	for (i = 0; i < num; ++i)
	{
		printf("%d ", input[i]);
	}
	printf("\n");
}

int main(void)
{
	int T;
	int test_case;
	int i;

	scanf("%d", &T);

	for (test_case = 1; test_case <= T; test_case++)
	{
		scanf("%d", &num);
		for (i = 0; i < num; i++)
		{
			scanf("%d", &input[i]);
		}
		quickSort(0, num - 1);
		printf("#%d ", test_case);
		printResult();
	}

	return 0;
}

---

쿼리형 문제나, 시뮬레이션 문제 등은 아이디어 문제이므로, 시험장 가서 공부하는 수 밖에 없다.

 

주로 Priority Queue, Hash Table, (+ Merge Sort 정도)가 정석 유형이므로, 집중 공부하자.

Priority Queue, Hash Table(를 위한 Linked List 포함)를 자유자재로 만들 수준으로 익혀두고

나올 때 까지 시험을 치는 것이 가장 효율적으로 합격하는 방법인 것 같다.

 

알고리즘 공부가 좋다면 다음으로 많이 나오는 유형인 Tree까지 공부하자. 

 

하지만 아쉽게도 BOJ에서는 해시 테이블 유형의 문제를 찾기 힘들다.

왜냐하면 BOJ에서는 라이브러리도 사용 가능하고, 웬만한 문제들은 stl의 map으로 해결할 수 있기 때문이다.

 

최대한 연습할 수 있는 문제는 블로그를 참고하자.

 

삼성 B형 링크에 개념과 문제를 정리하였다.