해설35 [C] N과 M 백트래킹(Backtracking): 해를 찾는 도중에 지금의 경로가 해가 되지 않을 경우 그 경로를 더이상 가지 않고 되돌아오는 것! -> 모든 가능한 경우의 수 중 특정 조건을 만족시키는지 확인 -> 특정 조건 만족안하면 탐색 X -> DFS등에서 모든 경우의 수를 탐색하는 과정에서 같이 사용하여 더 이상 아니면 그 이전으로 돌아가서 다시 탐색 -> 조합과 관련된 문제는 백트레킹! -> 자기 자신을 호출하는 재귀함수를 주로 이용, 탈출 조건 잘 써야함! 15650 N과 M(2) -> 중복 안됨 -> 오름차순 #include int arr[11]; void ascend(int front,int n, int m, int cnt) { for(int i=front;i 2023. 8. 5. [C] 7569: 토마토 7576 토마토 문제와 거의 유사하지만 전에 문제는 2차원 배열, 이번 문제는 3차원 배열로 풀어야한다는 점에서 다르다. 전에 코드에 비해 나아진 점을 찾아보자면! 1. graph 값을 저장하면서 동시에 익은 토마토가 있는 경우에 바로 queue에 저장해뒀고 2. 몇번째 날에 익었는지를 새로운 배열로 선언하지 않고 queue 배열을 [][4]로 지정하여 0에는 z, 1에서 y, 2에는 x, 3에는 익은 날짜를 저장함으로써 가독성을 높였다. 3. 익은 토마토 개수와 토마토가 없는 자리의 개수를 따로 구함으로써 예외인 경우를 처리해줬다. 주의해야할 점을 찾아보자면! 3차원 문제이기때문에 Z,Y,X 순서를 헷갈리지 않아야하고 맨 마지막에 bfs()함수에서 return 할때 queue[rear][3]에는 아무런.. 2023. 8. 4. [C] 1003: 피보나치 함수 피보나치!!하면 바로 Dynamic Programming으로 풀어야겠다는 생각이 들어야한다! 가장 대표적이면서 기본적인 DP 문제가 피보나치랑 이항계수 관련된 문제이기 때문이다 예시와 같이 피보나치 함수를 f(n)부터 구한다면 호출의 개수가 n이 조금만 증가해도 기하급수적으로 늘어난다. 그렇기 때문에 f(0)과 f(1) 부터 배열에 저장하면서 f(n)을 구해야만 효율적으로 호출할 수 있다. 이 문제에서도 n이 1,2,3...증가할 수록 호출하는 f(0)과 f(1)의 개수가 피보나치 수열의 점화식을 따른다. 그렇기 때문에 이것을 배열에 미리 저장한 후 테스트케이스가 주어지면 불러오면 되는것이다 #include int arr[500001]; int fibo_0[41]; int fibo_1[41]; int m.. 2023. 8. 3. 이전 1 ··· 6 7 8 9 다음