글 (463) 썸네일형 리스트형 [Python] 26076번 곰곰이의 식단 관리 2 https://www.acmicpc.net/problem/26076 25/09/12 0-1 BFS문제다. 이전에 곰곰컵에 나가서 틀린 이후에 한참동안 묵혀놨다가 해결해서 적어본다. 문제 접근 방식: 2025.09.15 - [알고리즘/백준 문제 풀이] - [Python] 3140번 GULIVER [Python] 3140번 GULIVERhttps://www.acmicpc.net/problem/3140 25/09/03 재밌는 0-1 BFS문제이다. 해당 아이디어를 통해 다른 문제도 쉽게 해결할 수 있었다. 문제 접근 방식: 두 조각으로 분리하기 위해서 필요한 벽의 개수의 최솟값lighter.tistory.com기본적인 접근 방식은 위의 문제와 매우매우매우 유사하다. 단지 해당 문제는 정답이 0, 1, 2로.. [Python] 3140번 GULIVER https://www.acmicpc.net/problem/3140 25/09/03 재밌는 0-1 BFS문제이다. 해당 아이디어를 통해 다른 문제도 쉽게 해결할 수 있었다. 문제 접근 방식: 두 조각으로 분리하기 위해서 필요한 벽의 개수의 최솟값을 묻는 문제이다. 처음에 생각했던 방법은 왼쪽에서 오른쪽으로 순회하면서 진행하는 2차원 DP였다. $DP[r][c]$ $=$ $r$행 $c$열까지 봤을 때 두 조각으로 분리하기 위해 필요한 벽의 개수의 최솟값 으로 DP식을 정의하고 돌렸다. 당연히 틀렸다. 틀린 후에는 태그를 까고 0-1 BFS라는 사실을 알게된 후에, 벽일 때는 0의 코스트로 가고 벽이 아닐 때는 1의 코스트로 가서 왼쪽에서 오른쪽으로 순회하도록 짰다. 근데 틀렸다. 진행방향을 오른쪽 위, .. [Python] 12944번 재미있는 숫자 놀이 https://www.acmicpc.net/problem/12944 25/09/14 전형적인 포함-배제 원리의 문제이다. 문제 접근 방식: 당신은 포함배제의 원리를 아는가? $K$개 중 $m$개를 선택해서 $N$에 $m$개의 숫자의 $\text{lcm}$을 나눠준 값을 더하거나 빼주면 된다. $m$이 홀수인 경우 더해주고, $m$이 짝수인 경우 빼주면 된다. 왜 그런지는 집합의 모습을 생각해보면 이해하기 쉬울 것이다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.더보기# 12944번 재미있는 숫자 놀이# 수학, 포함 배제의 원리import sysinput = sys.stdin.readlinefrom math import lcmans = 0N, K = m.. [Python] 7003번 Checker Board https://www.acmicpc.net/problem/7003 25/07/03 이와 거의 똑같은 문제로 왕들의 외나무다리 돌게임이라는 문제가 있는데, 해당 문제를 이전에 해결했음에도 불구하고 문제를 헤맸었다. 문제 접근 방식: 결국 줄 별로 게임이 분리된다는 것은 쉽게 관찰할 수 있다. 따라서 줄 별로 게임이 어떻게 거동되는지 확인해보자. 결론적으로 두 말 사이의 거리만큼의 돌이 존재하는 님게임이라고 볼 수 있다. 왜냐하면, 처음에 두 말 사이의 거리가 $n$이라고 해보자. 그러면 선공이나 후공이 거리를 늘리는 행동을 하면, 다른 사람이 똑같은 행동을 해서 거리를 좁힐 수 있기 때문이다. (따라쟁이 전략) 따라서 거리가 줄어들면 줄어들었지, 늘어나지는 않는다. 즉, 두 말 사이의 거리가 돌의 개수.. [Python] 30165번 Product Oriented Recurrence https://www.acmicpc.net/problem/30165 25/06/18 선형 점화식으로 바꾸는 문제이다. 꽤나 유익하다고 생각되어 적어본다. 문제 접근 방식: 문제의 요구사항은 다음과 같다. $f_x = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}$으로 정의된 점화식이 있고, $n, f_1, f_2, f_3, c$가 주어질 때 $f_n \mod (10^9 + 7)$을 구하는 것이 우리의 목적이다. 곱으로 되어있는 점화식이기 때문에, 우리가 흔하게 접하지 못하는 점화식의 형태이다. 우리가 흔하게 접하는 점화식의 형태는 덧셈의 형태이므로, 곱을 합의 형태로 바꾸기 위해 양 변에 밑을 $c$로 하는 로그를 취해주자. $$\log _c f_x = 2.. [Python] 16711번 Erasing Matrix https://www.acmicpc.net/problem/16711 25/08/28 이전에 비슷한 걸 풀었는데, 거기서 좀더 응용하면 문제를 해결할 수 있다.2023.03.14 - [알고리즘/백준 문제 풀이] - [Python] 9718번 Matrix Transformation [Python] 9718번 Matrix Transformationhttps://www.acmicpc.net/problem/9718 9718번: Matrix Transformation The first input line contains a positive integer,n, indicating the number of matrices (test cases). Each matrix starts with a line containi.. [Python] 24833번 Air Conditioner https://www.acmicpc.net/problem/24833 25/09/12 이게 어떤 알고리즘인지는 잘 모르겠는데, 문제에 대한 시각화를 해보고 싶어서 글을 적게되었다. 문제 접근 방식: 가로축은 시간을 나타내고, 세로축은 온도를 나타낸다. 그리고 빨간 선은 해당 시점에 특정 손님이 원하는 온도의 범위이다. 시간 1당 온도를 최대 1올리거나 1내릴 수 있으므로, 회색으로 칠한 범위가 해당 시점 이후로부터 가능한 온도의 범위가 된다. 이 회색 범위와 빨간 선이 겹친다면 겹친 구간에서 다시 기울기가 1인 직선과 기울기가 -1인 직선을 그어서 범위를 표현할 수 있다. 만약 회색 범위와 빨간 선이 겹치지 않는다면 불가능 한것이고, 모든 손님에 대해서 겹치는게 가능하면 가능한 것이다.아래는 내가 위의 .. [Python] 5746번 Onion Layers https://www.acmicpc.net/problem/5746 25/08/28 쉬운 볼록껍질 문제다. Do You know Convex Hull?? 문제 접근 방식: 볼록껍질 구하고 해당 볼록껍질에 속한 점은 기존 점 리스트에서 날린다. 이걸 반복하면서 볼록 껍질 개수를 세준다. 짝수 개면 안된다고 하고, 홀수 개면 OK란다. 약간의 예외처리 사항은 점이 2개 이하일 때는 볼록 껍질을 만들 수 없다는 점과, 180도일 때 여러 점을 포함하지 않고 끝 점만 포함한다는 점이다. 해당 부분을 틀려서 2번 틀렸다. 볼록껍질 코드는 모노톤 체인으로 구현했다.아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.더보기# 5746번 Onion Layers# 기하학, 볼록.. 이전 1 2 3 4 ··· 58 다음
