재원블로그 재원블로그

코딩테스트 고득점 Kit 완전탐색 Level 2 카펫 문제이다. 이 문제는 완전 탐색으로 푸는 문제지만, 완전 탐색을 하는 기준이 중요한 문제이다. 처음에는 가로와 세로의 길이에 대한 완전 탐색으로 풀려고 했지만, 이는 최악의 경우 5000 * 2000000 = 100억번의 연산을 할 수도 있으므로 시간 초과가 난다. 그래서 yellow의 개수를 알고 있고, 이 안에서 가로 세로 길이를 정해놓으면 자연스럽게 brown의 개수도 나오므로 이를 통해 문제를 풀었다. #include #include using namespace std; vector solution(int brown, int yellow) { vector answer; for (int i = yellow; i >= 1; i--) { int wi..

코딩테스트 고득점 Kit 완전탐색 Level 2 문제 소수 찾기 풀이이다. 이 문제는 string 으로 주어진 0 ~ 9 까지의 숫자를 조합하여 소수가 되는 모든 경우의 수를 구하는 문제이다. 숫자가 아무리 커도 9999999 까지밖에 안되므로 전역 배열 isPrime을 선언하여 에라토스테네스의 체를 이용하여 소수를 구하고, 숫자들의 조합을 완전 탐색으로 구한 뒤 그 숫자가 소수이면 map에 저장하여 최종적으로 map.size() 를 통해 답을 구했다. #include #include #include using namespace std; #define MAX 9999999 bool isPrime[MAX + 1]; map m; void makePrime() { for (int i = 2; i

코딩테스트 고득점 Kit 정렬 Level 2 문제 H-Index 풀이이다. 이 문제는 정렬 파트에 있지만 사실 논문 수가 최대 1000개, 인용 수가 최대 10000번 이므로 완전 탐색으로 풀어도 10000 * 1000 = 10000000 이므로 1초를 넘지 않는다. 따라서 굳이 sort를 하지 않아도 되는 문제이다. #include #include #include using namespace std; int solution(vector citations) { int answer = 0; int citaSize = citations.size(); sort(citations.begin(), citations.end()); for (int h = 0; h = h) { orMore++; } } if (orMo..

코딩테스트 고득점 Kit 정렬 Level 2 문제 가장 큰 수 풀이이다. 처음에는 numbers 의 각 원소를 string으로 바꾸고, 이 때 4자리를 맞춰서 바꾼 뒤 정렬하여 풀었는데, 시간도 많이 소요되고 애초에 정답이 아니었다. 구글링을 통해 numbers 를 정렬할 때 to_string() 으로 바꾼 뒤 둘을 합친 결과가 큰 쪽으로 내림차순 정렬을 하면 쉽게 풀렸다. string 비교 연산이 사전순으로 비교해준다는 사실을 잊어 어렵게 풀었다. #include #include #include using namespace std; bool compare(int a, int b) { string tempA = to_string(a); string tempB = to_string(b); return te..

코딩테스트 고득점 Kit의 힙에서 Level 2단계 문제인 더 맵게이다. 우선순위 큐를 이용한 아주 기초적인 문제였다. 기억해야 할 점은 C++ STL 에서 priority_queue는 디폴트로 최대 힙이다. 따라서 최소 힙으로 만들기 위해서는 priority_queue pq; 와 같이 선언해야 한다. #include #include #include using namespace std; int makeScoville(vector& scoville, int k) { int result = 0; priority_queue pq; for (int i = 0; i = 2..

코딩테스트 고득점 Kit의 깊이/너비 우선 탐색(DFS/BFS)에 있는 Level 2 문제 게임 맵 최단거리이다. 이 문제는 기초적인 BFS 개념만 있으면 풀 수 있는 문제이다. #include #include #include using namespace std; int dy[] = {-1, 0, 1, 0}; int dx[] = {0, -1, 0, 1}; bool inRange(int y, int x, int n, int m) { if (y >= 0 && y = 0 && x < m) { return true; } return false; } int bfs(int startY, int startX, vector& maps) { int n = maps.size(); int m = maps[..