728x90 백준41 [BOJ/Python] 1717. 집합의 표현 📌 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 📌 문제 접근 방법 상호배타 집합의 find_set연산과 union연산을 구현해서 풀이하였다. 시간초과가 났는데, 해결을 위해서 재귀 깊이를 설정해주고 input을 sys.stdin.readline으로 바꿔줬다. 최대 재귀 깊이는 어떻게 계산해야 하는지 궁금해졌다! 지금까지는 아무거나 큰 값으로 넣어줬는데 어떻게 계산해야하지? 📌 코드 # 백준 1.. 2021. 10. 21. [BOJ/Python] 17144. 미세먼지 안녕! 📌 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 📌 문제 접근 방법 단순 구현 문제! 문제가 시키는 대로 따라서 구현하면 된다. spread 함수를 만들어서 미세먼지가 퍼지도록 한다. dust라는 배열을 따로 만들어서 각 위치의 먼지 변화량을 저장하고 원래 배열과 더해준다. clean 함수를 만들어서 공기청정기를 가동시킨다. 공기청정기의 위치와 방향을 매개변수로 받아서 해당하는 방향대로 값을 swap해준다. 2, 3의 과정을 T번만큼.. 2021. 10. 20. [BOJ/Python] 14981. 톱니바퀴 📌 문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 📌 문제 접근 방법 톱니바퀴의 상태를 deque을 이용해서 받아서 원형큐라고 생각하고 코드를 구현했다. 시계방향으로 회전일 경우, 맨 마지막 원소를 빼서 맨 첫 번째에 삽입해줬다. 반시계방향으로 회전일 경우, 맨 첫 번째 원소를 빼서 맨 마지막에 삽입해줬다. 그리고 회전이 일어나는 경우, 앞 뒤 바퀴와 원소를 비교해서 맞물린 부분이 다르면 해당 바퀴도 재귀로 회전을 시켜줬다. 이 때,.. 2021. 10. 14. [BOJ/Python] 17471. 게리맨더링 📌 문제 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 📌 문제 접근 방법 N개의 구역을 조합을 이용해서 2개의 선거구로 나눈다. 각 선거구를 bfs를 통해 탐색해서 모든 구역에 방문할 수 있는지 체크한다. 여기서, 선거구에 있는 구역만 탐색을 하는 것이 포인트! (w in group → 이걸 처리 안해줘서 실패가 나왔음!) 2개의 선거구 모두 선거구 안의 모든 구역에 방문할 수 있다면, 인구 수의 차이를 구하고 최소값으로 갱신한다. 📌 코드 # 백준 17471 .. 2021. 10. 13. 이전 1 2 3 4 5 6 7 ··· 11 다음 728x90