tmi)2022년의 개강날이다. 3학년의 시작이다. OT가 끝나서 시간이 좀 비어서 중도에서 코딩 한문제 풀고 올린다. https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 사고과정) 우선 처음엔 당연히 M~N까지 2부터 M까지 쭈우욱 돌려보려했다. 하지만 이럴 경우 반복문이 두 개 이므로 O(N^2)이다. 저번에 소수 관련해서 포스팅을 올릴 때 , 에르테스토노스의 체? 라는 방법을 공지했다. 1 2 4 8 16이 16의 약수인데 어차피 16의 제곱근인 2 4로 나뉘어지는 거면 자..
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 처음의 생각은 초기 상태도 생각해줘야하니, 초기 상태에서의 최대 갯수를 구하려했다.(예시 2) 하지만 생각해보면 PPPP에서 오른쪽으로 2개 교환해도 결국엔 같으니, 그건 의미없다 판단. 오른쪽으로 한번 OR 아래로 한번 교체를 해주면 결국엔 모든 사탕을 교체할 수 있으니, 케이스가 2가지다. 교체를 하고, 확인하고 , 다시 원상태를 위한 교체를 해줘야한다. 안해주면 다음 번 케이스를 하려 할 때 이미 바뀐 거로 해야하니 오류가 남. #include #include #include using namespace st..
https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 사고과정) 1. (A집합 갯수 - 교집합 갯수 ) + (B집합 갯수 - 교집합 갯수) 하면 되겠구나. 그러면 교집합을 만들어야하네. 2. A와 B를 서로 비교해가면서 같은 걸 교집합 배열에 넣어야겠다. - > 여기서 문제 봉착. 원소의 갯수가 너무 크고(각 200,000)이다 보니 이중 반복문으로 일일이 반복하면 시간복잡도(n^2)이라 너무 시간이 오래 걸려서 시간 초과가 뜸. 3. 그렇다면..
