노는 게 제일 좋아

백트래킹의 전형적인 문제 조건을 잘 읽어야 하는 문제 https://www.acmicpc.net/problem/15654 #맞은 풀이 #include #include #include using namespace std; int N, M; vector vec; vector ans; bool check[8]; void func(int cnt) { if (cnt == M) { for (auto v : ans) { cout > M; for (int i = 0; i > a; vec.push_back(a); } sort(vec.begin(), vec.end()); // 오름차순정렬 func(0); } 다 비슷한 문제다. 이러한 N이 다 다른 숫자가 주어져서 그렇지 만약 중..

왜 DP 알고리즘 분류에 들어있는지 모를 문제 https://www.acmicpc.net/problem/4963 테스트 케이스가 많은 문제는 어차피 하나에 대해서 풀 수 있다면 모조리 풀 수 있고 ios::sync_with_stdio(0); cin.tie(0); 을 꼭 써주자. 이건 그냥 따로 공부할 필요도 없다. 그냥 대각선까지 가능한 BFS를 풀면된다. 탐색을 4방향에서 8방향으로 늘리면 되는 문제다. 다를게 하나도 없다. #맞은 풀이 #include #include #include #define X first #define Y second //8방향으로 이동가능 제자리 빼고 int dx[8] = {1,1,1,0,0,-1,-1,-1}; int dy[8] = {-1,0,1,-1,1,-1,0,1}; us..

Example에서 그냥 의미있는 것들만 남김 1. binary_search() https://en.cppreference.com/w/cpp/algorithm/binary_search int main() { std::vector haystack {1, 3, 4, 5, 9}; std::vector needles {1, 2, 3}; for (auto needle : needles) { std::cout

앞서 나온 자료구조보다 해시 테이블은 비교적 빠른 탐색 속도를 가지고 있다. 어떻게 그렇게 될 수 있는지 알아보고 어떤 자료를 표현하기에 적합한지 생각해보자 또한 여기선 lookup 이라는 용어를 알 수 있다. lookup은 조회로 해석되는데 특정 원소가 컨테이너에 있는지 확인하거나 컨테이너 키 값에 해당하는 value를 찾는 작업을 말한다. 단적으로 배열에선.. 어떠한 것이 있는지 알려면 O(N)의 시간이 걸린다. 왜냐하면 모든 것을 살펴봐야 하기 때문이다. 그렇다면 얘는 어떤 방식이길래 그것보다 빠를 수 있을지 생각해보자 앞서 배운 이진 탐색을 생각했다면 똑똑한 사람이다. [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 이진탐색, Binary Search 하지만 여기서 알..

[CS Interview] - 비선형 자료구조를 사용하는 이유 우리는 선형구조만으로 모든 것을 표현하지 못한다. 그래서 Tree를 그려내었고 Tree는 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에 순환 또는 원형의 종속성을 표현할 수 없다. 때문에 우리는 또 다른 자료구조인 Graph를 구현하고자 한다. 즉, 노드 간의 더 자세한 경로의 표현을 하고싶다면 Tree 보다는 Graph가 더 적합한 자료구조라고 할 수 있다. Graph는 우선 노드에 대한 데이터를 가지고 있을 뿐만 아니라 노드 간의 간선 데이터도 가지고 있어야 한다. 즉, 해당 노드의 값과 해당 노드와 연결된 노드에 대한 정보를 가지고 있어야 한다는 것이다. edge, 간선은 무방향, 일방향 이 존재하고 해당 edge에..

전형적인 DP문제다. 처음엔 백트래킹으로 풀려했으나.. 개수가..너무 많아서 백트래킹을 어떻게 캐시로 저장할까하다가.. 방향을 틀었다. https://www.acmicpc.net/problem/11052 #처음 틀린풀이 #include using namespace std; int N; int card[1001]; int dp[1005][1005]; //카드를 살 때, 카드 수는 적되 가격은 높게 사야한다. //현재 카드가 i개 가지고 있고 카드의 수와 가격을 보면서 골라야 한다. //결국 다 뒤져봐야함 int M = -1; //최댓값 int x = 0; int func(int cnt, int val){ if(dp[cnt][x] > 0) return dp[cnt][x]; //종료조건 if(cnt > N)r..

음 아주 어렵진 않지만 생각하기 어려운 문제다. https://www.acmicpc.net/problem/12865 #맞은 풀이 #include using namespace std; //가장 가치가 크게 해야함. 가장 큰 무게가 가장 큰 가치를 보장하지 않음 //모든 것을 보고 넣을 지 말 지 정해야 함. (Brute Force지만).. 정말 다조사하면 시간초과남 //똑똑하게 조사해야함. 2^100 연산이 필요. 캐싱 필요( 값 저장) // 담을 수 있는지, 없는지 // 담을 수 있다면 담는 것이 좋은지, 아닌지 int weight[101]; // 무게 int value[101]; // 가치 int N,M; // 개수, 최대무게 int dp[102][100001]; // 값 저장 //재귀를 이용한 풀이 ..

정말 느낌대로 풀면 되는 풀이지만 검증을 해야한다 사실.. https://www.acmicpc.net/problem/1026 #맞은 풀이 #include #include #include using namespace std; int N; vector vec; vector target; int main(){ cin >> N; //A숫자 for(int i = 1; i> a; vec.push_back(a); } //B숫자 for(int i = 1; i > b; target.push_back(b); } sort(target.begin(), target.end()); // 오름차순 sort(vec.begin(), vec.end()); // 오름차순 reverse(vec.begin(),vec.end()); // 내림..

음.. 그냥 생각하고 푸는 문제다. 수학문제같다. 메모리가 192다. 128 + 64 를 의도한 건지는 모르겠다. https://www.acmicpc.net/problem/2217 #맞은 풀이 #include #include #include using namespace std; int N; int size; vector vec; int M = 0; int main(){ cin >> N; size = N; while(N--){ int a; cin >> a; vec.push_back(a); } sort(vec.begin(),vec.end()); // 오름차순 정렬 //큰 것부터 차례로 더함 for(int i = 1; i

이 문제도 백트래킹으로 어렵지 않은 문제다. 다만 출력 조건에 맞게끔 선택하려면 선택 과정에서 필터가 있어야 한다. https://www.acmicpc.net/problem/15657 #맞은 풀이 #include #include //N개의 수를 담을 벡터 #include //오름차순 정렬 using namespace std; int N,M; vector vec; // N개의 수를 담을 벡터 vector ans; // 수열을 넣을 벡터 void func(int cnt){ if(cnt == M){ //M개 골랐다면 출력 for(int a : ans){ cout a; vec.push_back(a); } sort(vec.begin(), vec.end()); func(0); } 여기선 필터가 이미 선택한 숫자보다..