전체 글102 [C/C++] 6064: 카잉 달력 일단 이 이중 반복문을 통하여 모든 m*n케이스를 찾아보려고 할 경우 제 시간안에 찾아볼 수 없다. 그렇기 때문에 특정 조건일 때만 돌아가도록 만들어줘야 한다. 이 문제는 결국 x+M*a=y+N*b 라는 a와 b에 관한 부정방정식을 푸는 것인데 결국 이는 답이 되는 수를 t라고 한다면 t%M==x t%N==y가 되도록 만들어줘야한다. 그렇기 때문에 while문에 들어가는 초기 변수가 j=x_target이 된 것이고 while문을 한번 돌때마다 x만큼 증가시켜주면서 만족하는 수가 있는지 확인해줘야한다. 한가지 유의해야할 점은 x==x_target && y==y_target일 때인데 사실 이 경우 x%x_target이 x가 아니라 0이므로 이때를 주의하여 코드를 작성해야한다. 또한 이 경우에는 gcd 유클리.. 2023. 8. 24. [C] 1697: 숨바꼭질 사실 이 문제가 BFS 관련 문제라는 것을 빨리 깨달았다면 구현은 생각보다 쉽게 할 수 있었을 것이다. 그냥 어떻게 풀지 모르겠어서 각 경우의 수를 나누어 구해보고 있었는데 5에서 시작해 17로 가기 위한 경우를 그리던 중 가지가 뻗어지는 tree형태인 것을 확인할 수 있었다. 그리고 몇 초만에 갔는지 확인해야하므로 BFS 관련 문제인 것을 파악했다. 모르겠으면 무식하게 좀 해봐야겠다. 특히 이 문제 같은 경우는 갈 수 있는 방법이 3가지이므로 가지가 3개인 tree인 것을 알 수 있다. 그리고 2차원 배열을 구현할 때 각 index를 써주는 것이 귀찮아서 그냥 처음에 int *ret0=&queue[front][0];로 선언하였더니 코드가 더 깔끔하고 읽기 쉽게 느껴졌다. 또 queue[1000000][.. 2023. 8. 23. [C] 1074: Z 맨 처음 생각했던건 이차원 배열 graph[40000][40000]을 잡고 돌아다니면서 수를 저장하여 r행 c열을 몇번째로 방문했는지를 확인하는 거였다. 하지만 이렇게 할 경우 512MB라는 메모리 제한에 걸리게 된다. 따라서 DecideSquare이라는 함수를 만들어서 r행 c열까지 재귀적으로 가는 동안 4가지 사각형 중 어디로 가야할지를 정하게 된다면 탐색에 걸리는 시간 뿐만 아니라 메모리도 아끼게 된다. 여기서 주의해야할점은 재귀 함수를 쓸때 각 조건을 잘 살펴야하고 언제 return을 해야하는지를 잘 생각해야한다. 그리고 pow()를 쓸때는 double형 변수를 써야한다! #include #include void recursion(double n,int x,int y,int x_target,int.. 2023. 8. 23. [C] 11403: 경로 찾기 문제는 정점 (i,j)에 대해서 i에서 j로 가는 길이가 양수인 경로가 있는지 확인하는 프로그램을 짜야한다. 여기서 알아야할 알고리즘은 Floyd's Algorthim으로 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우' 사용이 가능한 알고리즘이다. 2차원 배열에 저장을 하며 노드의 개수가 N개라고 할 때 N번만큼의 단계를 반복하여 리스트를 갱신하기 때문에 DP라고 볼 수도 있다. 이 알고리즘의 점화식은 Dab=min(Dab,Dak+Dkb)이지만 이 문제를 풀 때는 최단 경로가 아닌 경로가 있는지 확인만 하면 되기 때문에 코드가 조금 다를 수 있다. 그리고 이 점화식의 시간복잡도는 O(n^3)이다. #include #include int graph[101][101]; int mai.. 2023. 8. 23. 이전 1 ··· 9 10 11 12 13 14 15 ··· 26 다음
