삼성 SW 역량테스트 B형 (Professional 등급)
B형 준비 관련 글
- 준비방법 (박트리) https://baactree.tistory.com/53
- 준비방법 요약정리 (MR.L) http://mrl.kr/b-test/
- 준비방법 (알광) https://algwang.tistory.com/59
- 문제예시 (mark3236) https://mark3236.tistory.com/entry/%EC%82%BC%EC%84%B1%EC%A0%84%EC%9E%90-SW-%ED%85%8C%EC%8A%A4%ED%8A%B8-B%ED%98%95-%EA%B0%80%EC%9D%B4%EB%93%9C
시험장에서 제공되는 레퍼런스 코드
https://swexpertacademy.com/main/code/referenceCode/referenceCodeList.do?#none
내가 준비한 내용
1. 더블 링크드리스트 (+문제 풀 때 배열에 주소 저장할 수 있으면 꼭 저장할 것! 삭제를 최대한 빠르게 하도록. 혹은 삭제를 바로 안 해도 된다면 삭제 테이블, 배열로 저장해둘 것)
링크드 리스트를 구현하고 Hash size 배열만큼 만들어서 거기에 달아두면 바로 해시 알고리즘...
2. 해시 (+ 최적화를 위해 트라이도 공부 => 필요 없음)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#define HASH_SIZE (100000-9)
int N;
char unique_str[10001][22];
int unique_hash[10001]; // 찾아가기 쉬우라고 hash 저장해주기
char input_str[10001][22];
int unique_num;
struct _st {
char name[22]; // strcmp
int pos; // position 저장
struct _st *next;
};
struct _st Hash_map[HASH_SIZE];
int Hash_num[HASH_SIZE];
int compare(char *a, char*b)
{
int i;
for (i = 0; a[i] && b[i] && (a[i] == b[i]); i++);
if((a[i] - b[i])==0)return 1;
else return 0;
}
int get_hash(char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
{
hash = (((hash << 5) + hash) + c) % HASH_SIZE;
}
hash = hash % HASH_SIZE;
return hash;
}
void insert_hash(char * str, int pos)
{
// str을 해시에 넣는다.
struct _st *head;
char *temp = str;
int hash = get_hash(str);
head = &Hash_map[hash];
// 일단 들어갈 헤드 먼저 찾기
for (;;)
{
if (head->next == 0)
{
int idx = 0;
while (unique_str[unique_num][idx] = temp[idx])idx++;
unique_hash[unique_num] = hash; // 그때의 hash값 저장해줌!
unique_num++;
// unique 어케 그 자리에 넣지
idx = 0;
while (head->name[idx] = temp[idx])idx++;
break;// 들어갈 자리 발견
}
else if (compare(head->name, str)) break;
hash = (hash + 1) % HASH_SIZE;
head = &Hash_map[hash];
}
// break 했을 때의 최종 해시가 추가됨
Hash_num[hash]++;
// 그 자리가 내 자리
for (;;)
{
if (head->next == NULL || head->next->pos > pos)
{
struct _st *newp = (struct _st *)calloc(1, sizeof(struct _st));
if (newp == 0x00) return 0;
newp->pos = pos;
newp->next = head->next;
head->next = newp;
break;
}
head = head->next;
}
}3. 힙 (+자료에 따른 최소, 최대값 저장하는 테이블)
#include <stdio.h>
int Heap[5001];
int lastnode = 1;
void insert_heap(int data)
{
int n = lastnode;
Heap[lastnode++] = data;
while (n / 2 > 0)
{
if (Heap[n] < Heap[n / 2])
{
int temp = Heap[n];
Heap[n] = Heap[n / 2];
Heap[n / 2] = temp;
}
else break;
n = n / 2;
}
}
int delete_heap(void)
{
int data = Heap[1];
int n = 1;
Heap[1] = Heap[--lastnode];
while (n * 2 <= lastnode)
{
int c;
if (n * 2 == lastnode)
{
c = n * 2;
}
else
{
if (Heap[n * 2] < Heap[n * 2 + 1])
{
c = n * 2;
}
else c = n * 2 + 1;
}
if (Heap[c] < Heap[n])
{
int temp = Heap[c];
Heap[c] = Heap[n];
Heap[n] = temp;
}
else break;
n = c;
}
return data;
}
// 밑에 main() 필요
+ Union Find 공부하기
+ 세그먼트 트리 준비 (필요 없음)
#include <stdio.h>
int Arr[1 << 20];
int pos[100002];
void update(int node, int s, int e, int idx, int data)
{
if (s == e)
{
Arr[node] = data; // 1로 채워줌
return;
}
int m = (s + e) / 2;
if (idx <= m) update(node * 2, s, m, idx, data);
else update(node * 2 + 1, m + 1, e, idx, data);
Arr[node] = Arr[node * 2] + Arr[node * 2 + 1];
}
int query(int node, int s, int e, int qs, int qe)
{
if (qs <= s && e <= qe) return Arr[node];
else if (qe < s || e < qs) return 0;
int m = (s + e) / 2;
int l = query(node * 2, s, m, qs, qe);
int r = query(node * 2 + 1, m + 1, e, qs, qe);
return l + r;
}
int main(void)
{
int T;
scanf("%d", &T);
for (int t = 0; t < T; t++)
{
int N, M;
int start;
scanf("%d %d", &N, &M);
start = M + 1;
for (int n = 1; n <= N; n++)
{
pos[n] = n + M;
update(1, 1, N+M, pos[n], 1);
}
for (int m = 0; m < M; m++)
{
int temp;
scanf("%d", &temp);
// temp 영화를 찾아옴
if (pos[temp]-1 >= 1) printf("%d ", query(1, 1, N + M, 1, pos[temp] - 1));
else printf("0 ");
update(1, 1, N + M, pos[temp], 0); // 영화 꺼냄
update(1, 1, N + M, --start, 1); // 영화 맨 앞으로 옮김
pos[temp] = start;
}
printf("\n");
for (int i = 0; i <= N; i++) pos[i] = 0;
for (int i = 0; i <= 1 << 20; i++) Arr[i] = 0;
}
return 0;
}
시험에 필요한 알고리즘
- 해시: 사람 이름 등 문자열 자료가 많이 들어오면 해시 필수
- 링크드리스트: 특정 날짜에 예약한 손님 등 링크드 리스트 추가, 삭제 구현 필요 (인덱스가 숫자 id 값이 아니면 해시와 합쳐지는 경우도 많음)
- 트리: 디렉토리 추가, 순회의 경우 Left child Right sibling tree 구현 필요 (https://www.geeksforgeeks.org/left-child-right-sibling-representation-tree/)
- 소트: 퀵 소트 / 힙 소트
- 힙: 순위 관리가 필요한 문제
- BFS, DFS: 거의 안 나오나 때때로 스택 구현 등이 필요할 수 있음
- 비트마스크: 자료 압축이 필요한 문제에 사용 가능하며, 대부분 문제에 시간 단축을 위해서 적용 가능
참고
라이브러리는 메모리 alloc 외에는 사용할 수 없다.
그러나 실제로 메모리 alloc을 쓰는 경우 대개는 시간초과가 나기 때문에 사전에 정적으로 할당을 해두어야한다.
최적화 시도
- 삭제시 바로 주소로 접근해서 삭제할 수 있게 배열에 저장해두거나,
삭제할 것이 여러 곳에 있어서 배열에 한 값을 저장할 수 없는 경우에는
삭제 인덱스를 둬서 거기에만 삭제되었다고 표시.
나중에 링크드리스트를 탐색하다가 삭제 테이블을 확인하고 삭제해야하면 삭제
- 해시보다 최대한 비트로 해결 가능한지 확인하기
- 해시 테이블 비교시에 원래 hash 값 (해시 테이블 사이즈로 나누기 전 값. 사이즈는 long long) 도 구조체 멤버 변수로 둬서 같은지 다른지 판단하는 시간을 조금 더 절약하기. 짧은 해시 비교 - 긴 원래 해시 비교 - 진짜 값 비교. 이렇게 3단 구조로.
- 배열 초기화를 안 하기 위해서 testcase 번호를 visited 배열의 visited 체크용으로 사용.
혹은 카운트 배열 등에 체크할 때 함수 호출 횟수를 누적해서 체크용으로 사용.
- heap 으로 자료구조를 사용할 때, 빈번하게 상위 x 명이 출력되어야한다면, 상위 x +1 명만 heap 으로 관리하는 방법이 있다.
시간 복잡도, 공간 복잡도 계산
ex) 알고리즘 시간 복잡도 활용
또는 for문 * 몇개 겹처 들어갔는지 * n 몇갠지해서 1억 1초로 계산 <= 3초 등...
ex) 해시 테이블 크기 * 구조체 크기 (align까지 고려해서) <= 256MB 등....
참고할만한 문제
//https://leetcode.com/problems/lru-cache/