본문 바로가기

분류 전체보기

 (61)
[백준] 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..
볼록 껍질(convex hull)(2), Monotone Chain 알고리즘, python 모노톤 체인(Andrew's Monotone Chain) 알고리즘 볼록 껍질(convex hull)(1), Graham Scan 알고리즘, python 볼록 껍질(convex hull)(1), Graham Scan 알고리즘, python볼록 껍질이란? 점들의 집합이 있을 때 그 집합에서 임의의 두 점을 이은 선분이 항상 집합에 포함되면 볼록 집합이라 부른다. 왼쪽을 볼록 집합(convex set)이라고 하고 오른쪽을 비볼록집합(non conaiden0413.tistory.com 모노톤 체인 알고리즘도 스택을 사용해 점들을 순회하며 CCW를 판별하여 꼭짓점들을 추가해 나가는 방식이 그레이엄 스캔과 동일하다.하지만 점을 정렬하는 방식과 볼록 껍질을 구성하게 되는 순서에서 차이점이 있다. 모노톤 체..

티스토리툴바