본문 바로가기
728x90

알고리즘339

[python] 백준 16287 Parcel https://www.acmicpc.net/problem/16287   문제 해결오직 4개를 쓰며 정확히 w의 무게를 맞추는 방법에 대해서 여러가지 방법을 생각해 볼 수 있다.DP, DFS ...무게가 엄청 클 수 있고 n이 상대적으로 작으므로 n개에서 4개를 고르는 것을 사용한다.그런데 4개를 고를 때 graph를 사용하여 dp를 만들기는 상당히 부담스럽다. 4차원 공간보다 2개씩 나누어 2차원 DP를 만들고 2차원 + 2차원 계산을 하는 것이 좋을 것이라 생각했다.하지만 dp[i][j] 의 value 값을 무엇을 쓸지 사실 의미가 크게 없었다. {0, 1}로 하고 (w-i-j )숫자가 나오는 조합을 N개 안에서 또 찾는 것은 시간복잡도가 상당했다.따라서 dp를 1차원으로 만들어서 확인을 하는 것이 좋.. 2024. 6. 22.
[python] 백준 20149 선분 교차 3 https://www.acmicpc.net/problem/20149   문제 해결선분이 겹치는지 안겹치는지 확인할 때는 CCW (Counter Clock Wise)를 사용한다.선분 1, 선분 2가 있으면 선분 1과 선분 2의 끝점 각각을 CCW를 사용했을 때 부호가 반대로 나오고 선분1의 두 끝점과 선분2를 CCW를 사용했을 때 부호가 반대로 나오면 무조건 두 선분은 만나게 된다.문제는 끝점이 교차할 때 CCW가 0이 나올 경우가 있는데 조건을 나누어 코드를 짜야한다.선분 1의 끝점 두개와 선분 2의 끝점을 보고 선분 1에서 x축 값이 큰 값 (x 같으면 y값)이 선분 1의 x축 값이 작은 값(x같으면 y값)보다 크고 선분 2의 작은값보다 크고 큰값보다 작으면 겹친다. (코드 참고...) CODEimpo.. 2024. 6. 16.
[python] 백준 22940 선형 연립 방정식 https://www.acmicpc.net/problem/22940 문제 해결Reduced Row echelon form 실수 부분 반올림 주의 (함부로 int 쓰지 말것) CODEimport sysinput = sys.stdin.readlinen = int(input())arr = [list(map(int, input().split())) for _ in range(n)]for i in range(n): div = arr[i][i] for j in range(i, n + 1, 1): arr[i][j] /= div for j in range(n): if i==j:continue div = arr[j][i] # 계수가 1인 항의 몇배를 곱해서 없앨 수 .. 2024. 6. 15.
python] 백준 1743 음식물 피하기 https://www.acmicpc.net/problem/1743  문제 해결일반적인 bfs문제; CODEimport sysinput = sys.stdin.readlinefrom collections import dequedef bfs(x,y): que = deque() dxs = [-1, 1, 0, 0] dys = [0, 0, -1, 1] que.append((x,y)) visited[x][y] = 1 result = 1 while que: a, b = que.popleft() for dx, dy in zip(dxs, dys): na = a + dx; nb = b + dy if 0 2024. 6. 14.
728x90