안녕 세상아,

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 전형적인 백트래킹 문제이다. N과 M 문제 풀어봤으면 걍 눈 감고도 풀기 가능하다. https://hello-world-cpp.tistory.com/2 [백준/c++] 15649 N과 M(1) https://www.acmicpc.net/problem/15649 전형적인 백트래킹 문제,, DFS를 참고해서 풀면 된다. 중복도 허용하기 때문에 백트래킹계의 순열이라고 볼 수 있다. DFS의 재귀를 이용하여 풀었다. 자세한 설명은 코 hello-world-cpp.tistory.com 여기 더 ..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이번 시리즈는 새로운 배열을 하나 만들고 입력받는 그러한 과정만 거치면 N과 M (1)과 똑같다. 배열 값을 입력 받은 후 sort만 해주면 된다. 계속 풀다보니까 백트래킹을 100중에 3정도는 알 것 같은 느낌이다. 다양한 문제를 더 풀다보면 갑자기 어느순간 확 느는 느낌을 받을 수 있길 바라며.. #include #include #include using namespace std; i..

set, map의 차이는 set은 key값만 저장하고 map은 key값과 value를 저장한다. set과 map 둘 다 중복을 허용하지 않는다. 또한, 둘 다 컨테이너 내부에서 오름차순으로 정렬 된다. ​ std::set 컨테이너 template class set; ​ key 타임의 키(key) 값을 저장하는 연관 컨테이너 저장된 데이터는 키 값을 기준으로 정렬됨 (오름차순) 데이터 삽입, 삭제, 탐색은 0(log n) 시간 복잡도로 동작 (균형잡힌 이진탐색트리 사용) 중복되는 데이터를 set구조로 저장하려면 std::multiset 컨테이너 사용 데이터 정렬되지 않은 상태로 저장하려면 std::unordered_set 컨테이너 사용 #include 에 정의 begin(), end(), rbegin(),..

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 생각보다 간단하게 풀렸던 것 같다. 입력값의 범위가 N, M 모두 최대 10,000이기 때문에 최악의 경우 10의 8승까지 나오게 될 것 같아서 겁 먹고 시작했지만 간단하게 풀렸다. 2중 for문을 사용하면 시간초과가 될 것이기에 신경쓰면서 풀었던 것 같다. vector를 사용하면 시간초과가 나기 때문에 set을 사용하는 것이 좋을 것 같다. 그냥 set을 사용해도..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 내 기준 어려웠다. 내가 구현에 특히 약한 것 같긴 하다. 사실 약하지 않은 부분 없음 예시를 보고 왜 이런 답이 나오는지 수식을 짜기가 어려웠다. 결국 공식은 : (같은 종류 의상의 수 + 1) - 1 이다. 여기서 -1을 해주는 이유는 알몸일 때를 빼주는 것이다. ex) headgear=3, face=..

에라토스테네스의 체는 유명한 소수 구하기 문제이다. 시간 복잡도가 O(N^1/2)이기 때문에 많은 양의 소수를 구할 때 유용하게 사용할 수 있다. 원리는 간단하다. 2의 배수인 수를 모두 지운 후 2는 옆에 적어준다. 이후 지워지지 않은 가장 작은 수(n) 부터 n의 배수를 지워주고 n을 옆에 적어주면 된다. #include using namespace std; int n = 120; int main() { ios::syn_with_studio(false); cin.tie(NULL); cout.tie(NULL); int arr[121]; //배열에 값 입력 for (int i = 2; i

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net min값을 가장 크게 두고 계속 작은 값 갱신하면서 곱해주면 된다. #include #include #include using namespace std; long long int street[100001];//도시 간 거리 long long int oil[100001];//리터 당 가격 int main() { ios::sync_with_stdio(false); cin.tie(NULL..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 큐의 양쪽에서 삽입 삭제가 이루어지기 때문에 deque를 사용해야한다. deque를 사용해야하는 것은 쉽게 알 수 있다. dq 크기의 반 이하인지, 이상인지 구해야하지만 괜히 복잡하게 생각해서 함수 두개 따로 만들어서 min값 받으려고 했다. 하다보니까 뭔가 이상하고 잘 안돼서 노선 바꿈..물론 이런 방법으로도 풀 수 있겠지만 푸는 사람이 많이 없는 이유가 있겠지..? 암튼 정답 코드는 입력받..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 그냥 쉽게 생각해서 2중 for문 사용했는데 역시나 시간초과로 틀림 ㅎㅎ;; 틀리는게 당연함 입력값 최대가 N, M 둘다 100,000임 #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int..

구조체를 정렬할 때 벡터로 변환해서 정렬하면 편하다. struct 입력 받는 것도 벡터를 이용해서 받으면 돼서 따로 문법을 외우지 않아도 된다. 역시 벡터가 짱인듯? ​ 하지만 일반적인 벡터와 달리 조건이 있어야한다. 조건 없이 하면 에러가 나면서 작동하지 않는다. #include #include #include #include using namespace std; struct Person { string name; int kor, eng, math; }; bool compare(Person p1, Person p2) { if (p1.kor == p2.kor && p1.eng == p2.eng && p1.math == p2.math) return p1.name < p2.name; if (p1.kor ==..