본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[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.
[python] 백준 21939 문제 추천 시스템 Version 1 https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 문제 해결 Hash 맵을 통해 문제 번호를 알면 문제 난의도를 바로 알 수 있도록 매핑한다. 문제 난이도를 알면 그 난이도 문제 번호들을 알 수 있도록 int-list 매핑을 한다. recommend == 1일 때는 어려운 난이도부터 살펴보고 recommend ==-1은 쉬운 난이도부터 문제가 있는지 살펴보도록 구현한다. CODE import sys input = s.. 2023. 8. 30.
728x90