정렬 + 스위핑 문제https://www.acmicpc.net/problem/2170 2170번: 선 긋기첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x www.acmicpc.net 💡 풀이 코드 import sysn = int(sys.stdin.readline())line = []for _ in range(n): start, end = map(int, sys.stdin.readline().split()) line.append((start, end))line.sort()last = -sys.maxsizeanswer = 0for start, end in line: ..

BFS + 백트래킹 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크www.acmicpc.net 0 - 빈 칸1 - 벽2 - 바이러스 처음에 생각한 방식 이것도 처음에 패턴 찾아서 쌩자 구현하려 했는데, 불가능이다. 그 이유는 바이러스(2)가 벽(1)을 만날때까지 상하좌우로 이동하며 벽(0)을 바이러스(2)로 감염시키기 때문이다. 즉, 패턴을 찾을 수 없다. 접근 방식바이러스들(2)의 위치에서 동시에 퍼져야 하므로 BFS벽을 무조건 3개 세워야 하는데, 바이러스가 최대한 퍼지지 않는..

BFS 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로www.acmicpc.net (1) 처음에 생각한 방식 - V1 (실패)# 벽 부수고 이동하기 (골드 3) / BFSimport sysfrom collections import dequen, m = map(int, sys.stdin.readline().split())graph = [[] for _ in range(n)]visited = [[False] * m for _ in range(n)]..

BFS 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가www.acmicpc.net 문제 조건처음에 아기 상어의 크기는 2, 아기 상어는 상하좌우로 인접한 한 칸씩 이동아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지날 수 없고, 나머지 칸은 모두 지나갈 수 있다.아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.더 이상 먹을 수 있는 물고기가 공간에 없다면 아기..

DP 문제https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)www.acmicpc.net ▪︎  내 코드import sysn = int(sys.stdin.readline())arr = list(map(int, sys.stdin.readline().split()))def bitonic(n, arr): dp = [1] * n dp2 = [1] * n for i in range(1, n): for j in range(i): if arr[i] > arr[j]..

DP 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net ▪︎ 내 코드 (성공) import sys n = int(sys.stdin.readline()) elec = [] for i in range(n): start, end = map(int, sys.stdin.readline().split()) elec.append((start, end)) elec = sorted(elec, key=lambda x:x[1]) def electronic(elec, ..