본문 바로가기
728x90

분류 전체보기423

[python] 백준 11400 단절선 https://www.acmicpc.net/problem/11400 문제 해결사이클이 만들어지는 선들은 하나가 끊긴다고 안이어지지 않는다.사이클이 안만들어지는 연걸선이 단절선이 된다.따라서 그에 관한 DFS 알고리즘을 사용하면 된다.CODEimport sysinput = sys.stdin.readlinesys.setrecursionlimit(10**5)def dfs(start ,parent): global cnt cnt += 1 visited[start] = True visit_order[start] = cnt lsv = visit_order[start] for childNode in graph[start]: if childNode == parent:conti.. 2024. 7. 7.
[python] 백준 11266 단절점 https://www.acmicpc.net/problem/11266 문제 해결단절점이란?정점을 제거했을 때 그래프가 두 개 이상으로 나누어지는 정점, 즉 없으면 두개의 그래프로 나누어진다고 생각단순 사이클을 이루는 점이거나 직선 그래프를 잇는 점이 아닌 여러 노드들을 잇는 교차로 점들을 단절점이라 생각하면 된다.풀이는 이해가 쉽지만 바로 풀기는 쉽지 않은 문제... CODEimport sysinput = sys.stdin.readlinesys.setrecursionlimit(10**5)def dfs(node, is_root): visit_order[0] += 1 # visit 번호 visit_order[node] = visit_order[0] child_cnt = 0 # 최소 진입순.. 2024. 7. 6.
[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.
728x90