삼성전자 SW 역량테스트 B형 준비

 

 

svp 자기주도학습 겸 앞으로 칠 SW 역량테스트 B형에 대해 미리 정리해놓고자 함 😎

 

 

 

: 1문제를 4시간 동안 푸는 시험

: main 함수는 수정할 수 없고 solution 함수만 구현

: A형에서는 볼 수 없는 엄청난 사이즈의 제약사항 (1억, 10억…)

 

[ 문제 풀이 순서 ]

-> 문제 이해 

-> 아이디어 도출 

-> 설계(시간복잡도 계산) 

-> 구현 

-> 디버깅 

-> 최적화 (중복된 연산, 불필요한 연산 등을 찾아 최적화)

 

 

[ 공부해볼만한 키워드 ]

Array, Linked List, Bitwise 연산, Greedy, 완전탐색(Brute-Force), BFS, DFS, DP, 분할정복, Sort, Binary Search, Graph, Dijkstra, Tree, LCA, Heap, Trie, KMP, Hash, Union Find, 부분합, Segment Tree, Priority Queue

 

 

 

BFS

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int number = 9;
int visit[9];
vector<int> a[10];

void bfs(int start){
    queue<int> q;
    q.push(start);
    visit[start] = true;
    
    while(!q.empty()){
        // 큐에 값이 있을경우 계속 반복 실행
        // 큐에 값이 있다. => 아직 방문하지 않은 노드가 존재 한다. 
        int x = q.front();
        q.pop();
        printf("%d ", x);
        for(int i=0; i< a[x].size(); i++){
            int y = a[x][i];
            if(!visit[y]){
                // 방문하지 않았다면..
                q.push(y);
                visit[y] = true; 
            }
        }
    }
}

int main(void){
    
    // 1과 2를 연결 
    a[1].push_back(2);
    a[2].push_back(1);
    
    // 1과 3을 연결 
    a[1].push_back(3);
    a[3].push_back(1);
    
    // 2와 4를 연결 
    a[2].push_back(4);
    a[4].push_back(2);

    // 2와 5를 연결 
    a[2].push_back(5);
    a[5].push_back(2);
    
    // 4와 8을 연결 
    a[4].push_back(8);
    a[8].push_back(4);
    
    // 5와 9를 연결 
    a[5].push_back(9);
    a[9].push_back(5);
    
    // 3과 6을 연결 
    a[3].push_back(6);
    a[6].push_back(3);
    
    // 3과 7을 연결 
    a[3].push_back(7);
    a[7].push_back(3);
    
    // 1번 노드부터 bfs 탐색 실행 
    bfs(1);
    
    return 0;
} 
출처: https://hongku.tistory.com/156 [IT에 취.하.개.:티스토리]