알고리즘 문제풀이/백준134 [백준 16236] 아기 상어 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net bfs를 사용하는 구현문제. 조건이 너무 많다. 1. 물고기가 있는 지 확인 2. 있다면 먹기 3. 여러 마리라면 우선순위가 있다. 가까운 물고기 -> 위쪽 -> 왼쪽 에 있는 물고기 먹기 4. 없으면 엄마 상어 부르기 이다. 물고기를 먹기 위한 조건은 크기보다 작은 경우에만 가능하다. 크기가 동일하면 지나가는 것만 가능 크기가 커지는 조건은 물고기를 크기만큼 먹었을 때 크기가 1만큼 커진다. 1 2 3.. 2020. 12. 26. [백준 1722] 순열의 순서 www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지 www.acmicpc.net n=20이기 때문에 백트래킹으로 전부 확인했다가는 tle가 뜨는 문제 순열의 개념과 dp를 사용해야 한다. 고등학교 수학 문제에 자주 등장하는 문제 중 하나인데 그 때의 풀이법을 살펴보자. n = 4이고 10번째 순열을 구하라 라는 문제가 있으면 1 2 3 4 : 4개의 숫자를 사용할 수 있고 앞자리 부터 차례로 3! 2! 1!을 계산해볼 것이다. k = 10가 3!보다 크다는 의미는 맨 앞.. 2020. 12. 25. [백준 17140] 이차원 배열과 연산 www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net map과 vector를 사용해서 풀었다. 1. row와 col 비교 row>= col이면 row따라 else 면 col따라 연산을 진행한다. 2. 연산 2-1. 연산을 진행할 때 등장횟수 측정을 위해 map을 사용했다. 각 row/col마다 map으로 등장횟수를 측정하고 vector에 담아서 map을 소트했다. vector v(m.begin(), v.end()); 2-2. map에 담는 과정에서 0.. 2020. 12. 23. [백준 1456] 거의 소수 www.acmicpc.net/problem/1456 1456번: 거의 소수 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. A의 범위는 10^14보다 작거나 같은 자연수이고, B는 A보다 크거나 같고, 10^14보다 작거나 같은 자연수이다. www.acmicpc.net 에라토스테네스의 체를 사용하면 되지만 소수 제곱을 확인하는 과정에서 long long으로 선언해도 오버플로우가 발생한다. 예를 들어 i =10^7이고, tmp = 10^14라면 tmp * i = 10^21을 확인할 때 계산 자체가 오버플로우기 때문이다. 따라서! if( i * tmp 2020. 12. 23. 이전 1 ··· 14 15 16 17 18 19 20 ··· 34 다음