본문 바로가기
반응형

알고리즘/[ADV] 삼성 SW 역량 테스트 A형117

BOJ 17779 : 게리맨더링 2 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/17779  (x, y) → (r, c)로 설명한다. (r, c)를 기준으로 마름모를 만드는 것이 핵심이다.(r, c)를 기준으로 d1과 d2를 늘려가면서 선거구를 만든다.이때, 범위를 체크하는 것보다 벽 = -1 을 만나면 종료하도록 구현하면 편하다. 따라서 input에서 A의 주변을 -1로 만들고 (1, 1)부터 입력을 받자.#define MAX (20 + 5)int N;int MAP[MAX][MAX];void input(){ scanf("%d", &N); for (int r = 0; r  모.. 2021. 3. 20.
BOJ 17142 : 연구소 3 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/17142 연구소 문제와 다른 점은 벽을 세우는 것이 아니고, 바이러스를 M개 선택해야하는 것이다. 바이러스의 선택 → DFS 경우의 수 : 조합 문제 바이러스의 확산 → 토마토 문제를 같이 조합해서 풀면 된다. 먼저 문제를 풀기 편하게 input을 받으면서 MAP을 재변경하자.벽(1)과 바이러스(2)를 그대로 두면, 바이러스가 몇초 뒤에 퍼지는지 셀 때, 구분하기 까다롭다.따라서 벽은 -1로, 바이러스는 -2로 표시하자.또한, 바이러스는 따로 배열에 저장해두자.typedef struct st{ .. 2021. 3. 17.
BOJ 17140 : 이차원 배열과 연산 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/17140  시뮬레이션 문제는 그대로 구현하면 된다. 주의할 점은 최적화를 하다가 0이 나오면 종료하면 안된다는 점이다.아래와 같은 배열의 경우 도중에 0이 있어도 다음에 숫자가 있을 수 있다. (예제 1의 4번째 연산 결과)또한 배열의 row와 column이 반드시 늘어나지 않는다.예를 들어 1만 5개 있는 경우는 배열의 길이가 5에서 [1, 5]로 2로 줄어들기 때문이다. 이 점을 잘 이해하고 구현해야한다.먼저 calculate 함수를 설계해보자.100번까지 답이 나오지 않을 경우, 101번째.. 2021. 3. 14.
BOJ 17143 : 낚시왕 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/17143 시뮬레이션 문제는 그대로 구현하면 된다. 아래의 내용을 구현해보자. 1. 낚시왕이 오른쪽으로 한 칸 이동한다.2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.   상어를 잡으면 격자판에서 잡은 상어가 사라진다.3. 상어가 이동한다. int main(void){ int ans; input(); ans = 0; for (int c = 1; c  1. 낚시왕의 이동은 main에서 for문을 이용하여 이동한다.2. catchShark, 낚시왕이 상어를 잡을 때, 상어.. 2021. 3. 12.
BOJ 17144 : 미세먼지 안녕! (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/17144 시뮬레이션 문제는 시키는 대로 구현하면 된다. 먼저 diffusion 함수를 만들어보자. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.(r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.확산되는 양은 Ar,c/5이고 소수점은 버린다.(r, c)에 남은 미세먼지의 양은 Ar,c - (Ar,c/5)×(확산된 방향의 개수) 이다.인접한 네 방향으로 확산은 되지만, 공기청정.. 2021. 3. 8.
BOJ 16236 : 아기 상어 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/16236  아기 상어 구조체는 좌표와 몇 마리의 물고리를 먹었는지, 그리고 현재의 크기가 필요하다.typedef struct st1 { int r; int c; int eat; int size;}SHARK;SHARK babyshark; input을 받으면서 9인 경우에 아기 상어 구조체를 초기화 해주자.void input(){ scanf("%d", &N); for (int r = 0; r  아기 상어는 먹을 수 있는 물고기가 있는 경우, 움직여서 물고기를 먹어야 한다. 전체 코드 구조를 알아보자.. 2021. 3. 6.
BOJ 16235 : 나무 재테크 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/16235 시뮬레이션 문제는 시키는대로 잘 구현하면 된다. 봄 : 나무의 나이만큼 양분 감소, 나무의 나이 1 증가, 어린 나무부터 양분 획득, 양분 부족시 사망.여름 : 죽은 나무가 양분으로 나이 / 2 만큼 추가가을 : 8방향 번식 나이 1의 나무가 생성겨울 : 양분 추가 문제의 핵심은 나무가 중복될 수 있다는 것이다.그리고 어린 나무부터 양분을 획득한다 조건에서 정렬이 필요할 것 같다. 무작정 구현했더니, time out이 나오게 되었다./* time out */void spring(){ /.. 2021. 3. 4.
BOJ 16234 : 인구 이동 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/16234  2차원 탐색은 보통 BFS를 이용한다.2차원 MAP 탐색 기본 원리는 단지번호붙이기를 풀어보자. 단지번호붙이기와 다른 점은, queue에 담는 조건이 인접한 A[r][c]의 차이가 L 이상 R 이하인 경우로 바뀐 것이다.어쨌든, 조건을 만족하는 경우 queue에 담으면서 영역을 확장해 나가면 된다. 그리고 선택된 영역을 visit으로 check해서 다음 BFS에 선택되지 않도록 한다. 먼저 r, c, visit배열에 대해 BFS로 영역을 만드는 하는 함수를 만들어보자./* 순서대로 왼.. 2021. 3. 2.
BOJ 5373 : 큐빙 (삼성 SW TEST A형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/5373 실제 큐브를 만들어서 직접 돌리면 된다.시계/반시계 방향에 대해서는 아래처럼 구현하면 된다.if (clockwise == '+') { for (int r = 0; r 실제 시험장에서 종이에 큐브를 그려가면서 어떤 규칙이 있는지 확인해보는 것이 좋다. 그리고 U / D / F / B / L / R의 경우는 반대편의 면을 제외하고 변경하면 된다.예를 들어 U인 경우 UP과 DOWN을 제외하고 하나씩 변경하면 된다.물론 미리 원본 copy를 복사해둬야 한다.case UP: if (clockwise.. 2021. 2. 27.
반응형

티스토리툴바