Algorithm(코딩테스트)/정렬3 [백준] 7795 : 먹을 것인가 먹힐 것인가 문제 문제 분석 - 시간 제한이 1초이므로 C++에서는 약 5억 번의 연산을 넘기면 안된다. 그런데, N과 M의 범위가 2만이므로, 다중 for문을 사용하게 되면 2억의 연산을 하게 된다. 이를 T 번 하게 되므로 시간 초과가 발생한다. - 처음에는 for 루프를 돌면서 A의 각각 숫자가 B의 숫자보다 크다면 +1을 하여 그 횟수를 세어주었다. 결론적으로, 아래와 같은 코드로 시간 초과를 받았다. // 오답 코드 : 시간 초과 (테스트 케이스 개수가 정해지지 않았고 T * O(N^2) 연산에서 2억번 미만의 연산이 나오지 않을 가능성이 높다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); c.. 2024. 2. 13. [백준] 10825 : 국영수 (C++) 문제 문제 분석 #정렬 #구조체/클래스 - 이전에는 넣어야 하는 자료가 2개, 3개여서 pair, tuple에 담으면 됐으나 이제는 담아야 하는 자료가 4개이다. - 담아야 하는 자료가 많은 경우 구조체나 클래스를 사용하면 된다. - 클래스를 사용할 경우 접근 제한 지정자를 지정하지 않으면 자동으로 private으로 되므로 public으로 바꿔주어야 한다. - 오름차순일 경우 return을 '>' 으로, 내림차순일 경우 return을 ' 2024. 2. 9. [백준 2910번] 빈도 정렬 (C++) 문제 문제 분석 - 먼저 C의 값이 높다. 이 점을 유념해서 봐야한다. (단, 자료형은 int 형을 사용해도 된다. 21억을 넘진 않기 때문이다.) [방법1] 자료를 저장할 때 배열의 인덱스로 접근하는 방식으로 문제를 해결한다면 메모리 초과가 날 것이다. => 왜냐하면 배열은 먼저 메모리에 할당을 해야 값을 넣을 수 있기 때문이다. [방법2] 이런 문제를 해결하기 위해 insert가 될 때마다 메모리에 할당하는 map 자료구조를 사용하면 메세지의 최대 길이는 1000이므로 메모리 문제가 해결된다. 그러나 map/set과 같은 해시 자료구조는 넣은 순서대로 저장되지 않는다. (vector, tuple, pair의 자료구조는 넣은 순서대로 저장된다.) [방법3] 방법1과 방법2에서 도출되었던 문제를 바탕으로.. 2024. 2. 7. 이전 1 다음
