본문 바로가기
반응형

알고리즘312

BOJ 20055 : 컨베이어 벨트 위의 로봇 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/20055  시뮬레이션 문제이므로 그대로 구현한다. BELT 구조체는 현재 belt의 번호, 로봇이 있는 경우 로봇의 번호, 그리고 내구도 A가 저장된다.robot의 번호는 벨트가 최대 200개이고 내구도가 1000이므로, 20만개 정도로 메모리를 잡는다.robot[i] = i번째 로봇이 현재 있는 belt의 번호이다.#define MAX (100 + 20)int N, K;typedef struct st{ int number; int robotNumber; int A;}BELT;BELT belt[.. 2021. 4. 10.
BOJ 1715 : 카드 정렬하기 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1715 카드 비교 횟수를 줄이기 위해서는 가장 작은 수의 두 카드를 비교해야한다. 그리고 카드를 합친다. (+ 횟수를 누적한다.) 그러면 다시 남은 카드(+ 합친카드 포함) 중에서 가장 작은 수의 두 카드를 비교해야한다. 따라서, 우선순위 큐를 이용한다. 가장 작은 두 카드는 두 번 pop하면 얻을 수 있고, 합친 카드를 우선순위 큐에 넣어도 우선순위 큐를 두 번 pop하면 가장 작은 두 카드를 구할 수 있다. #include int N; int heap[100100]; int hn; int pop(int* heap, int& hn) { int tmp, ret; ret = heap[1]; heap[1] = heap[hn]; heap[h.. 2021. 4. 9.
BOJ 19238 : 스타트 택시 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/19238 문제를 자세히 읽어서 아래의 조건을 파악하는 것이 핵심이다. 1) 승객의 출발지는 모두 다르지만, A 승객의 도착지와 B 승객의 출발지가 같을 수 있다.2) 승객의 출발지나 도착지가 벽으로 막혀서 찾을 수 없는 경우를 고려해야 한다. 먼저 구조체 3개가 필요하다. RC : 좌표 저장 구조체PEOPLE : 1 ~ M번 승객의 출발지와 도착지, 그리고 check를 이용하여 탑승 여부를 확인하는 구조체INFO : 택시가 가장 가까운 승객을 찾을 때, 승객의 번호와 거리를 저장할 구조체#def.. 2021. 4. 8.
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 19237 : 어른 상어 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/19237  시뮬레이션 문제는 그대로 구현만 하면 된다. 먼저, MAP에는 number, current, time이 필요하다.number는 자신의 냄새를 찾기 위해 사용하고, current는 실제 현재 MAP에 있는 상어의 번호이다.그리고 time은 냄새의 유효시간이다. SHARK에는 상어의 좌표 (r, c), 방향, 방향에 대한 우선순위 2차원 배열, 생존 여부가 필요하다.typedef struct st1{ int number; int current; int time;}INFO;INFO MAP[.. 2021. 4. 6.
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.
최적화) 삼성 C형 샘플 문제 : 블록 부품 맞추기 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크삼성 C형 전체 링크 블록 부품 맞추기 문제를 더 최적화 해보자. 아래의 makeBlock에서 코드를 하나씩 지워보며 시간을 재보면 sort에서 비용이 많이 드는 것을 알 수 있다.int makeBlock(int module[][4][4]){ register int i, sum; bcnt1 = bcnt2 = mcnt1 = mcnt2 = 0; for (i = 0; i  따라서, 정렬 후 이분 탐색으로 hashing된 블럭을 찾지말고, hash table에 블럭을 저장하도록 하자.블럭의 hashing된 값의 최대 크기는 0x2222222222222222이므로 그래도 저장하기에는 너무 큰 값이다.따라서 PRIME으로 나눈 나머.. 2021. 4. 3.
BOJ 19236 : 청소년 상어 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/19236  아래와 같이 FISH 구조체를 선언하여 좌표와 방향, 그리고 죽었는지 살았는지 체크하는 dead를 정의하자.상어의 이동을 쉽게 종료하기 위해 MAP 주변은 -1로 벽을 만들고, (1, 1)부터 입력을 받자.MAP에는 물고기의 번호만 저장하고, 그 물고기 번호로 fish 배열에서 물고기의 정보를 찾는다.int MAP[6][6];typedef struct st2{ int r; int c; int dir; int dead;}FISH;FISH Fish[17];void input(){ for .. 2021. 4. 3.
BOJ 1644 : 소수의 연속합 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1644 N이 4,000,000으로 매우 크므로, 매번 소수를 판단하는 것은 비효율적이다. 따라서, 소수의 판단은 에라토스테네스의 체를 이용한다. int N; int prime[4000000 + 50000]; int primeSet[4000000 + 50000]; int pcnt; void eratos() { prime[1] = 1; for (int i = 2; i * i 2021. 4. 2.
반응형

티스토리툴바