본문 바로가기
반응형

SWE/코테137

[성실코딩 16일차] 백준 #1010 다리 놓기 / DP 조합 ** 쉬운 문제라고 생각했는데 세번째 예제 케이스에서 0으로 답을 출력했다. 뭐가 문제인지 생각해봤는데 unsigned long long result = factorial(m) / factorial(m - n) / factorial(n); 다음 코드에서 long long 은 정수형이니까 정확하게 나눠지지않고 (소수점이 버려짐), 그거에 따라 오차가 발생한다. 따라서 factorial(m-n)을 먼저 나누는지, factorial(n)을 먼저 나누는지에 따라 결과값도 달랐음. 해결책은 질문검색에서 봤는데, 점화식을 계산하는 방식으로 해보라고했다.C(n,m) = C(n-1,m) + C(n-1,m-1) 즉, DP 메모제이션으로 풀라는 말 같다. 오늘말고 다음에 해봐야겠다...... 일단, 틀린 코드라도 #includ.. 2018. 11. 2.
배낭 문제(Knapsack Problem) - 경우의 수(조합) 구하는 방법 Knapsack Problem 냅색 문제 배경 혹은 필요성 예를 들어, 배낭에는 최대 4kg까지 넣을 수 있다. 물건 A~C 중 어느 것을 담아야 할까?방법론 1. 비싼 물건 먼저 차례로 넣는다. 2. 가벼운 물건 먼저 차례로 넣는다.3. 비싼 물건 먼저, 가벼운 물건 먼저 두 가지 방법으로 모두 해보고, 그 중 금액이 비싼 것을 선택한다.=> 세 가지 방법 모두 틀림. 왜냐하면 문제가 아래와 같은 조건으로 주어질 경우, 잘못된 답을 고르게 되기 때문이다. 또 다른 방법론으로 Exhaustive Search가 있다. 모든 경우의 수를 다 확인해보는 방법이다.이 방법을 사용할 경우, 지금 문제의 경우의 수는 A를 배낭에 넣고 안넣고 2가지가 가능하고,B를 배낭에 넣고 안넣고 2가지, C를, D를,,, 해서.. 2018. 10. 31.
[성실코딩 15일차] 백준 #2644 촌수계산 / DFS 헤헤 깔끔하게 풀려서 기분이 좋다 조건들 하나하나 고려하면서 코드짜는 연습하기!! #include #include using namespace std; int n; // 사람 인원 vector arr; // 친척 관계 int visited[101]; // 노드에 방문했는지 int a1, a2;// a1과 a2의 관계 int result = -1; //촌수 // 자기 자신 방문했을 때도 촌수를 증가시켜주므로, // 0이 아니라 -1에서 시작. bool dfs(int _a) { // _a: 사람 번호 result++; // 촌수 증가 visited[_a] = 1; // 방문표시 if (_a == a2) { // 원하는 사람이 나오면 return true; } // 원하는 사람이 아니면 // 연결된 노드들 확.. 2018. 10. 31.
[성실코딩 15일차] 백준 #2583 영역 구하기 / DFS 문제는 쉬운데 보통 배열 인덱스 매기는 방향과 다르게 모눈종이의 왼쪽 아래를 (0,0) 오른쪽 위를 (N,M)로 가정해서 입력을 준다. 그리고 칸으로 수를 증가시키는 게 아니라 꼭지점으로 수를 증가시키고 있음 이런 디테일한 부분 놓치지않고 꼼꼼하게 문제푸는 능력 기르기! #include #include #include using namespace std; int map[101][101] = {}; int m, n; // map의 행, 열 // result int num_area = 0; int temp_area_size = 0; vector area_size; // map 이동 int dx[4] = {0,0,-1,1}; // 열, 상하좌우 int dy[4] = {-1,1,0,0}; // 행 void df.. 2018. 10. 31.
반응형

티스토리툴바