컴굥일지

문제 https://www.acmicpc.net/problem/1764 문제 내용 듣도 못한 사람 수 n명, 보도 못한 사람 수 m명의 이름이 주어진다. 두 명단에 공통으로 들어있는 사람의 수와 명단을 출력하면 된다. 문제 풀이 이 문제에서 find() 함수를 써서 하면 시간 초과가 난다. n, m의 범위가 모두 500,000 이하의 자연수이기 때문이다. 그렇기 때문에 binary_search()를 사용했다. binary_search()는 정렬된 상태에서 사용 가능하다. 그래서 듣도 못한 사람들의 명단을 sort()한 뒤에 보도 못한 사람이 포함되었는지 binary_search()를 사용해서 확인한다. 만약 듣도 보도 못한 사람이라면 result 벡터에 추가하고 나중에 결과 출력할 때 출력하면 된다. 코..

문제 https://www.acmicpc.net/problem/14425 문제 내용 n개의 문자열로 이루어진 집합에, 그 뒤로 주어지는 문자열들이 몇 개나 포함되어있는지를 구하는 문제이다. 위 사진에서 빨간색으로 묶여있는 문자열들 안에, 그 뒤로 이어지는(파란색) 문자열의 포함 여부를 판단하면 된다. 문제 풀이 문제 자체는 간단하다. 다만 n의 입력 범위가 1~10000, m의 입력 범위가 1~10000이라는 점에서 단순하게 탐색하면 안 된다. m개 입력되는 문자열을 n개의 집합에서 처음부터 매번 찾을 수는 없기 때문이다. (시간 초과 난다) 그렇기 때문에 이 문제에서는 이진 탐색을 사용했다. binary_search()는 정렬된 상태에서 사용이 가능하기 때문에, n개의 문자열 집합을 입력받고 나서 so..