전체 글102 [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. [C] 1389: 케빈 베이컨의 6단계 법칙 일단 인접행렬로 그래프를 저장한다음에 for문을 이용하여 언제가 베이컨 수가 가장 작은지를 확인해봤다. 나아진 점1: 처음에 bfs를 돌릴때 queue에다가 먼저 놓고 bfs함수를 호출함으로써 dfs와 bfs를 섞어쓰던 실수를 없앴다! 나아진 점2: bfs함수에서 beacon_number을 구할때 따로 배열을 만들어 몇번째에 beacon_number에 넣었는지 저장해두었는데 이번에는 beacon_number[i]=beacon_number[tmp]+1; 를 사용하여 배열 2개로 저장하던걸 1개로 저장하여 효율성을 높였다. 나아진점 3: bfs 만드는 속도가 빨라졌고 continue의 사용을 적절히 했다! 그리고 그래프에서의 최단거리를 구할 때는 항상 BFS를 쓴다는 것을 잊어버리면 안된다!! #includ.. 2023. 8. 3. [C] 14500: 테트로미노 이 문제는 효율적이게 풀 수 있는지는 모르겠지만 그냥 bruteforce로 풀었다. 하늘색 막대기는 2가지 경우의 수 노란색 막대기는 1가지 경우의 수 초록색 막대기와 분홍색 막대기는 4가지 경우의 수 주황색 막대기는 8가지 경우의 수가 있고 각각의 경우의 수 중에 최대 값을 구하면 됐다. 그리고 구역을 나누어서 최대한 for문의 개수가 적게 만들도록 노력했다. 사실 코드가 너무 길고 구현이 단순해서 쉽게 안풀릴 줄 알았는데 다행히 잘 풀렸다! 앞으로도 일단 그냥 코드를 짜보는 연습을 더 해야겠다 #include #include int arr[501][501]; int blue(int x_max,int y_max) { int max=0; int tmp; for(int j=1;jtmp3?tmp1:tmp3;.. 2023. 8. 1. [C] 10773: 제로 새로운 수의 삽입과 삭제가 한쪽 끝에서만 일어나고 있기 때문에 stack이라고 생각할 수 있다. 중요한건 맨 뒤 rear 이기 때문에 rear쪽에서의 변화만 잘 생각해주면 쉽게 구현 가능하다! #include int arr[100001]; int stack[100001]; int main(void) { int n; scanf("%d",&n); for(int i=1;i 2023. 7. 30. 이전 1 ··· 13 14 15 16 17 18 19 ··· 26 다음