[프로그래머스] 소수찾기 c++
알고리즘 생각한 알고리즘을 다음 세가지 단계로 나눴다. 1. 받은 종이조각의 숫자들을 하나하나 배열에 넣어서, 만들 수 있는 모든 숫자 조합을 구하기(next_permutation사용). 2. 011과 11이 같은 숫자인 것처럼, 중복을 제거하기 3. 에라토스테네스의 체를 이용해서 소수판별하기 정리 만들 수 있는 숫자 조합을 모두 구하는 과정에서 가령 1,2,0의 숫자가 있을 경우에 순열(next_permutation)로 120, 102, 210, 201, 012, 021의 숫자를 만든 후에, 각자의 숫자에 대해서 숫자를 하나씩 더해가면서 (120의 경우 1, 12, 120 세개의 수를 만들 수 있다.) 모든 숫자조합을 만들 수 있었다. STL이 지원하는 vector의 기능들에 대해서 잘 사용해볼 수 있..
2022. 9. 30.
[개념정리] 조합(Combination) 직접 구현해보기
아래의 [백준] 14052번 문제를 풀다가 개념을 정리해보았다. https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 주어진 숫자들에 대해서 조합을 하고, 조합된 숫자들에 대해서 문제를 풀어나가야 하는 상황에서 STL을 사용해서 문제를 풀자니 코드 재활용이 안되고, 과정이 머릿속에서 그려지지 않을 것 같아서 c++코드로 조합(Combination)을 구현해보았다. 문제 상황 (1,4), (5,2), (9,4), (8,3) ... 와 같이 두개의 숫자로 이루어진 ..
2022. 9. 6.
[백준] 18870 좌표압축
계속 이진탐색을 활용한 정렬문제를 풀다보니 저절로 이진탐색이 떠올랐다.. 해당 원소가 나머지 원소들과 비교했을 때 몇번째로 크냐?? 를 묻는 문제이므로, vector를 정렬한 후에 저장된 원소를 하나씩 꺼내면서 이진탐색을 진행한다. 단, v에서 중복원소를 지워야해서 좀 까다로웠다. 처음 set을 사용했다가 std::set은 배열과같이 indexing이 안되므로 복잡해질거같아서 vector의 erase함수를 이용하기로 했다. v.erase(unique(v.begin(),v.end()),v.end()); 먼저 unique(v.begin(),v.end())는 가령 [3,3,4,1,5,5]배열이 있을 때 [3,4,1,5,5,5]로 만들어준다. 즉, unique 함수를 적용하면 위와 같이 중복된 원소를 제거하며 ..
2022. 4. 20.
