With The Lights Out

https://www.acmicpc.net/problem/4134 4134번: 다음 소수 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. www.acmicpc.net 해결 방법 유명한 소수 판별법을 사용했다. 에라토스테네스의 체를 이용해 sqrt(N) 까지만 나누어 보고 소수인지 아닌지 판별할 수 있었다. 따라서 시간 복잡도도 sqrt(N)이다. 시도해보진 않았지만 범위를 long long 이 아닌 unsigned int 로 하여도 무방할 듯 하다. IsPrime 함수에서 소수를 판별하고, 소수가 아니면 값을 증가시켜 다시 검사해 소수를 찾는다. ※ for문의 i값 범위는 당연히 sqrt(N) 이하지만 양변 제곱을 통해 조건문은 i * i <..

https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 해결 방법 확실히 생각을 오래 하니까 쉬워졌다. 간격을 전부 구해서 배열에 저장한 후 최대공약수를 구해주고 간격을 최대공약수로 나눈 뒤 -1 만큼 해준 숫자를 모두 더해주면 된다. ex) 1 3 7 13 2 4 6 // 간격 1 2 3 // 최대공약수 2로 나눔 0 1 2 // -1 해준다. 답 : 3 #include #include using namespace std; long long ..

https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 해결 방법 유클리드 호제법을 사용했다. 분모끼리 곱해서 우선 약분이 가능하거나 가능하지 않은 한 개의 분수로 만든다. 구해진 분자와 분모를 이용해 유클리드 호제법을 적용하면 최대공약수를 구할 수 있다.(당연히 1일 수 있다) 최대공약수로 분자와 분모를 나누어 주면 끝. 정말 간단했는데... 새삼 알고리즘 구상의 중요성을 느낀다. 턱을 괴고 생각하는 시간을 더 늘려야겠다. #include #include using namespace std; long ..

https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 해결방법 유클리드 호제법으로 해결했다. #include #include #include using namespace std; long long int euclid(long long int a, long long int b) { if (a % b != 0) { return euclid(b, a % b); } else { re..

https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 해결방법 처음엔 비트마스크 연산을 통해서 모든 부분집합을 구한 뒤(공집합 제외), 벡터에 넣은 뒤 unique 연산을 해서 서로 다른 부분집합의 개수만 출력하려 했는데, set 자료형의 특징을 사용하면 그럴 필요가 없다는 것을 깨달았다. set 자료형의 특징 중복된 키를 허용하지 않음 중복된 키를 insert 해도 추가되지 않음 따라서 앞의 원소부터 차례대로 경우의 수를 구해준 뒤 무차별적으로 set 컨테이너에 넣으면, 서로 다른 부분집합만 컨테이너에 남게 된다. ..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 해결 방법 문제가 말하는 것은 '듣도' 와 '보도' 둘 다에 해당하는 원소를 찾아서 출력하라는 것인데, set을 사용하지 않고 벡터로 한 컨테이너에 전부 입력받은 뒤 정렬하고 연속해서 나타나면 출력하도록 풀었다. 정석은 set을 사용하는 것 같은데 아무쪼록 풀었으니 상관없지 싶다. 다른 코드들도 찾아보니 sort는 무조건 하게 되기 때문. #include #include #include usin..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 해결 방법 map 의 키값은 중복을 허용하지 않으므로, 가지고 있는 카드를 입력을 받을 때 이전에 추가한 key인지 확인 후 중복되면 해당 숫자의 value 값을 늘려 주는 방식으로 해결했다. map의 키값은 중복이 안된다는 것을 명심하자. #include #include #include using namespace std; unordered_map m; int..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 해결방법 unordered_map을 통해 쉽게 해결했다. 그냥 map 을 사용하면 해결이 되지 않는다. 왜냐하면 value를 통해 key 를 찾는 과정에서 결국에는 N번만큼의 선형 탐색을 하게 되기 때문이다. 따라서 시간 초과가 뜬다. 처음엔 나도 왜 시간 초과가 뜨나 했지만 map 이 이진탐색트리로 구현되어 삽입 시 자동정렬 된다는 사실을 망각하였었고, 이름만 map..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 해결 방법 벡터에 값을 저장 한 후 정렬 정렬한 뒤 unique 를 이용해 중복 제거 unordered map 에 중복 제거하고 정렬 된 키를 value 와 맞게 대입 본래 배열 순서대로 출력 주안점 unordered_map 은 key:value 를 순서대로 저장하지 않으므로 탐색할 때 시간 복잡도는 1 이다. 그냥 map 은 key 를 기준으로..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 해결 방법 sort는 정렬에 데이터의 순서를 보장하지 않는다. sort는 퀵 정렬을 기반으로 하고, stable_sort 는 합병 정렬을 기반으로 하기 때문에 원소의 순서를 보장한다. 여기서는 가입 순서가 중요하기 때문에, 순서가 바뀌면 안 된다. 따라서 stable_sort 를 사용하면 쉽게 해결 가능하다. #include #include #include using namespace std; vect..