본문 바로가기

cses4

후속 노드 그래프 (Successor graph), 희소테이블 모든 정점에 대해 인접한 정점이 단 하나인 그래프로, 함수형 그래프(functional graph)라고도 부른다. succ(x)의 형태로 후속 노드 그래프의 모든 간선을 표현할 수 있기 때문. 후속 노드 그래프는 하나 이상의 컴포넌트로 구성돼 있고, 각각의 컴포넌트는 사이클 '하나'와 그 사이클로 가는 경로로 구성되어 있다. (그래프의 끝에 사이클이 단 하나 달린 형태) 트리구조와 유사하다.(트리에서 루트노드가 자식중 어딘가 가리키고 있다면 후속노드 그래프가 된다. -- 그건 더이상 트리가 아님) 희소테이블 p[u][k]에 이 구조를 담아 푸는 문제가 대부분 - 정점 u에서 k번 이동한 후의 정점을 log시간에 구하기 기본문제 : https://cses.fi/problemset/task/1750 널리쓰이.. 2020. 1. 29.
CSES PS - Elevator Rides (bit, dp) https://cses.fi/problemset/task/1653/ 쉬운 설명의 어려운 문제 bit쓰는 dp중엔 기본문제인 듯 하다. https://suuntree.tistory.com/124?category=797985 비슷한 유형의 더 어려운 문제 최대 20명의 사람들의 몸무게가 주어질 때, 최대 하중이 x인 엘레베이터에 사람을 채워 보내는 최소 운행 횟수를 구해라. (몸무게 2020. 1. 22.
CSES PS - Towers (그리디, sorting) https://cses.fi/problemset/task/1073 sorting and searching으로 분류된 것으로 볼때, 무작위 크기를 순서대로 multiset에 넣으면서 처리하는 것에 주목하라는 의미인 듯 하다. 큐브를 이용해서 타워를 쌓을 것이다. (큰 큐브 위에 작은 큐브를 올리거나, 새로운 타워의 기반으로 사용하거나) n개의 큐브의 크기가 주어질 때, 모든 큐브를 사용해서 만들 수 있는 타워의 최소개수를 구해라. (반드시 입력 순서대로 처리해야 한다.) i번째 큐브를 이용해서 타워를 쌓을 땐, 그보다 약간 큰 큐브 위에 두는 게 최적이다. int main() { FAST; int n; cin >> n; multiset st; while (n--) { int a; cin >> a; auto.. 2020. 1. 13.
CSES PS - Grid Paths https://cses.fi/problemset/task/1625/ 백트래킹 문제. 아이디어가 안떠올라서 답확인함. 7*7 공간에서 (0,0) ~ (6,0)까지 갈 때 경로가 ?,L,R,U,D 총 48자로 주어진다. 이때 ?대신 아무 방향이나 사용할 수 있을 때 가능한 경로의 수를 모두 구하는 문제. ?가 48개 있을 때 백트래킹 없이 dfs하면 4^48만큼의 시간이 걸리므로 백트래킹이라고 생각하지 않았다. U 9개 D 15개, R 12개, L 12개의 적절한 순열인 줄 알았지만 아니었다. (빨간색은 방문할 수 없는 지점(벽너머거나, 방문했거나), 파란색은 방문할 수 있는 지점(y>0 && y 0 && cy < 6 && !visited[cy - 1][cx] && !visited[cy + 1][cx]) r.. 2019. 12. 22.

티스토리툴바