본문 바로가기

알고리즘15

BOJ 5829 ) Luxury River Cruise 5829번: Luxury River Cruise Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with N ports (1 >K; river=vector(N+2,vector (2)); int L,R; for(int i=1;i>L>>R; river[i][0]=L; river[i][1]=R; } char temp; for(int i=0;i>temp; if(temp=='L')seq.push_back(0);// L else seq.push_back(1);// R } cout 2020. 9. 22.

BOJ 5980 ) Corn Maze 5980번: Corn Maze This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both www.acmicpc.net 텔레포트가 있는 미로를 탈출해야 한다. BFS문제인데 텔레포트를 밟는 계산을 고려하는게 좀 어려웠다. 일단 최단경로를 구하는 문제라서 같은 길을 두번 거치면 무조건 거리가 증가해서 visited.. 2020. 9. 20.

BOJ 14675 ) 단절점과 단절선 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net 주어진 트리에서 쿼리로 주어지는 정점과 간선이 해당 트리의 단절점 또는 단절선 인지(없을 경우 트리가 둘로 나뉘는지)를 묻는 문제이다. 한학기만에 알고리즘 문제를 풀었는데 너무 오랜만이라 완전히 방향을 잘못 잡았다. 고질병인 시간복잡도 계산 안하고 일단 문제 풀기는 여전히 고쳐지지 않았다. 정점의 개수 10만에 쿼리가 10만갠데 매 쿼리마다 dfs를 돌렸고 당연히 시간초과가 났다. 생각해보니까 당연한거였는데 왜 짤때는 모르는걸까. 주어진.. 2020. 9. 19.

이전 1 2 3 다음

티스토리툴바