개구리의 개발 블로그 개구리의 개발 블로그

백준 2015번 수들의 합 4 파이썬 문제 링크 - https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 연속하는 부분수열의 합이 K가 되는 구간의 개수를 찾는 문제였다. 주어진 수열의 순서를 바꿀 수 없었기 때문에 누적합을 우선 구하고 시작했다. 그리고 만약 수열의 크기가 작았다면 어떻게 접근했을 지 고민했다. 누적합 배열의 원소들 중 2개를 골랐을 때 차가 K인 경우의 수를 완전..

백준 15681번 트리와 쿼리 파이썬 문제 링크 - https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 반례를 찾는 것이 중요하다. 문제의 로직을 세울 수 있는 것만큼이나 중요한 것 같다. 쉬운 문제였지만 쉬운 반례를 찾지 못해 한참을 헤맸다. 1. 코드 #트리와 쿼리 (tree + dp ) 220503 #dp[node] = 1 이후에 #if len(tree[node]==1) : ret..

백준 3860번 할로윈 묘지 파이썬 문제 링크 - https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아 www.acmicpc.net 정답률이 15퍼센트인 것을 모르고 문제를 풀기 시작했다. 문제를 번역하는 과정에서 중요한 내용들을 번역하지 않아서 이슈가 좀 있었던 것 같았다. 음수 사이클이 도착점에 도달하는 지 여부에 상관없이 존재하기만 한다면 Never을 출력해야 한다. 이 부분에서 많이들 오답을 받은 것 같다. 1. 풀이 시작점과 도착점이 고정되어 있다. 2차원 좌표에서 최단 거..

백준 1102번 발전소 파이썬 문제 링크 -https://www.acmicpc.net/problem/1102 1102번: 발전소 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 www.acmicpc.net 오랜만에 재밌는 DP 문제였다. 처음에는 문제를 보자마자 백트래킹으로 풀어야겠다고 생각했다. 그런데 생각해보면 A발전소를 고칠 수 있는 모든 발전소에 대한 경우를 탐색하기 때문에 가지치기가 불가능한 상황이다. 현재 상황에서 정상 작동하고 있는 모든 발전소가 A개이고 정상 작동하지 않는 모든 발전소가 B개라면 총 A*B개의 발전소를 고치는 조합이 존재한다..

백준 1182번 부분수열의 합 파이썬 문제 링크 - https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분수열은 연속할 필요 없이 주어진 수열에서 원소를 중복 없이 선택하면 된다. 즉, 주어진 수열의 순서가 바뀌어도 똑같은 답을 갖게 된다. 처음에는 백트래킹으로 시도했다. 전체 수열에서 원소를 선택하는 경우와 선택하지 않는 경우를 나누어 탐색한다. 하지만 DFS 도중에 가지치기 되는 경우가 없기 때문에 사실상 ..

백준 10282번 해킹 파이썬 문제 링크 - https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 간단한 다익스트라를 통해 해결 가능한 문제다. 방문 표시를 하며 다익스트라를 실행한 후 방문된 노드를 계산하는 작업을 따로 해주면 된다. 이 때 방문된 노드까지 가는 최단 시간 중 가장 큰 값을 갱신한다. 1. 풀이 의존성의 방향은 간선의 방향이다. 시작 노드는 1개로 지정되어 있다. 주어진 시작 노드에서 모든 노드에 대한 최단 경로를 구한다. 방문 표시된..

백준 1162번 도로포장 파이썬, 다익스트라 문제 링크 - https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 주어진 도로에서 최대 K개의 도로의 가중치를 0으로 만들 수 있다. 조합을 사용할까 고민했다. 다익스트라를 이용하여 dist배열을 2차원으로 만들고 도로의 가중치를 0으로 만든 횟수를 저장했다. 1. 풀이 heap에 현재까지 누적 가중치, 0으로 만든 도로의 수, 현재 노드를 넣어준다. 다음 노드를 방문..

백준 1261번 알고스팟 파이썬, BFS, 다익스트라 문제 링크 - https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 다익스트라 문제 분류에서 찾은 문제였다. 아무리 봐도 BFS로 간단하게 풀 수 있을 것 같아서 그렇게 풀었다. 벽 부수고 이동하기 문제랑 거의 유사하다. 1-1. 풀이 현재 노드에 방문하기 위해서 부숴야하는 벽의 개수를 방문 표시에 저장하며 BFS를 실행한다. 방문하지 않은 경우나 이미 방문했지만 현재 부숴야..