본문 바로가기
반응형

알고리즘312

BOJ 6588 : 골드바흐의 추측 알고리즘 문제 전체 링크 www.acmicpc.net/problem/6588 어떤 숫자가 소수의 합으로 이루어져 있는지 판단해야 한다. 매번 소수 판단 함수를 사용하면, 비용이 많이 들어 time out이 나기 때문에, 주어진 n = 1000000이하의 수에 대해 모두 소수인지 미리 구해둔다. 즉, 에라토스테네스의 체를 이용하여 소수를 먼저 만든다. 그리고 primeNumber에는 prime을 check하여 실제 소수 값을 순서대로 적어둔다. 주어진 요구사항은, n을 만들 수 있는 방법 중 b - a가 가장 큰 값을 출력해야 하므로, 가장 작은 소수 2, 즉 primeNumber[st = 0]부터 시작하면서 n - primeNumber[st]가 소수인지 판단한다. primeNumber[st]가 소수이고 .. 2021. 3. 16.
BOJ 1406 : 에디터 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1406 참고 - BOJ 5397 : 키로거 stack을 2개 이용하면 에디터의 문자열을 쉽게 관리할 수 있다. 먼저 초반에 abcd가 입력되었다고 하자. 커서는 바로 d의 옆에 존재한다. (sp1 = 4) → abcd| 이제 P e 명령어에 의해 e가 추가되었다고 하자. stack1의 크기를 늘려주면서 e를 넣어주면 된다. (sp1 = 5) stack1[sp1++] = 'e'; → abcde| 이제 L 명령어에 의해 왼쪽으로 옮긴다고 하자. 왼쪽으로 옮기는 것은, 문자열은 여전히 abcde 이지만 커서는 d 뒤에 위치하게 된다. 따라서 커서의 뒷부분을 stack2로 옮겨준다. (sp1 = 4, sp2 = 1) stack에서 가장 나중에.. 2021. 3. 15.
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.
Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 (2) : 최적화 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 B형 전체 링크 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경 Indexed Priority Queue, Heap - 삭제 구현, 최적화 이전 글에서는 우선순위 큐의 임의 원소 삭제에 O(NlogN)의 비용을 O(N) + O(logN) ≒ O(N)으로 줄였다.이제 memoization을 이용하여 O(N) + O(logN)을 O(1) + O(logN) ≒ O(logN)으로 줄여보자.아이디어는 다음과.. 2021. 3. 13.
Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경 Indexed Priority Queue, Heap - 삭제 구현 B형에서는 우선순위 큐를 이용해 문제를 풀어야 하는 경우가 많다.우선순위 큐를 쓰면 임의의 값을 push해도 정렬을 유지할 수 있고,가장 우선순위가 높은 값을 제거해도 정렬을 유지할 수 있다.하지만 우선순위 큐를 쓰면 될 것 같은데, 애매한 상황이 하나가 있다.우선순위는 낮.. 2021. 3. 13.
BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/11866www.acmicpc.net/problem/1158 참고- BOJ 10845, 18258 : 큐, 큐2- BOJ 1168 : 요세푸스 문제 2  요세푸스 문제 0은 요세푸스 문제보다 K, N 값만 다르다. MAX 값을 5000이상으로 잡으면 두 문제 모두 풀 수 있다. 큐 기본 문제를 풀면 큐의 구현은 아래와 같다. 큐의 크기   :  wp - rp큐의 pop   :  queue[rp++]큐의 push :  queue[wp++] 먼저 사람들을 큐의 순서대로 넣는다. 예제의 경우는 1 2 3 4 5 6 7 이 큐에 들어간다. K 번째 사람을 제거하기 위해 K - 1번.. 2021. 3. 13.
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.
해시 응용 : 2차원 배열 탐색 삼성 B형 전체 링크 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 아래와 같은 15x15 2차원 배열에서 오른쪽의 4x4 조각이 총 몇 개 있는지 찾아보자. 실제 B형 문제라면, 아래의 코드에서 findPiece 함수를 만들면 된다. #include int N = 15; int M = 4; char MAP[15][15] = { { 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, }, { 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, }, { 0, 0, 1, 0, 0.. 2021. 3. 9.
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.
반응형

티스토리툴바