본문 바로가기
반응형

_385

[성실코딩 17일차] 백준 #11866 조세퍼스 문제0 11월2일 금요일이 17일차여야하는데 부산 학술대회 다녀오고 노느라고 못했다ㅜㅜ 그러므로 오늘 일요일인데 17차 메꾸고잇당 허허 원래의 나였으면 이 문제를 풀 수 있는 규칙성이 있을까 엄청 고민했을 것 같은데 귀찮아서인지,,,, 시간제한도 2초나 되니까 그냥 반복적으로 컴퓨터 연산에 맡겼다. 숫자를 출력할 때는 visited 1 표시해서 다시 방문하지 않고 넘어가도록 했다. 다른 사람 코드보니까 대부분 두 개 중 하나 방식으로 푼 것 같다. 1. queue를 구현해서 M-1번째까지는 모두 pop하고 queue 뒤에 다시 push 하는 방법 2. sll로 구현해서 출력하면 해당 노드를 delete하는 방법 내 방식 포함해서 대부분 방식들이 비슷한 시간 복잡도를 가질 것 같다. 그러므로 코드 안짜봐야징 #i.. 2018. 11. 4.
[성실코딩 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.
반응형

티스토리툴바