본문 바로가기
반응형

25분2

[BaekJoon/백준] 1764번 C++ 두 문자열 목록 중 겹치는걸 찾는 문제다. 찾기를 시도할 때 find 함수를 시간복잡도 O(N)으로 하게 되면 총 시간복잡도가 O(N^2)이 되어서 시간초과가 날 것이다. 이 문제는 이진탐색 = 이분탐색을 시도해야한다. 실수할 수 있는 점은, '문제에서 출력 결과를 사전순으로 요청한 것' 여기서 나도 틀렸다. #include #include #include using namespace std; vector str; vector result; int N, M; bool compare(string a, string b) { return a < b; } bool bin_search(int n, string key) { int pl = 0; int pr = n - 1; int pc; do { pc = (pl +.. 2021. 3. 30.
[BaekJoon/백준] 10816번 C++ 문제는 두 가지 방법으로 풀었다. 감이 왔다가, 다시 헷갈렸다가... 조금 헤맸다. 결국에 처음 왔던 감 대로 도수분포표 정렬 할 때의 방식을 응용해서 풀었다. 정수 범위가 -10,000,000 ~ +10,000,000 이므로 20,000,000 이라고 보면 되고 int는 4바이트니까 총 80,000,000 byte의 공간이 필요한데, 메모리 제한이 256MB이므로 충분하다고 판단했다. 입출력은 속도가 빠른 C의 입출력을 가져와 썼다. #include #include using namespace std; int arr[20000000]; int main() { int N, M, temp; scanf("%d", &N); for(int i = 0; i < N; i++) { scanf("%d", &temp);.. 2021. 3. 21.
반응형

티스토리툴바