복습용 블로그

www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 케빈 베이컨의 6단계 법칙이라는 유명한 법칙이다. 세상 모든 사람은 6단계 안으로 만날 수 있다는 것이다. 문제는 간단하다. 사람들이 숫자로 주어지고, 사람들의 관계가 주어졌을 때 케빈 베이컨 수가 가장 적은 사람을 고르는 문제이다. 케빈 베이컨 수는 사람들 사이의 최소 링크 수의 합이다. 예를 들어, 사람들 사이의 관계가 (1,3), (1,4), (4,5), (..

www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 거친 제목의 문제 이름에 이끌려 들어가보았지만, 쉬운 문제였습니다. (그렇지만 틀렸었다.) 듣도 못한 사람을 listen 벡터에 넣었습니다. 처음에는 listen 벡터 외에 see 벡터를 추가하여 보도 못한 사람들의 벡터를 만들어 이분 탐색을 진행하였지만, 시간 초과가 났습니다. (시간 초과가 이것 때문은 아니고, 처음에는 이분 탐색 알고리즘을 직접 구현했었지만, 시간초과나서 그냥 algorithm 라이브러리..

www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 단순히 계산하면 n개의 숫자 사이에 n-2 개의 +, - 가 존재합니다. (마지막 부호는 = ) 그러므로 $O(2^n)$ 이지만 n=100이므로 시간초과가 날 게 뻔해보입니다. 그러므로 DP를 이용해 봅시다. 상근이는 0~20까지의 숫자만 알고 있으므로 possible 배열을 이용하여 0~20에 다음 숫자를 계산했을 때 가능하면 dp 경우를 더해줍니다. 그 값을 dp배열에 복사하여 dp배열 내에서 0보다..

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 오랜만에 수학 문제를 풀고 싶어서 도전했지만 수학이라기보단 노가다 문제였습니다. 문제는 어렵지 않다. 두 박스가 한 점에서 만나는지 선으로 만나는지 교차하는지 (내부에 포함되는 것 포함) 만나지 않는지를 나누어 계산하면 됩니다. 상대적으로 정답률이 낮은 이유는 아마 여러 경우 중 놓친 것이 있거나 했기 때문일 것입니다. (나도 몇 번 틀렸다.) 구조체를 이용하여..