컴공생 일상 블로그 컴공생 일상 블로그

일명 물 채우기 BFS 문제 물을 담아두기 위해서, 테두리부터 물을 흘려 보낸다는 아이디어가 필요하다. - 알고리즘 0. 한 번 추가됬던 칸은 check. 1. 테두리를 우선순위 큐에 추가 2. 우선순위 큐에서 하나씩 pop 하면서, 주변 탐색 3. 주변 탐색 시, 더 낮은 높이면 해당 칸으로 나아가 탐색을 진행하고, 아니면 우선순위 큐에 추가 4. 탐색 시에는 처음에 우선순위 큐에서 pop 한 칸의 높이를 기준으로 탐색 - 예시 문제 1. 수영장 사장님 : https://www.acmicpc.net/problem/15730 2. 물 채우기 : https://www.acmicpc.net/problem/2276 - 수영장 사장님 Code #include #include #include #include us..

- 문제 https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net - 문제 설명 저번에 풀었던 미세먼지 안녕! 과 비슷한 문제이다. 문제를 꼼꼼히 읽고, 시간을 들여, 구현만 잘 해주면 되는 문제이다. 탐색, 구현, 시뮬레이션 1. 온풍기들이 모두 작동되고, 각 칸 마다 더해줘야하는 온도를 구함 - 온풍기의 방향에 유의 - 온풍기가 작동하는 영역을 DFS로 탐색하면서 각 칸 마다 더해줘야하는 온도 계산 - 벽으로 막혀 있는 경우를 고려하여 탐색 2. 각..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net - 에라토스테네스의 체 알고리즘 N+1크기의 배열을 선언한다. 배열을 모든 요소를 0으로 초기화한다. 배열의 인덱스가 2의 배수인 모든 칸을 1로 초기화한다. 그 다음수인 3을 선택한다. 배열의 인덱스가 3의 배수인 모든 칸을 1로 초기화한다. 그 다음 소수인 5를 선택한다. 배열의 인덱스가 5의 배수인 모든 칸을 1로 초기화한다. 위 내용을 N까지 반복한다. void func(int n)..

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net '-' 가 나오면, 그 뒤는 모두 빼기가 가능하다. #include int main() { int set=0; char op; int sum, next; scanf("%d", &sum); while (1) { scanf("%c", &op); scanf("%d", &next); if (op == '-') set = 1; else if (op != '+') break; if (set==1) su..

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 좌표 정렬 하는 문제이다. #include int main() { int N; scanf("%d", &N); int arr[N][2]; int i,j; for(i=0; i

https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net .. 택시 기하학에서 원은 마름모 형태가 된다. 원 : PI * R * R 마름모 : 2 * R * R #include #define PI 3.14159265358979 int main(){ float R; scanf("%f", &R); printf("%.6f\n", PI*R*R); printf("%.6f\n", 2.0*R*R); return 0; }

www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 최소값만 구해내면 되기 때문에, 배열을 오름차순으로 정렬한뒤 for(i=0; i key){ arr[j+1]=arr[j]; arr[j]=key; } else break; } } } int main() { int N; int arr[1001]; int i; scanf("%d", &N); for(i=0; i