Algorithm475 [파이썬] 백준 1976 : 여행 가자 (골드4) [파이썬] 백준 1976 : 여행 가자 (골드4)백준 1976 : 여행 가자 (골드4)풀이방향성 생각탐색해도 되고, 유니온파인드 써도 된다.인접 행렬을 순회하면서 하나의 집합으로 합치고, 주어진 path가 모두 같은 root를 가지는지 확인하기.전체코드import sysinput = sys.stdin.readlineN = int(input())M = int(input())G = [tuple(map(int,input().split())) for _ in range(N)]path = list(map(lambda x : int(x)-1,input().split()))P = [i for i in range(N)]def find(x): if x != P[x]: P[x] = find(P[x]) .. 2025. 4. 23. [파이썬] 백준 10775 : 공항 (골드2) [파이썬] 백준 10775 : 공항 (골드2)백준 10775 : 공항 (골드2)풀이방향성 생각그리디 + 유니온파인드항상 선택 가능한 범위 중, 가장 큰 쪽을 골라줘야 다음 쿼리가 들어왔을 때 더 많은 선택지가 생긴다.P 배열을 어떤 방식으로 지정해주냐에 따라 다르다.P 배열을 0으로 초기화 시킨 경우 방문처리의 개념으로 지정을 해준다.자기 자신으로 초기화를 시키는 경우, 현재 위치에 쿼리가 들어오는 경우 다음 도킹 가능 위치를 저장한다.전체코드import sysinput = sys.stdin.readlineN = int(input())M = int(input())P = [i for i in range(N+1)]def find(x): if x != P[x]: P[x] = find(P[x].. 2025. 4. 23. [파이썬] 백준 1300 : K번째 수 (골드1) [파이썬] 백준 1300 : K번째 수 (골드1)백준 1300 : K번째 수 (골드1)풀이방향성 생각이분탐색각 row가 정렬되있음을 바로 확인할 수 있다.각 row에서는 이분탐색으로 진행할 수 있고, 등차수열이라 나눗셈으로 바로 몫을 구할 수 있다.min value, max value는 구간에 포함되지 않도록 잡아주고, while문 조건을 min_val+1 전체코드N = int(input())K = int(input())min_val,max_val = 0,N**2+1while min_val+1 코멘트규칙성이 있는 array에서는 굳이 이분탐색을 사용하지 않아도 된다는 점 생각하기. 2025. 4. 21. [파이썬] 백준 1253 : 좋다 (골드4) [파이썬] 백준 1253 : 좋다 (골드4)백준 1253 : 좋다 (골드4)풀이방향성 생각3개의 수를 고르는 방식으로 풀면 $O(N^3)$으로 터진다.투포인터나, 이분 탐색을 이용해서 풀이.정렬 이후 이분 탐색을 이용해서 풀기.2중 for문으로 두 개의 값을 선택한 후(arr[i] + arr[j] = val), 전체 구간에서 val이 처음 나오는 구간과 끝나는 구간을 찾는다.구간 내에 인덱스 i와 j는 포함하면 안되니 처리를 해준다.숫자들을 선택할 때, N^2 내 iteration마다 set으로 관리를 해주면 터져서 차분 배열을 사용한다.구간의 시작과 끝에서만 이벤트 처리를 하고, 인덱스 i와 j가 내부에 있을 때, 각각 역으로 이벤트 처리를 해준다.전체코드N = int(input())arr = sort.. 2025. 4. 21. 이전 1 2 3 4 5 6 7 ··· 119 다음
