알고리즘/삼성SW역량테스트기출
-
[백준 14889번 - 스타트와 링크] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 19. 20:12
백준 14889번. 총 n 명을 n/2 명씩 두 팀으로 나누고, 각 팀의 능력치 합을 구해서 차이를 최소로 하도록 하는 문제이다. 만약 각 팀에 3명씩 있고, 1,2,3번이 스타트팀, 3,4,5번이 링크팀이라면, 스타트팀 : S12 + S21 + S13 + S31 + S23 + S32 링크팀 : S34 + S43 + S35 + S53 + S45 + S54 가 된다. 사용한 알고리즘 - 백트래킹 순차적으로 탐색하면서 해당 맴버를 선택하거나/선택하지 않거나. 해서 함수를 호출하도록 했다. depth 가 n / 2 이 되면 호출을 멈추도록 재귀를 구현하였다. 그리고 거기서 두 팀 멤버 능력치의 차를 구해서 기존거보다 더 작으면 갱신해주었다. 완성된 코드 #include #include #include #inc..
-
[백준 14503번 - 로봇 청소기] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 19. 18:39
백준 14503번. 사용한 알고리즘 - bfs 방향을 설정하기가 조금 까다로웠던 문제.... 청소한 곳을 체크하기 위한 visited 배열을 두었다. 시작 지점을 큐에 넣고 bfs 시작. 1. 현재 지점의 visited 배열을 true로 2. 현재 방향을 기준으로 왼쪽 부터 차례대로 탐색한다. 나는 아예 배열을 따로 만들어서 현재 청소기가 바라보는 방향인 d에 따라서 탐색할 순서를 설정해줬다. 문제에서 주어진 d 의 순서도 왼쪽방향이면 이렇게 안해도 됐을 텐데.. d의 값은 오른쪽 방향으로 증가하고, 실제 인접한 부분 탐색은 반대 방향으로 해주어야 해서 그냥 배열 하나 더만들어서 편하게 했다. a~ d 까지는 문제에 주어진대로 그대로 알고리즘을 짜면 된다. 처음에는 그냥 청소한부분 map 값을 1로 만들..
-
[백준 14500번 - 테르로미노] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 19. 06:36
백준 14500번. 사용한 알고리즘 - bfs depth 가 4로 정해져있으니 bfs 풀어야겠다는 생각이 들었다. 그리고 테스트 해보니 빠뜨린게 있었는데..! ㅜ/ㅗ/ㅓ/ㅏ 모양은 따로 값을 계산해서 최대값인지를 체크해주어야 한다. bfs 를 위한 visited 배열을 만들었는데, 해당 배열을 dfs 함수의 인자로 넣어주니까 시간초과가 계속 나더라..(call by reference 로 해도..) 그래서 없애고 전역변수로 줬더니 맞았다. 그래도 시간이 빠듯한듯. dfs 풀면 대략 500 * 500 * 4 ^ 4 정도의 시간복잡도가 된다. 완성된 코드 #include #include #include using namespace std; int n, m; vector v; vector visited; int..
-
[백준 14499번 - 주사위 굴리기] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 19. 04:12
백준 14499번. 사용한 알고리즘 - 구현 - 시뮬레이션 문제에 전개도가 그려져 있는 것에 착안하여.. 전개도를 이용하여 풀어보기로 했다. 이렇게 주사위를 a[4], b[4] 배열에 저장해놓는다. 바닥면은 항상 a[1] (= b[1]) , 윗면은 a[3] (= b[3])로 고정하자. 명령이 1 => 오른쪽 2 => 왼쪽 3 => 위쪽 4 => 아래쪽 이다. 오른쪽으로 주사위를 굴리는 경우, 배열 a에 들어있는 숫자들을 왼쪽 방향으로 하나씩 밀어서 재저장한다. 왼쪽으로 주사위를 굴리는 경우, 배열a에 들어있는 숫자들을 오른쪽 방향으로 하나씩 밀어서 재저장한다. 위쪽으로 주사위를 굴리는 경우, 배열 b에 들어있는 숫자들을 아래쪽 방향으로 하나씩 밀어서 재저장한다. 아래쪽으로 주사위를 굴리는 경우, 배열 b..
-
[백준 12100번 - 2048(Easy)] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 18. 22:02
백준 12100번. https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 예전에 많이 했던 게임인데 반갑네.. 그 게임과는 다르게, 블록이 새로 추가되거나 하지는 않고, 주어진 블록들을 가지고 같은 숫자 만나면 합치고 합쳐서 최대 5번까지 이동했을 때 최대 숫자를 출력하는 문제이다. 사용한 알고리즘 - 시뮬레이션 - dfs - 구현 음.. 또 다 해봐야지.. 라는 생각밖에 안들었다. 백트래킹으로 promising 하지 않..
-
[백준 14501번 - 퇴사] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 18. 15:13
백준 14501번. 사용한 알고리즘 - dfs N이 최대 15이기 때문에, dfs 재귀로 시도를 먼저 해보았다. i번째 날부터 시작한다고 가정했을 때 dfs 를 호출한다. (총 N번 호출) 각 경우마다, 해당 날에 상담을 하고, 다음 상담 가능일부터~ N일 까지 dfs 를 호출한다. (N - 현재 날 - Ti 번 호출) 현재 날짜에 해당 상담을 하면 N일이 넘어가거나, N일이면 반환. 완성 코드 #include #include #include using namespace std; int n; vector v; int ans = 0; void dfs(int time, int curr_t, int result) { if (time + curr_t > n) { ans = (result > ans) ? resu..
-
[백준 14502번 - 연구소] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 18. 02:50
백준 14502번. 벽 3개를 추가로 세워서 바이러스가 퍼지지 않는 안전영역의 최대값을 구하는 문제이다. 사용한 알고리즘 - 브루트포스 - bfs 처음에는 벽 3개를 치는 경우의 수중 쳐낼 수 있는 가지수가 없나 생각을 해봤는데, 내 머리로는 도저히 떠오르지 않아서 그냥 다 구해보기로 했다. 3 = m || map[nx][ny] == 1 || map[nx][ny] == 2) { continue; } else { q.push(make_pair(nx, ny)); map[nx][ny] = 2; } } } } // 안전 영역 크기 구하기. for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { if (map[i][j] == 0) result++; } } retur..
-
[백준 13458번 - 시험 감독] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 17. 02:07
백준 13458번. 간단한 식을 세워 구할 수 있는 문제였다. 각 시험장을 돌면서, 최솟값은 1. 응시자의 수에서 1(=총 감독관)을 뺀 수를 C 로 나눈 만큼 더해주고, 나머지가 있다면 1을 더 더해주면 된다. B, C가 1이고, N이 백만, Ai가 각 백만 응시자수가 있다면, 정답이 약 백만*백만 = 일조 이므로, long long 타입으로 선언해줬다. 완성 코드 #include #include using namespace std; int main() { int n, b, c; vector a; scanf("%d", &n); for(int i = 0; i < n; ++i) { int tmp; scanf("%d", &tmp); a.push_back(tmp); } scanf("%d %d", &b, &c)..