반응형 알고리즘/[ADV] 삼성 SW 역량 테스트 A형 상시9 BOJ 17472 : 다리 만들기 2 (A형 상시) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17472 아래의 순서대로 구현한다. 1) BFS를 이용해 섬을 구분한다.2) 섬과 섬 사이의 거리를 구한다.3) 섬의 개수 N에 대해, 다리 N - 1개를 선택하여 모두 연결되어 있다면, 다리의 길이를 갱신한다.구조체는 좌표를 기억하기 위한 RC 구조체가 필요하다.MAP 주변은 모두 -1로 처리하고 (1, 1)부터 입력을 받는다.connect 배열은 섬과 섬 사이의 거리를 저장하기 위한 배열이다.섬과 섬 사이의 거리는 가장 가까운 거리만 필요하므로, 큰 값(WORST = 0x7fff000.. 2021. 5. 1. BOJ 17471 : 게리맨더링 (A형 상시) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17471 A형에서 그래프는 2차원 배열로 만들면 대부분 충분하다. 제시된 N이 매우 작기 때문이다.(N이 매우 큰 그래프는 링크드 리스트를 이용해 그래프를 만들어야 한다.) 만약 1번 구역과 2번 구역이 인접하다면, MAP[1][2] = MAP[2][1] = 1, 그렇지 않다면 0이 된다.people 배열에는 구역의 인구 수를 저장한다.#define MAX (10 + 5)int N;int MAP[MAX][MAX];int people[MAX];void input(){ scanf("%d", &N).. 2021. 4. 28. BOJ 17406 : 배열 돌리기 4 (A형 상시) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17406 MAP은 (1, 1)부터 input을 받고, COMMAND 구조체에 (r, s, c)를 저장한다.#define MAX (50 + 10)int N, M, K;int MAP[MAX][MAX];typedef struct st{ int r; int c; int s;}COMMAND;COMMAND command[10];void input(){ scanf("%d %d %d", &N, &M, &K); for (int r = 1; r 명령에 대한 순서를 임의로 정해서 배열 A의 최솟값을 구해야하.. 2021. 4. 24. BOJ 3954 : Brainf**k 인터프리터 (A형 상시) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/3954 명령어를 쉽게 판단하기 위해 아래와 같이 define하자.typedef unsigned char uc;#define MAX (50000000)#define DECREASE ('-')#define INCREASE ('+')#define POINTER_LEFT ('')#define POINTER_RIGHTJUMP ('[')#define POINTER_LEFTJUMP (']')#define OUTPUT ('.')#define READ_AND_SAVE (',')#define MODULO (25.. 2021. 4. 21. BOJ 17281 : ⚾ (A형 상시) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17281 9명의 타자가 있고 1번 타자는 4번에 고정이므로, 8! = 40320번의 경우의 수에 대해 시뮬레이션을 하면 된다.9명 타자를 줄 세우는 방법은 N과 M (1) - 순열의 방법을 이용한다. input에서는 간단히 player의 결과를 저장한다.void input(){ scanf("%d", &N); for (int i = 1; i 먼저 1번 타자를 4번에 고정하면 경우의 수를 만드는데 처리해야할 코드가 추가되므로,1번 타자는 1번에 고정하고 2 ~ 9번 타자에 대한 경우의 수를 .. 2021. 4. 17. BOJ 17136 : 색종이 붙이기 (A형 상시) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17136 input에서 색종이 상태를 입력받고, 색종이의 개수 PAPER_COUNT에 저장해둔다.그리고 각 색종이의 최대 개수인 5를 MAX_PAPER[1~5]에 저장한다.#define MAX (10 + 10)int MAP[MAX][MAX];int PAPER_COUNT;int MAX_PAPER[10];void input(){ for (int r = 0; r DFS로 완전 탐색을 하기 위해 아래의 3가지 함수를 만든다. checkPaper는 (r, c) 좌표에 대해 색종이를 붙일 수 있는지 판.. 2021. 4. 14. BOJ 17135 : 캐슬 디펜스 (A형 상시) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/17135 먼저 궁수가 탐색해야할 우선순위를 구해보자.아래의 그림은 D = 1, 2, 3인 경우 궁수가 탐색해야하는 순서다.적이 가장 가까울 경우 가장 왼쪽에 있는 적을 공격한다고 하였으므로, 거리가 가장 가까운 앞을 보고, 그 다음 거리부터는 왼쪽/가운데/오른쪽 순서대로 탐색한다. D = 4인 경우, 규칙이 점점 보인다. 위의 탐색 순서를 궁수를 기준으로 r, c로 나타내면 아래와 같다. 좌표 r은 -1부터 시작해서 감소하다가 다시 증가한다.좌표 c는 처음엔 0이며, 그 다음 주기에는 -1.. 2021. 4. 11. BOJ 17070 : 파이프 옮기기 1 (A형 상시) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집)www.acmicpc.net/problem/17070 파이프는 오른쪽, 아래, 대각선으로만 진행하므로 방향을 3개 define한다.input에서는 MAP 주변에 벽을 세운다.#define MAX (16 + 5)#define RIGHT (0)#define DOWN (1)#define RIGHT_DOWN (2)int N;int MAP[MAX][MAX];void input(){ scanf("%d", &N); for (int r = 0; r (1, 1)과 (1, 2)에 항상 파이프가 가로로 시작하므로,MAP[1][1]과 MAP[1][2]에 .. 2021. 4. 8. BOJ 16637 : 괄호 추가하기 (A형 상시) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/16637 첫 번째 예시를 보자.연산자는 + * - * 로 총 4개이다. 순서대로 1, 2, 3, 4번째 연산자로 정의하자. 먼저 괄호 안에는 연산자가 하나만 들어있어야 하므로, 1번 연산자에 괄호를 만들면, 2번 연산자는 괄호가 불가능하다.→ (3 + 8) * 7 - 9 * 2 따라서 DFS로 아래의 경우의 수가 되도록 만든다. 0 0 0 0 → 괄호가 없는 경우0 0 0 1 → 4번 연산자에만 괄호를 만든 경우0 0 1 0 0 1 0 0 0 1 0 1 → 2번, 4번 연산자에 괄호를 만.. 2021. 4. 5. 이전 1 다음 반응형
