본문 바로가기

python

 (50)
[백준] 2042 구간 합 구하기, python https://www.acmicpc.net/problem/2042 [백준] 2357 최솟값과 최댓값 [백준] 2357 최솟값과 최댓값https://www.acmicpc.net/problem/2357 세그먼트 트리, python 세그먼트 트리, python세그먼트 트리란? 세그먼트 트리란 완전 이진 트리에 배열의 구간 정보(최대, 최솟값, 합, 곱 등)를 저장하고 빠르게 구간 쿼aiden0413.tistory.com 구간합을 계산할 때는 합 세그먼트 트리를 생성한 다음, 이전에 풀었던 최솟값 최댓값 구하는 로직과 똑같이 왼쪽 자식 노드가 홀수일 경우 해당 노드값을 합에 반영시키고 노드번호를 1 증가시키고,오른쪽 자식 노드가 짝수일 경우 해당 노드값을 합에 반영시키고 노드번호를 1 감소시킨다.그..
[백준] 2357 최솟값과 최댓값, python https://www.acmicpc.net/problem/2357 세그먼트 트리, python 세그먼트 트리, python세그먼트 트리란? 세그먼트 트리란 완전 이진 트리에 배열의 구간 정보(최대, 최솟값, 합, 곱 등)를 저장하고 빠르게 구간 쿼리를 처리할 수 있는 자료구조이다.완전 이진트리란 리프노드를 제외aiden0413.tistory.com 특정 구간 (a, b) 사이의 최댓값, 최솟값을 m 번 구하는 문제이다.파이썬의 min, max는 시간복잡도가 O(n) 이므로 모든 (a, b) 부분배열에서 min, max 함수를 사용하게 되면 O(n²) 이 되어 시간초과가 나게 된다. 따라서 이 문제는 세그먼트 트리를 이용하여 풀어야 한다.세그먼트 트리란 완전 이진트리에 구간별로 나누어 그 구간 ..
[백준] 1194 달이 차오른다, 가자. , python https://www.acmicpc.net/problem/1194 키를 보유하고 있다면 문을 열고 탐색하고, 키를 보유하고 있지 않다면 키가 있는 곳에 들렀다가 키를 가지고 문을 열고 탐색하여 목적지까지의 최단 경로를 찾는 문제이다. 처음에는 최단경로를 찾는 문제이므로 bfs탐색을 해 목적지인 '1'까지의 경로를 모두 구하고, 도중에 열쇠를 보유하지 않은 문이 있다면 그 문에 해당하는 열쇠까지의 경로를 재귀적으로 구하는 방식으로 풀려했었는데 오답이 나왔다. 이 문제는 비트마스킹을 사용해서 현재 보유한 키정보를 업데이트하면서 bfs탐색을 하는 문제이다.a~f까지의 키 정보를 a부터 0번째, b는 1번째, c는 2번째 비트에 키를 보유하고 있다면 1, 보유하고 있지 않다면 0으로 표시한다.예를 들어 ..
[백준] 11003 최솟값 찾기, python https://www.acmicpc.net/problem/11003 구간의 최솟값을 찾는 문제이다.파이썬 내장함수 min을 쓰게 되면 O(n)을 n 번하게 되어 시간초과가 나게 된다. 이 문제는 모노토닉 큐를 사용하여 해결할 수 있다.모노토닉 큐(단조 큐)란 큐안의 원소들이 항상 오름차순, 또는 내림차순을 유지하도록 관리되는 큐이다.이 문제에서는 최솟값을 찾아야 하므로 큐가 오름차순을 유지되도록 관리한다. 모노토닉 큐에는 인덱스와 값을 같이 넣어주어야 한다. 왜냐하면 윈도우의 크기가 범위를 벗어나게 되면, 큐의 맨 왼쪽값(구간의 최솟값)이 범위를 벗어나게 되면 제외해 주어야하기 때문이다.윈도우를 오른쪽으로 이동시키고 윈도우에 추가되는 값과 모노토닉 큐의 맨 오른쪽값을 비교한다. 만약 추가되는 값이 더..
[백준] 1365 꼬인 전깃줄, python https://www.acmicpc.net/problem/1365 전깃줄이 꼬이지 않기 위해선 오름차순 순서대로 연결해야 한다.입력된 케이스에서 가장 긴 증가하는 부분 수열을 구하고 그 외의 전깃줄을 잘라내면 된다. LIS(가장 긴 증가하는 부분 수열), python LIS(가장 긴 증가하는 부분 수열), python가장 긴 증가하는 부분 수열이란? 가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) 란 오름차순으로 정렬된 부분 수열 중에 가장 긴 것을 말한다. 예를 들면 수열이 [10, 20, 5, 30, 15, 50]에서aiden0413.tistory.com import sysfrom bisect import bisect_leftinput =..
[백준] 14658 하늘에서 별똥별이 빗발친다, python https://www.acmicpc.net/problem/14658 트램펄린을 놓을 수 있는 모든 경우에 수에 대해 별똥별이 해당 범위 내에 포함되는지 여부를 체크하여 개수를 세어주면 된다. import sysinput = sys.stdin.readlinen, m, l, k = map(int, input().split())# 별똥별이 떨어질 수 있는 모든 x좌표와 y좌표를 set으로 저장pos_x = set()pos_y = set()star = []for _ in range(k): x,y = list(map(int, input().split())) pos_x.add(x) pos_y.add(y) star.append([x,y])answer = 0# 트램펄린의 왼쪽 위 좌표..
[백준] 19238 스타트 택시, python https://www.acmicpc.net/problem/19238 bfs를 통해 모든 칸을 탐색하면서 해당위치에 승객이 있다면 (이동해야 하는 거리, 행, 열) 값을 힙에 넣는다.전부 탐색 후 힙에서 하나를 꺼낸다. 꺼낸 승객은 최소 이동거리를 만족하고, 거리가 같다면 최소행, 최소열인 순으로 힙에서 정렬이 되므로 조건을 만족한다.만약 승객이 없거나, 연료가 없을 시 종료한다. 해당 승객의 위치에서 목적지까지 bfs탐색을 한번 더 한다. 목적지에 도달하기 전에 연료가 0 미만으로 떨어지거나, 목적지로 가는 길이 막힌 경우 종료한다.여기서 길이 막힌 경우를 빼먹어서 런타임에러가 발생했다. 위 두 과정을 종료되지 않을 때까지 반복해서 구현하였다. import sysfrom collections..
[백준] 17779 게리맨더링 2, python 주어진 조건에 맞게 구역을 5개로 나누고, 각 구역의 인구수 총합을 구한 다음, 인구수가 가장 많은 구역과 가장 적은 구역의 인구 차이의 최솟값을 구하는 문제이다. 범위를 만족하는 모든 x, y, d1, d2의 경우에 대해, 각 케이스마다 구역을 나눈 뒤 인구수 차이를 구하고, 최종적으로 그 값의 최솟값을 구하면 된다. 처음에 격자를 생성하면서 각 row마다 누적합을 계산해 놓는다.이후 각 구역마다 row에 해당하는 column값을 구하고 누적합을 계산한다. 1번 구역의 경우 1 그리고 x 1번 구역의 인구수의 총합은 각 row마다 1~c까지의 합을 미리 계산해 둔 누적합을 더해주면된다. 2번 구역의 경우는 1 x 2번 구역의 인구수 총합은 row 총합에서 1~c까지의 누적합을 빼주면 c~n까지의 합을 ..

티스토리툴바