본문 바로가기
반응형

알고리즘312

BOJ 20920 : 영단어 암기는 괴로워 (우선순위 큐 갱신 + Hash Table) 삼성 B형 전체 링크 www.acmicpc.net/problem/20920 단어를 저장하기 위해 해시 테이블을 사용한다. 회사에 있는 사람에서는 해시 테이블을 이용해 단어를 저장하고, 정렬하였다. 마찬가지로 외워야할 단어를 저장하고, count한 다음에 정렬해도 된다. 하지만, 여기에서는 우선순위 큐를 갱신하는 방법으로 문제를 풀어보겠다. 먼저 위에서 요구하는 우선순위를 보자. 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 위의 우선순위에서 단어를 입력받을 때, heap에서 해당 단어의 횟수를 증가시킬 필요가 있다. 우선순위 큐를 이용하여 단어의 수를 update해보자. 단어를 저장하고, 저장된 단어의 있는지 체크.. 2021. 3. 21.
BOJ 2696 : 중앙값 구하기 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2696 문제의 원리는 가운데를 말해요와 같다. 차이점은 매 tc마다 heap을 초기화 그리고 최초 입력을 받고 홀수 번째 입력부터 가운데 값을 출력 한 줄에 10개씩 출력 이다. #include int T, M; int minHeap[100100]; int minHn; int maxHeap[100100]; int maxHn; int maxPop(int* heap, int& hn) { int tmp, ret; ret = heap[1]; heap[1] = heap[hn]; heap[hn--] = -10001; for (int i = 1; i * 2 heap[i * 2] && heap[i] > heap[i * 2 + 1]) break; el.. 2021. 3. 20.
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.
포인터의 크기 (Size of Pointer) - 삼성 SW 역량 시험 환경 삼성 C형 전체 링크 보통 visual studio 환경에서 포인터의 크기는 4byte다. 아래의 코드를 확인해보자. #include int main() { putchar('\n'); printf("char : %d\n", sizeof(char)); printf("short : %d\n", sizeof(short)); printf("int : %d\n", sizeof(int)); printf("long int : %d\n", sizeof(long long int)); putchar('\n'); printf("char* : %d\n", sizeof(char*)); printf("short* : %d\n", sizeof(short*)); printf("int* : %d\n", sizeof(int*)); pr.. 2021. 3. 20.
BOJ 4913 : 페르마의 크리스마스 정리 알고리즘 문제 전체 링크 www.acmicpc.net/problem/4913 1,000,000의 크기의 수를 매번 소수 판단할 수 없으므로 에라토스테네스의 체를 이용하여 메모해둔다. 그리고 매번 L과 U에 포함된 소수의 개수와 소수 중 제곱수의 수를 셀 수 없으므로 아래와 같이 메모한다. #define MAX (1000000) int L, U; int prime[MAX + 100]; int primeSum[MAX + 100]; int squreSum[MAX + 100]; int main() { makePrime(); /* 에라토스테네스의 체 */ squreSum[2] = primeSum[2] = 1; for (int i = 3; i = 1 : L이 자연수인 경우 (U는 항상 L보다 크다) 2) L이 음수.. 2021. 3. 19.
BOJ 18139 : Rush Hour Puzzle (해시, 2차원 배열 탐색) 삼성 B형 전체 링크 www.acmicpc.net/problem/18139 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 내용을 번역해서 요약하면 아래와 같다. 1) 6 x 6 board에서 자동차가 최대 10개 존재한다. 2) 자동차는 1칸씩 움직이며, 길이가 2 또는 3이다. 3) 1번 자동차가 exit로 탈출해야 한다. 4) exit는 항상 3번째 줄의 오른쪽 끝이다. 따라서 1번 자동차는 항상 3번째 줄에 가로로 존재한다. 5) 최대 10칸까지 움직인다. 그 이상 움직여도 1번 자동차가 exit로 탈출 못하면 -1을 출력한다.. 2021. 3. 18.
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 7569 : 토마토 (3차원) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/7569  BOJ 7576 토마토는 2차원에서 토마토가 퍼져나갔다.이번 문제는 3차원에서 토마토를 만들어가면 된다. 2차원에서는 4방향으로 토마토를 큐에 담았지만,3차원에서는 좌표의 높이(h)에 대해 위, 아래 토마토를 추가해주면 된다.즉, 총 6방향으로 BFS가 퍼져 나간다./* 순서대로 왼쪽, 위, 오른쪽, 아래 */int dr[] = { 0, -1, 0, 1 };int dc[] = { -1, 0, 1, 0 };void BFS(){ for (int h = 1; h rp) { QUEUE out = queue[rp++]; for (int i = 0; i  그리고 inp.. 2021. 3. 17.
BOJ 7576 : 토마토 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/7576  미로 탐색 문제에서 BFS를 이용하여 거리를 계산하였다. 같은 방법을 토마토 문제에서 적용할 수 있다.토마토를 모두 넣고 미로 탐색과 같은 방식으로 BFS를 적용하면, 토마토가 상자를 꽉 채우게 된다.토마토가 상자를 꽉 채우는 것은.각 토마토가 상자에서 최소로 가능 경로를 모든 토마토에 대해 실행하면 된다. 다음과 같은 5 x 5 상자(MAP)에 토마토가 있다고 가정하자.편의상(경계 조건을 신경쓰지 않기 위해) MAP의 주변은 -1로 만든다. 이제 모든 토마토를 queue에 담는다. 참고로 토마토 문제의 경우는 미로 탐색과는 달리 visit이 필요가 없다.상자.. 2021. 3. 16.
반응형

티스토리툴바