728x90 알고리즘/[python] 백준 BOJ328 [python] 백준 2641 다각형그리기 https://www.acmicpc.net/problem/2641 문제 해결같다고 판정되는 다각형은 오직 시작점의 차이와 역방향 이동 두개의 차이만 허락된다. CODEimport sysinput = sys.stdin.readlinefrom collections import dequeconvert = lambda x: (x+2)%4 if x!=2 else 4n = int(input())sample = deque(map(int, input().split()))rev_sample = deque(map(convert, sample))rev_sample.reverse()cnt = 0result = list()for _ in range(int(input())): x = deque(map(int,input().sp.. 2025. 1. 27. [python] 백준 2352 반도체 설계 문제 해결가장 길게 오름차순 수열을 만들수 있는 LIS (Longest Increasing Subsequence) 문제원소 하나씩 살펴보면서 가장 최근 이은 값도가 크면 하나 더해주고 작은 값이 나오면 이분탐색 통해 이전 값들에서 하나에 예약 연결한다 생각하고 value값을 바꿔놔도 문제 없다CODEimport sysinput = sys.stdin.readlinefrom bisect import bisect_leftif __name__ == "__main__": n = int(input()) A = list(map(int, input().split())) link = [] for d in A: if not link or link[-1] 2024. 8. 15. [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. 이전 1 2 3 4 ··· 82 다음 728x90
