본문 바로가기

python

 (50)
[백준] 10875 뱀, python https://www.acmicpc.net/problem/10875 주어진 명령에 따라 뱀이 몸을 늘려나가는데 도중에 격자판을 벗어나거나 자신의 몸통에 닿을 때까지의 시간을 구하는 문제이다. 격자판의 크기가 최대 \(10^{8}\) 이고 t가 최대 \(2\cdot10^{8}\) 이므로 격자판을 2차원 배열로 만들고, 1초마다 머리를 갱신해서 풀게 되면 메모리와 시간초과가 나게 된다. 따라서 뱀이 직선으로 이동했을때 늘려진 몸통을 선분으로 저장하게 되면, 선분이 교차되면 머리가 몸통에 닿은 것이라고 할 수 있다.교차되지 않았다면 t만큼 추가해주고, 교차되었다면 교차된 선분 중에 현재 선분의 시작점과 교점까지의 거리가 최소인 시점에 종료해주면된다. 선분이 교차하지 않으면 몸통에 계속 추가해 나가고..
[백준] 1029 그림 교환, python https://www.acmicpc.net/problem/1029 파이썬 함수 결과값 자동 캐싱(cache, lru_cache), python 파이썬 함수 결과값 자동 캐싱(cache, lru_cache), python파이썬 functools에는 cache와 lru_cache이 있다.둘 다 함수의 결과값을 자동으로 캐싱해 주는 기능이다. lru_cache(Least Recently Used)는 최근에 가장 적게 사용된 캐시를 삭제한다.또한 maxsize로 캐시 용량을aiden0413.tistory.com 파이썬 함수 cache를 사용하면 동일한 인자에 대해 캐싱된 함수 결과를 반환하므로 dp와 동일한 효과를 얻을 수 있다.dfs를 통해 가격이 이전 가격 보다 높으면 set에 해당 아티스트를 추가..
[백준] 18809 Gaaaaaaaaaarden, python https://www.acmicpc.net/problem/18809 배양액을 뿌릴 수 있는 땅에 빨간색, 초록색을 뿌리는 모든 케이스를 구한다.각 케이스마다 bfs를 통해 꽃의 개수를 구하고, 최댓값을 구하면 된다. 먼저 배양액을 뿌릴 수 있는 땅의 좌표를 배열에 저장한다.배양액을 뿌릴 수 있는 땅 중에서 배양액을 뿌릴 땅을 선택한다.위에서 선택된 땅에서 초록색을 뿌릴 땅을 선택한다. 나머지는 빨간색을 뿌리면된다. 예를들면 배양액을 5개의 땅에 뿌릴 수 있다하고 초록색 배양액 2개 , 빨간색 배양액 1개를 뿌린다 하면, 먼저 5개중 3개를 고른다.그리고 고른 3개중에서 2개는 초록색, 1개는 빨간색을 뿌리면된다.combination을 사용해서 각각의 경우의 수를 구해주었다. 배양액들이 동일..
[백준] 2568 전깃줄 - 2, python https://www.acmicpc.net/problem/2568 [백준] 1365 꼬인 전깃줄, python [백준] 1365 꼬인 전깃줄, pythonhttps://www.acmicpc.net/problem/1365 전깃줄이 꼬이지 않기 위해선 오름차순 순서대로 연결해야 한다.입력된 케이스에서 가장 긴 증가하는 부분 수열을 구하고 그 외의 전깃줄을 잘라내면 된다. LIS(가장aiden0413.tistory.com 이전에는 전깃줄이 서로 교차하지않게 만들기 위해 없애햐 하는 전깃줄의 최소 개수만 구하는 문제였다면, 이번에는 없애하는 전깃줄의 번호까지 구하는 문제이다. LIS(가장 긴 증가하는 부분 수열), python LIS(가장 긴 증가하는 부분 수열), python가장 긴 증가하는 부분 ..
[백준] 6549 히스토그램에서 가장 큰 직사각형, python https://www.acmicpc.net/problem/6549 주어진 히스토그램 내에서 가장 큰 직사각형의 넓이를 구하는 문제이다.이 문제는 세그먼트 트리와 분할정복을 통해 \(O(nlogn)\) 으로 푸는 방법과단조 스택(monotonic stack)을 사용해 \(O(n)\)의 시간 복잡도로 풀 수 있다. 세그먼트 트리와 분할정복을 사용한 풀이 세그먼트 트리, python 세그먼트 트리, python세그먼트 트리란? 세그먼트 트리란 완전 이진 트리에 배열의 구간 정보(최대, 최솟값, 합, 곱 등)를 저장하고 빠르게 구간 쿼리를 처리할 수 있는 자료구조이다.완전 이진트리란 리프노드를 제외aiden0413.tistory.com 위 그림에서 구간 별 최소 높이 막대의 인덱스를 구하기 위해..
[백준] 11668 파이프 청소, python https://www.acmicpc.net/problem/11668 파이프가 여러 개 놓여 있고, 파이프들은 겹치지 않거나 한 점에서만 겹친다.이때 생기는 모든 교점을 청소하면서 로봇이 서로 충돌이 나지 않아야한다. 두 선분의 교차 판정(2), CW/CCW, python 두 선분의 교차 판정(2), CW/CCW, python두 선분의 교차 판정(1), python 두 선분의 교차 판정(1), python선분 교차 판정이란점 A, 점 B를 양 끝으로 하는 선분 AB와 점 C, 점 D를 양 끝으로 하는 선분 CD가 최소 1개 이상의 공통점을 가지는 경우aiden0413.tistory.com 먼저 외적을 이용해 ccw체크를 해서 두 선분의 교점이 있는지 판별했다.선분의 출발점이 같다면 그 점은 ..
[백준] 1708 볼록 껍질, python https://www.acmicpc.net/problem/1708 주어진 점들의 볼록 껍질의 꼭짓점의 개수를 구하는 문제이다. 볼록 껍질(convex hull)(1), Graham Scan 알고리즘, python 볼록 껍질(convex hull)(1), Graham Scan 알고리즘, python볼록 껍질이란? 점들의 집합이 있을 때 그 집합에서 임의의 두 점을 이은 선분이 항상 집합에 포함되면 볼록 집합이라 부른다. 왼쪽을 볼록 집합(convex set)이라고 하고 오른쪽을 비볼록집합(non conaiden0413.tistory.com 볼록 껍질(convex hull)(2), Monotone Chain 알고리즘, python 볼록 껍질(convex hull)(2), Monotone Chai..
[백준] 20149 선분 교차 3, python https://www.acmicpc.net/problem/20149 두 선분의 교차 판정(1), python 두 선분의 교차 판정(1), python선분 교차 판정이란점 A, 점 B를 양 끝으로 하는 선분 AB와 점 C, 점 D를 양 끝으로 하는 선분 CD가 최소 1개 이상의 공통점을 가지는 경우를 두 선분이 교차한다고 말한다. 첫번째 그림과 같이 한점aiden0413.tistory.com 두 선분의 교차 여부와, 교점이 1개일때 그 교점의 좌표를 구하는 문제이다. 매개변수 방정식을 이용해 연립방정식의 해를 구한다.만약 해가 존재할시 구한 매개변수를 대입하여 좌표를 구할수 있다. 해가 존재하지 않을시에는 두 선분이 평행한지, 한 직선위에 있는지 체크해서 평행하다면 교점이 없는것이고, 한 직..

티스토리툴바