본문 바로가기

전체 글60

BOJ 1012 ) 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net DFS로 간단히 해결 할 수 있는 문제. 왠진 모르지만 예전에 풀려고 시도했다가 실패한 흔적이 남아있었다. 벡터를 이용해 밭의 크기를 런타임에 지정해주고 배추는 1로 표시한다. 방문여부는 배추가 없는 곳은 방문할 필요가 없으므로 기본은 모두 0으로, 배추가 있는 곳은 배추 위치를 표시하면서 같이 방문여부를 1로 변경해준다. 그 이후에는 반복문을 돌면서 배추가 심겨진 곳을 dfs로 탐색한다. 다음 칸을 방문할지 말지는 배추가 있는지와 방문한적이 없는지를 모두 고려해준다. #i.. 2021. 3. 12.

BOJ 1003 ) 피보나치 함수 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 간단한 DP로 해결할 수 있는 문제다. '피보나치 + 제한시간이 짧음' 에서 바로 DP가 생각나서 그렇게 풀었다. 그냥 피보나치문제를 풀 수 있다면 어려움 없이 풀 수 있는 문제. #include #include #define pii pair #define x first #define y second using namespace std; int T,N; pii fib[42]; void makefib(){ fib[0]={1,0}; fib[1]={0,1}; for(int i=2;i>T; makefib(); while(T--){ cin>>N; cout 2021. 3. 12.

네트워크 프로그래밍 과제 서버 #include #include #include #include #include #include #include #include #include #include #include #define SA struct sockaddr #define MAXLINE 4096 #define bzero(ptr, n) memset(ptr, 0, n) #define LISTENQ 1024 int main(int argc, char **argv){ int listenfd, connfd; struct sockaddr_in servaddr; char buff[MAXLINE]; time_t ticks; listenfd = socket(AF_INET, SOCK_STREAM, 0); bzero(&servaddr, sizeof(s.. 2020. 10. 3.

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 ··· 7 8 9 10 다음

티스토리툴바