복습용 블로그

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 삼성 SW 기출문제로도 유명한 아기 상어 문제입니다. 상어 위치로부터 문제로부터 요구하는 물고기의 위치까지 최단 거리를 구하여 계속 더하면 되므로 bfs를 사용하였습니다. 처음에는 상어의 현재 위치에서 $n^2$개 중 먹을 수 있는 물고기를 체크하고, 이 물고기들을 bfs를 이용하여 최단 거리와 어떤 물고기를 먹을 지 구한 뒤 while문으로 동일하게 반복하였습니다. 그러니 $O(n^6)$이 되어 시간초..

www.acmicpc.net/problem/15973 15973번: 두 박스 표준 입력으로 두 박스의 정보가 한 줄에 하나씩 주어진다. 각 박스의 정보는 왼쪽 아래 꼭짓점 좌표 (x1, y1)과 오른쪽 위 꼭짓점 좌표 (x2, y2)로 구성되는데 이들 좌푯값 x1, y1, x2, y2 (x1 < x2, y1 < y2) www.acmicpc.net 오랜만에 수학 문제를 풀고 싶어서 도전했지만 수학이라기보단 노가다 문제였습니다. 문제는 어렵지 않다. 두 박스가 한 점에서 만나는지 선으로 만나는지 교차하는지 (내부에 포함되는 것 포함) 만나지 않는지를 나누어 계산하면 됩니다. 상대적으로 정답률이 낮은 이유는 아마 여러 경우 중 놓친 것이 있거나 했기 때문일 것입니다. (나도 몇 번 틀렸다.) 구조체를 이용하여..

www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 전형적인 bfs 문제입니다. 문제에서 한 가지 까다로운 조건이 있다면, 치즈 내부의 공기에는 치즈가 녹지 않는다는 것입니다. 그렇기 위해 공기가 치즈 내부에 있는가 외부에 있는가를 기준으로 녹는 위치를 정해야합니다. 녹는 방법은 치즈 블럭을 기준으로 상하좌우에 치즈 외부의 공기가 있는가 없는가만 알면 됩니다. 그렇기 때문에 bfs를 2번 이용하여 치즈 블럭 구분과 외부 공기를 구하였습니다. (모서리 부분에는 무조건 치즈..

소개글을 제외한 첫 글입니다! 첫 글인 만큼 가벼운 문제인 줄 알았던 문제를 풀어보겠습니다. (한 번 틀렸다.) 백준 1946 신입 사원 입니다. www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 제한시간은 2초이고 테스트 케이스는 최대 T=20, 지원자 수는 최대 N=100,000입니다. 문제를 풀기 위해 기존에 합격한 지원자들보다 새로운 지원자의 성적이 서류와 면접 모두 낮으면 떨어진다는 것을 알 수 있습니다. 처음에는 지원자 수를 고..