본문 바로가기
728x90

알고리즘339

[python] 백준 7795 먹을 것인가 먹힐 것인가 https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제 해결 모든 원소를 1대1로 비교해서 계산하는 것은 너무 비효율적이라는 생각이 든다. 정렬을 이용해서 A와 B를 오름차순으로 정렬하고, $i \in {0,1,2,3, . . .n-1} $ $j \in {0,1,2,3, .. m-1}$ 인 임의의 $i, j$에 대해서 A[i] > B[j]이면 A[i+1] > B[j]임을 생각을 하면 좋다. 만약.. 2023. 9. 14.
[python] 백준 20040 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제 해결 1~m 번호까지 차례대로 원하는 두 점을 연결한다.(중복 불가) 어 때 몇 번째 번호에서 사이클이 만들어지는지 구하는 문제이다. 처음에는 하나의 선분이 그어질 때마다 사이클이 존재하는지 직접 돌려야되나 생각했다. 하지만 유니온 파인드(union find)를 이용하면 계산양을 줄이고 쉽게 사이클이 만들어지는지 확인할 수 있음을 알 수 있었다. 그림으로 이해하면 너무 쉽다. CODE .. 2023. 9. 11.
[python] 백준 7490 0 만들기 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 문제 해결 처음 보았을 때 많이 당황스러운 문제였다. 1부터 N까지 덧셈, 뺄셈, 이어붙이기로 각각 계산 따라서 1부터 시작하여 +, -, 이어 붙이기 중 한 가지를 선택한 후 다음 수 2를 붙인다. 이와 같은 일을 N번 반복하므로 재귀를 이용하여 풀 생각을 한다. 필요한 변수는 sum: 1부터 n-1까지 합 (후에 1부터 N까지 합이 0이 되었을 때만 확인하면 되므로) sign: 1이면 덧셈, -1이면 뺄셈, sign 그대로이면 이어 붙이기로 판별.. 2023. 9. 7.
[python] 백준 3055 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 해결 BFS를 이용하여 푸는 문제라는 것은 쉽게 알 수 있다. 문제는 물과 고슴도치가 동시에 이동한다는 것이다. 그러나 운이 좋게 문제를 잘 보면 물이 올 지역에 고슴도치가 이동할 수 없다고 나오므로 물부터 이동시킨 후 고슴도치를 이동시키면 된다. 고슴도치가 더이상 움직이지 못하면 탈출하지 못하는 것이고 그전에 탈출구를 찾으면 탈출하는데 걸리는 시간을 출력하면 된다. CODE import sys inpu.. 2023. 9. 4.
728x90