전체 글102 [C] 2178: 미로 탐색 #include //bfs로 하면 좋은 점은 dfs는 각 경우의 따라서 어떤 경우가 최소인지 결정해야할 때가 있음 //bfs는 같은 층에 있는 노드들을 쭉 훑고 그 다음 층으로 내려가기 때문에 각 경우가 최소의 해인걸 알 수있음 (애초에 겹치는 경우가 없다, 비교해서 어떤 경우가 최소인지 확인하는 경우가 없음) int arr[101][101]; int dp[101][101]; //미로 저장 int queue[10001][2]; //방문한 좌표를 저장하여 queue 생성 -> front와 rear을 이용해 문제 해결! int dx[4]={-1,1,0,0}; // 4가지 방향의 x좌표 int dy[4]={0,0,-1,1}; int bfs(int n,int m) { int front=0,rear=0; queu.. 2023. 7. 29. [C] 1260: DFS와 BFS 거의 1년만에 자료구조 관련 문제를 푸느라 그런지 정말 오래걸렸다.. 그래도 어찌됐는 풀긴 했는데 일단 잠시 정리를 해봐야겠다 일단 DFS 관련 구현이 훨씬 쉽다. 가장 깊게 들어갔다가 그 노드가 leaf면 바로 뒤로 나오면 되기 때문에 사실상 함수를 만들어 재귀로 만든다면 바로 구현 가능하다. 문제는 BFS인데 얘는 같은 depth인 애부터 먼저 찾아줘야 하기때문에 재귀를 이용해서 푼다면 포인터를 쓰며 굉장히 어렵게 풀어야한다. 구조체를 만들어 서로 link해주면 될 것 같긴한데 사실상 비효율적이다. 이때 BFS와 관련해서 Queue를 하나 만들어주면 front에서는 삭제가, rear에서 삽입이 되면 쉽게 풀 수 있다. 특히 front와 rear이 같아지게 되는 경우는 곧 rear이 더 이상 새로운 값.. 2023. 7. 29. [C] 11726: 2Xn 타일링 생각보다 쉽게 풀려서 깜짝 놀랐다 아무래도 평소에 조금 더 어려운 문제를 푸느라 상대적으로 쉽게 느껴졌나보다! 아무래도 점화식도 피보나치 수열과 같은 형태라 생각이 떠올리기 쉬웠고 점화식형태도 하나라서 직관적으로 보였다. 무엇보다 구현도 간단했는데 다만 주위해야할건 입력값이 1000개인데 피보나치 수열의 특성상 f(1000)은 int의 범위에서 벗어난다. 아마 long long int를 써도 벗어날 것 이다, 따라서 이때 생각났던 문제가 nCr, 조합 관련 문제였는데 이것도 n!이 n이 커질수록 기하급수적으로 커지기 때문에 n-i를 곱할때 i만큼 동시에 나눠져야 범위를 벗어나지 않는다. 이것도 마찬가지로 10007을 넘어갈 때마다 10007로 나눈 나머지를 dp[]에 넣어주면 된다. 다음은 아래 소스코드.. 2023. 7. 25. [C] 2156: 포도주 시식 처음에 점화식을 쉽게 찾았고 구현도 다른 DP 문제처럼 쉽게 되서 완전 쉽게 풀줄 알았다... 점화식은 쉽게 보면 근데 여기서 간과한 점이 다른 "계단 오르기"문제와의 차이점이 있다는 것인데 그건 바로 와인을 안마셔도 된다는 것이었다..! 예를 들어 (6) 100 100 1 1 100 100의 최대 포도주 양은 계단 오르기 문제에서는 301이지만 여기서는 400이 된다. 3번째와 4번째에서는 안마시는게 이득이다. 따라서 if(dp[i]=2) { dp[2]=dp[1]+arr[2]; cnt=2; //연속 두잔을 마심 max=dp[2]; } if(n==3) { if(arr[2]>arr[1]) dp[3]=arr[2]+arr[3]; else { dp[3]=arr[1]+arr[3]; cnt=1; } max=dp[3.. 2023. 7. 24. 이전 1 ··· 16 17 18 19 20 21 22 ··· 26 다음