무니화니

[Python 3] BOJ 17720 마약수사대

https://www.acmicpc.net/problem/17220 마약수사대는 마약공급책을 잡고 싶어 한다.마약의 원산지는 '다른 공급책에게 공급 받지 않는' 공급책이다.여기서, 해당 문제는 마약 공급책들 중 마약을 공급받을 수 있는 공급책의 수를 구하는 문제이다. 해당 문제는 DAG (Directed Acyclic Graph)의 일종으로 볼 수 있다. 즉, cycle이 없지만, 방향성이 있는 간선들로 이루어져 있다.따라서, 마약을 공급받지 않는 공급책들을 모두 저장받고, 해당 공급책들에 대해서 BFS를 실시하여 전달이 가능한 공급책들의 수를 세면 된다. 여기서 각 공급책의 이름이 대문자 알파벳으로 주어져 있다.이들을 리스트의 index로 만들기 위해, 'A'의 아스키 코드에서 빼서 번호를 설정한다.또..

[Python 3] BOJ 16973 직사각형 탈출

보통의 bfs와 같은 그래프 탐색 문제는 한 개의 지도를 바탕으로 1x1짜리 정사각형이 좌표를 돌아다니는 느낌인데, 이 문제는 우리가 움직여야 하는 직사각형의 크기가 H by W이다. 따라서, 직사각형을 움직이면서, 도착지점에 갈 수 있는 최소이동을 물어보는 문제였다. BFS로 해결했다. 처음 시작점에 직사각형이 위치할 수 있는지 여부를 확인한다.이후 왼쪽 상단 지점을 기준으로 직사각형의 좌표를 잡고 상하좌우로 이동시킨다.만약 벽이 있거나, 장애물이 있으면 움직일 수 없다.하지만 단순히 이동한 직사각형 안의 모든 좌표를 확인해야하면 시간초과 (TLE)가 발생한다.우리가 이미 검증했던 좌표들은 사실 다시 확인할 필요가 없다.즉, 상하좌우 이동에서 방문하게 되는 새로운 좌표들에서만 장애물 여부를 확인하면 된..

1부터 n번까지 방이 있다.여기서 반복적으로 'x부터 y번까지의 방'을 벽을 허물어서 한 개의 방으로 만든다.이후에 총 방의 개수를 세는 문제이다. 처음에는 분리 집합으로 Union-Find를 통해 해결하려고 했다.그러나, 100만개의 방을 5000번 합치게 되면, TLE를 받는다. 여기서 앞 방과 뒤 방만 생각하고, 중간에 있는 방들을 생각하지 않아도 되는 방법을 모색했다.따라서, 검색과 gpt를 통해서 '차분 배열'을 배우게 되었다.누적 합 (Prefix Sum)의 일종으로서, 시작점과 끝점에 더하고 빼주는 것을 이용하는 알고리즘이다. 즉, x번 방과 y번 방 사이의 방은 고려하지 않고,x번째 방에 1을 더해주고, y번재 방에서 1을 뺀다.여기서 1을 더해주는 것은 오른쪽 방의 벽을 허물었다는 뜻이고..

영양분 (단백질, 탄수화물, 지방, 비타민)이 일정 기준 이상 갖춰지게끔 하는 식재료들의 조합 중 가장 가격이 싼 경우를 정하는 문제였다. 만약 가격이 가장 싼 경우가 한 가지가 아닐 경우, 사전 순으로 가장 빠른 경우를 출력하는 문제였다. Brute Force와 Backtracking을 이용하여 해결하였다. DFS를 이용해 반복적인 backtracking을 통해 모든 경우에 대한 brute force를 할 수 있었다.시간 복잡도는 O(2^n)이지만, n의 크기가 최대 15이기 때문에 파이썬으로도 충분히 시간 제한 내에 들어올 수 있다. flag variable을 이용하여 영양소 최저 기준을 모두 만족하였는지 확인한다.만약 영양소 최저 기준을 만족했다면, 정답으로 들어올 수 있는지 확인한다.여기서 기존 ..

비트마스킹과 브루트포스, (그리디)를 이용한 문제였다.먼저, 행을 기준으로 뒤집을 수 있는 모든 경우에 대해서 뒤집기를 실시한다.n이 20인 경우 2의 20제곱 (약 100만번) 정도의 뒤집기를 한다고 생각하면 된다.모든 경우를 다 뒤집기 때문에 브루트 포스이다.또한, 여기서 비트마스킹을 사용한다. 0부터 2^(n-1)-1까지의 숫자를 이용해서, 각 비트에 1이 있으면 뒤집기를, 없으면 뒤집기를 실시하지 않는다. for bit in range(1예컨데, n이 3개짜리인 테이블을 예시로 보자.HHTTHTHTH[표 1: 현재 테이블] 다음과 같은 3행에 뒤집기를 하고 싶다. 그렇다면 ,비트마스킹에서 '100'의 경우일 것이다.즉, 1행과 2행에서는 뒤집지 않고, 3번째 비트인 1에서만 뒤집는다.HHTTHTT..

https://www.acmicpc.net/problem/11266 Articulation Point (단절점)을 이용해서 풀어야 하는 문제였다.DFS를 응용하여 풀이할 수 있었다. 타 블로그들에서도 잘 설명이 되어 있지만, 간단하게 설명해보겠다. 현재 위치해있는 정점 A 보다 늦게 탐색이 될 예정인 정점들 중에서 정점 A보다 먼저 탐색이 되는 정점으로 가는 경로가 없을 경우에 정점 A를 단절점이라고 할 수 있다.그리고, 예외적인 케이스로서 루트 노드로 시작한 노드의 자식의 수가 2개 이상이면 단절점이라고 할 수 있다. 방문하지 않은 정점으로 이동을 할 경우에는, 반복적으로 dfs를 진행하여, 제일 정점의 방문 순번이 낮은 경우를 visited에 저장한다고 생각하면 된다.import sysinput=sy..

https://www.acmicpc.net/problem/15991 일반적인 DP 문제이다.두 개의 list를 정의하였는데, dp[n]는 1,2,3의 합으로 n을 만들 수 있는 모든 경우의 수를 정의하고, answer[n]은 대칭적으로 n을 만들 수 있는 경우의 수, 즉 문제의 정답을 의미한다.예를 들어,1 -> dp[1]= 11+1 , 2 -> dp[2]= 21+1+1, 1+2, 2+1, 3 -> dp[3]=4 와 같이 정의되고,  1 -> answer[1]= 11+1, 2 -> answer[2] =21+1+1, 3 -> answer[3] =21+1+1+1, 2+2, 1+2+1 -> answer[4]=3 와 같이 정의된다. 여기서, dp[i]의 값은 dp[i-1], 1 의 조합, dp[i-2], 2 의..

이분 매칭 알고리즘을 사용한다.이분 매칭 (Bipartite Graph)는 두 개의 겹치지 않는 정점의 집합으로 나타낼 수 있는 그래프다. 이 두 집합을 왼쪽 집합이랑 오른쪽 집합으로 정의한다. 이 때, 이분 매칭은 왼쪽 집합의 각 정점을 오른쪽 집합의 정점과 연결하되, 한 정점은 최대 한 번만 매칭을 해야 한다. 예를 들어보자.왼쪽 집합 = {A,B,C,D}오른쪽 집합 = {1,2,3}A= (1,2)B=(1)C=(2,3)D=(3) 1. A는 1과 2와 매칭될 수 있다. A를 1과 매칭시킨다.2. B는 1과 매칭될 수 있는데, 이미 A와 매칭이 되어있다. 따라서 A를 2로 옮기고, B를 1과 매칭시킨다.3. C는 2와 3과 매칭될 수 있다. A는 2와 매칭되어 있으므로, C를 3과 매칭시킨다.4. D는 ..

https://www.acmicpc.net/problem/11967  시작점인 (1,1)부터, "불이 켜져 있는"방들을 걸어다녀야 한다.각 방들을 움직이면서 다른 방의 불을 켤 수 있는 스위치들을 누르면서, 갈 수 있는 방들을 넓히는 것이 주요 포인트이다. 해당 문제가 일반적인 BFS문제랑 다른 이유는, 기존 bfs에서는 '내가 한 번 갈 수 없다고 판단한 장소는 다시 신경쓰지 않아도 된다.' 하지만, 여기 문제에서는 특정 방을 도착하면서 기존에 가지 못했던 방의 불이 켜지면서, 이제 갈 수 있는 방이 될 수도 있기 때문에, 방금 스위치를 켠 방이 기존에 내가 갔던 길로 연결되어 있는 방인지 확인해주는 과정을 통해 해결해야 한다. from collections import dequeimport sysin..

https://www.acmicpc.net/problem/2852[English Translation]Donghyuk enjoys watching NBA basketball games. Donghyuk has this weird hobby, where a team scores a goal, he records the time the goal got in and the team who scored. Basketball game goes on for 48 minutes. Return the time how long each team was winning. [Input]In the first line, total count of that each goal is given.Starting from the sec..