삼성 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/