알고리즘4 불량 사용자 [2019 카카오 겨울 인턴쉽] C++ DFS Set 을 이용한 풀이 처음엔 단순히 for문으로 완전탐색을 하면 풀릴 줄 알았다. 하지만 생각해보니 user_id와 banned_id의 개수는 총 8개 이하이므로 다중 for문으로는 전체 개수를 구할 수 없었다. 따라서 브루트 포스방식으로 풀려면 DFS를 적용해야했다. 2번 테스트케이스의 예로 들면 user_id의 인덱스는 0부터 4까지이고 banned_id의 인덱스는 0부터 2까지이다. 따라서 user_id의 인덱스 banned_id의 인덱스 012 0 1 2 013 0 1 2 014 0 1 2 023 0 1 2 024 0 1 2 034 0 1 2 021 0 1 2 023 0 1 2 ... 102 0 1 2 103 0 1 2 이런식으로 서로 같은 문자열인지 체크한다. *를 빼고 같은 문자열인지 포문을 돌며 한글자씩 체크한다.. 2020. 9. 12. 경주로 건설 - 카카오 2020 C++ DFS 코딩테스트 풀이 다들 BFS풀고 공식해설도 BFS로 풀었다. BFS로 풀든 DFS로 풀든 상관 없지만 핵심은 완전탐색 과 메모이제이션 이 있어야 시간초과가 나지 않고 정답을 맞출수있다. 완전탐색이라는 방향에서 BFS나 DFS어느것으로 풀어도되는데 많은 블로그에서 DFS로 풀면 틀린다는 듯이 말을 해서 풀이를 올리게 되었다. 충분히 짧은 시간내에 정답이 가능하다. 핵심은 cost배열(메모이제이션) 에 최소비용을 계속 갱신해주고 이 최소비용보다 높다면 그 지점으로 이어지는 경로자체를 return시키는 것이다. #include #include #include int dr[4]={0,1,0,-1}; int dc[4]={1,0,-1,0}; int visited[30][30]={0,}; int cost[30][30]={0,}; u.. 2020. 9. 11. 보석 쇼핑 [카카오 2020 인턴 코딩테스트] C++ 투포인터 간단 명확 풀이 전형적인 투포인터 문제이다. 다음과 같이 for(int i=0;igems.size()) break; } 배열의 범위가 최대 10만 이므로 브루트 포스방식으로 푼다면 O(n^2)이 된다. 이는 정확성 풀이에서는 다 맞출 수 있지만 효율성 풀이에서 통과할 수 없다. 따라서 투포인터 방식으로 다음과 같이 풀어야 한다. 정답 코드 #include #include #include #include #include #include using namespace std; bool comp(pair a,pair b) { if(a.second-a.first == b.second-b.first) return a.first=gems.size()) break; m[gems[hi]]=hi; hi++; } } sort(v.begin.. 2020. 9. 6. 백준 8980번 택배 골드4 그리디 알고리즘으로 풀었다. 받는 마을 기준으로 정렬을 시킨다. 1 5 10 2 3 40 3 4 40 이런경우에도 조건을 만족하려면 받는 마을 기준으로 정렬을 시켜야 최적해를 구할 수 있다. #include #include using namespace std; typedef struct Box { int sendi; int reci; int boxn; } Box; bool comp(Box a,Box b) { if(a.reci==b.reci) return a.sendi >n>>c>>m; Box arr[m]; for(int i=0;i>arr[i].sendi>>arr[i].re.. 2020. 6. 11. 이전 1 다음
