본문 바로가기
728x90

알고리즘316

[python] 백준 2096 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 해결 사실 문제 자체는 매우 쉽다. (dp를 이용해서 0열, 1열, 2열에 각각 올 수 있는 이전 행 최고 누적합을 가져오서 더하면 되므로) 하지만 메모리가 4MB 밖에 안주어진다. 정확한 양은 체감을 못해도 평소 250~500MB 되는 문제도 많은 것을 보면 엄청 적다는 것을 알 수 있다. 따라서 리스트를 n행 모두 사용하는 것이 아니라(dp[0], dp[1], .... 사용하면 메모리가 커진다..) 한.. 2023. 3. 7.
[python] 백준 14503 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 해결 한칸씩 정해진 규칙대로 움직이면서 청소 안된 곳 청소하는 것으로 구현하는 문제 사실 어렵진 않지만 처음 원본 그대로 deepcopy를 해야한다. 그 이유는 처음 0, 1은 단순히 청소 안된 곳, 청소 된 곳을 의미하는 것이 아니라 이동할 수 있는 곳, 이동 할 수 없는 곳(벽)을 의미하는 것이기도 하기 때문이다. 따라서 아래 코드는 vi.. 2023. 3. 7.
[python] 백준 14502 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 벽을 어떻게 세워야하는가? → 상황에 따라 다르다. So 모든 경우 다 해봐야 한다. 재귀 사용! 최대 영역을 어떻게 구하는가? 전염 되는 지역을 계속 이동 시킨 후 더이상 전염이 안될 때 전염이 안된 일반 지역의 구역 개수를 구하면 된다. 전염지역 구하기 위해 bfs() 할 때 계속 graph 값이 바뀌므로 copy.deepcopy를 이용해 복사본으로 돌리는 것이 좋다! copy 라이브러리 알아두.. 2023. 3. 6.
[python] 백준 15686 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 해결 치킨집을 m개로 줄여서 각 집에서 치킨집까지 최소거리 합을 구해야한다. 치킨집을 m개로 줄이는 경우의 수는 combinations 라이브러리를 이용하면 좋을 것이다. 그러기 위해서는 치킨집 좌표를 알아야할 것이다. for문을 통해 치킨집 좌표와 집 좌표를 구해놓자. 치킨집 m개를 뽑은 다음 집 하나 치킨집 하나씩 매칭 시켜가며 최소거리 합을 구해본다. 시간복잡도가 .. 2023. 3. 5.
728x90