Python43 [백준] 그리드 네트워크 https://www.acmicpc.net/problem/18769 18769번: 그리드 네트워크 재현이는 그리드 네트워크 컨설팅 회사를 운영하고 있다. 어떤 회사의 데이터 서버가 격자 형태의 그래프로 주어졌을 때, 최소의 비용을 들여서 전용 통신망을 설치하려고 한다. 이때, 전용 통 www.acmicpc.net 파이썬으로 인해 하루넘게 억까 당한 문제입니다. heapq를 사용하면 이 문제를 절대 통과가 불가능합니다. 따라서, 프림으로는 절대 풀 수 없고 우선순위 큐 대신 간선들을 정렬하여 크루스칼을 적용해주면 간신히 통과가 가능합니다. import sys from collections import defaultdict #sys.stdin = open("input.txt", "r") input = sys.. 2023. 3. 2. [백준] Baaaaaaaaaduk2 (Easy) https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net BFS를 활용하여 풀이하였습니다. 0으로 되어있는 칸들이 인간이 놓을 수 있는 위치들이므로 해당 위치들 중 2개를 뽑아서돌을 놓아보고 잡을 수 있는 최대 돌의 수를 얻는 방식으로 풀이하였습니다. 잡아먹을 수 있는 돌들의 집합인 경우를 체크하는 방법은 2번 돌들을 기준으로 BFS를 하다가 빈 공간을 만나면 잡아먹을 수 없는 그룹인 것을 이용하였습니다. im.. 2023. 3. 2. [백준] 미로 탈출하기 https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net DFS로 해결할 수 있는 문제입니다. 현재 위치에서 시작으로 탈출이 가능한지 DFS로 탐색하게 됩니다. 만약 탈출이 가능하다면 DFS로 탐색하면서 만나는 위치들은 모두 탈출이 가능한 지점들입니다. 그러므로 해당 위치들에는 탈출이 가능하다고 체크해주고 만약에 탈출이 불가능하다면 만난 지점들은 모두 탈출이 불가능한 지점들입니다. 이렇게 탐색을 해주면서 탈출이 가능한 위치만 체크해주면 .. 2023. 3. 1. [백준] 전설의 JBNU https://www.acmicpc.net/problem/12757 12757번: 전설의 JBNU 첫 줄에는 초기 데이터의 개수인 \(N(1 \le N \le 100,000)\) 과 명령 횟수인 \(M(1 \le M \le 100,000)\), 가장 근접한 Key까지의 거리의 제한인 \(K(1 \le K \le 10,000)\)가 주어진다. 입력의 둘째 줄부터 N개의 줄에 www.acmicpc.net Java의 TreeMap을 활용하여 풀긴 풀었는데 파이썬으로는 무수한 시간초과를 겪고난 뒤에 해결하여 현재는 미해결 문제로 분류하였습니다. 아이디어는 Map의 key들을 이분탐색하면서 대체 키를 찾아주면 됩니다. 포인트는 key들을 정렬된 상태로 유지해야하는데 Java는 TreeMap에서 기능들을 제공하지만.. 2023. 2. 28. [백준] 연구소 3 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 조합 + BFS를 사용하는 문제입니다. 조합을 통해 활성화시킬 바이러스들을 선택하고 선택한 바이러스들을 시작으로 BFS를 진행해주면 됩니다. 포인트는 선택되지 못해 비활성화되어 있는 바이러스들을 만나는 경우인데 이 경우에는 큐에는 넣어주지만 모든 빈칸을 바이러스로 만들기 위해 필요한 시간으로 체크되면 안됩니다. import sys from itertools import combinations from co.. 2023. 2. 26. [백준] 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 스택을 활용한 문제입니다. 문자들을 스택에 쌓아주면서 마지막 문자열이 매칭하고자하는 문자열과 비교해서 같으면 stack에서 pop하여 버리면 풀 수 있습니다. import sys # sys.stdin = open("input.txt", "r") input = sys.stdin.readline inputs = list(input().rstrip()) matching = input()... 2023. 2. 24. [백준] 등수 찾기 https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 그래프 탐색 문제입니다. 이 문제의 특징은 그래프를 2개를 만들어서 각각 그래프를 탐색해야한다는 것 입니다. 자기보다 잘한 사람들을 가르키고 있는 그래프(in_graph)와 자기보다 못한 사람(out_graph)을 가르키고 있는 그래프를 각각 만들고 X보다 잘한 사람을 찾기 위해 in_graph를 탐색하면 자기보다 등수가 높을 수 있.. 2023. 2. 24. [백준] 게리 멘더링2 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 정말 정말 귀찮은 2차원 배열 시뮬레이션, 브루트포스 문제입니다. 모든 x, y, d1, d2 조합에 대해 각각의 구역의 인구수를 계산해주면 됩니다. 가장 어려웠던 부분은 구역을 나누는 부분인데 저는 다음과 같이 해결하였습니다. 1. 먼저, 5번 구역에 대해 처리를 먼저 해줍니다. 5번 구역에 대한 경계선을 미리 체크해주고 5번 구역의 경계 안에 있는 부분들도 체크해줍니다. 최상단 행과 최하단 행에는 .. 2023. 2. 23. [백준] 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 시간초과로 고생을 꽤나 한 문제입니다. 처음에 접근은 BFS + 우선순위 큐를 사용하여 현재 위치에 도달할 수 있는 최소값만을 선택해서 dist 2차원 배열에 저장하는 방식으로 풀이했습니다. 하지만 이런 방식을 사용하면 우선순위 큐에 push하는데 O(log n)만큼의 시간이 소요되기 때문에 시간초과가 발생했습니다. 1. 제가 지나쳤던 부분은 BFS를 통해 탐색.. 2023. 2. 22. 이전 1 2 3 4 5 다음
