본문 바로가기
반응형

알고리즘312

BOJ 2609 : 최대공약수와 최소공배수 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2609 두 수 A, B의 최대공약수가 G라면 A = a * G, B = b * G로 정의할 수 있다. 그러면 최소공배수는 a * b * G = A * B / G 가 된다. 최대공약수는 유클리드 호제법으로 구할 수 있다. A % B = R이라고 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. (A ≥ B) 즉, B가 0이 아닌 경우 gcd(B, A % B)를 구한다. 이 과정을 B가 0이 되는 경우에 A를 return하면 된다. 최소공배수의 경우 A * B / G의 경우 A * B 연산에 의해 overflow가 발생할 수 있다. 따라서 나누기를 먼저해서 (A / G * B) overflow를 방지한다. #include int.. 2021. 5. 5.
SWEA 4013 : 특이한 자석 (모의 SW 역량테스트) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 특이한 자석 링크  풀이는 BOJ 14891 : 톱니바퀴 (삼성 SW TEST A형)를 참고하자. input 순서가 바뀌었고, 출력 방식만 다르다.#include #define MAX (100 + 20)int T;int wheel[5][10];int list[6];int number[MAX];int direct[MAX];int N;void input(){ scanf("%d", &N); for (int number = 1; number = 2; index--) { wheel[number][index] = wheel[number][index - 1]; } wheel[number][1.. 2021. 5. 5.
SWEA 4014 : 활주로 건설 (모의 SW 역량테스트) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 활주로 건설 링크  풀이는 BOJ 14890 : 경사로 (삼성 SW TEST A형)를 참고하자.tc가 여러 개이고 출력 방식만 변경되었다.#include #define MAX (100 + 20)int T, N, L;int MAP[MAX][MAX];int TMAP[MAX][MAX];void input(){ scanf("%d %d", &N, &L); for (int r = 0; r b) ? a - b : b - a;}int isFlat(int* arr, int start, int end){ int value = arr[start]; for (int i = start + 1; i 1) retu.. 2021. 5. 2.
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 21611 : 마법사 상어와 블리자드 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/21611  달팽이 배열을 만들고, 그 배열에 해당하는 index를 관리하면 해결할 수 있다. 아래는 변수에 대한 설명이다. MAP : 입력에 주어지는 2차원 배열snail : 달팽이 배열의 index 관리를 위한 2차원 배열indexArray : indexArray[i] = i로, 달팽이 배열의 index를 만들기 위한 배열indexValue : 달팽이 배열을 1차원 배열로 볼 때의 값을 저장한 배열icnt : indexValue 배열의 sizebombCount : 폭발한 1 ~ 3번 구슬의 개.. 2021. 5. 1.
BOJ 1913 : 달팽이 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1913  배열의 중심 좌표에서 달팽이 모양의 배열을 만들면 된다. 먼저 배열의 중심 좌표 (sr, sc)는 N / 2 + 1이 된다.문제의 예시 7인 경우 (4, 4) 부터 배열이 시작됨을 알 수 있다.sr = sc = N / 2 + 1; N = 5인 경우 규칙을 살펴보자.먼저 처음 1 → 2의 방향은 ↑ 방향이 된다.달팽이는 ↑, →, ↓, ← 로 방향을 반복해서 바꾼다.따라서, dr, dc는 아래와 같이 정의할 수 있다./* ↑, →, ↓, ← */int dr[] = { -1, 0, 1, 0 };int dc[] = { 0, 1, 0, -1 }; 방향이 두 번 바뀔 .. 2021. 4. 30.
SWEA 5644 : 무선 충전 (모의 SW 역량테스트) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 무선 충전 링크  MAP의 좌표를 BC로 나타내자.BC 구조체의 cnt는 MAP[r][c]에서 중복된 BC의 개수이고, bc배열은 BC의 번호가 된다.각 BC의 성능은 power배열에 저장한다.typedef struct st1{ int bc[10]; int cnt;}BC;BC MAP[MAX][MAX];int power[10]; 사용자 A, B의 좌표를 저장할 구조체 배열과 주어진 입력을 기록할 direction 배열을 만든다.typedef struct st2{ int r; int c;}RC;RC personA, personB;int directionA[100 + 20];int direct.. 2021. 4. 30.
BOJ 21610 : 마법사 상어와 비바라기 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/21610  구름의 좌표를 저장할 RC 구조체가 필요하다.최초 구름 4칸을 입력하고, cloud count = ccnt를 4로 설정해두자.그리고 MAP의 좌표는 (1, 1)부터 받는다.#define MAX (50 + 5)int N, M;int MAP[MAX][MAX];typedef struct st{ int r; int c;}RC;RC cloud[MAX * MAX] = { 0 };int ccnt;void input(){ scanf("%d %d", &N, &M); for (int r = 1; r 방.. 2021. 4. 30.
BOJ 21609 : 상어 중학교 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/21609  무지개 블록, 검은색 블록, 그리고 빈칸을 define하자.보통 배열의 빈칸은 0을 쓰지만, 여기에서는 무지개 블록이 존재하므로 -2로 define한다. 좌표를 저장하기 위한 RC 구조체와 블록 그룹의 우선순위를 결정할 BLOCK_INFO 구조체를 만든다. 그리고 MAP 주변을 검은색 블록으로 벽을 만들고, (1, 1)부터 입력을 받도록 하자.#define MAX (20 + 5)#define RAINBOW (0)#define BLACK (-1)#define EMPTY (-2)int N.. 2021. 4. 29.
반응형

티스토리툴바