노는 게 제일 좋아

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다. https://www.acmicpc.net/problem/1260 이것은 그냥 뭐..그냥 구현하면 된다. 다만 여기서 주의할 점은 방문을 언제할 것이냐를 판단하느냐 문제다. 나머진 어렵지 않다. 그냥 머릿속에서 생각하는 그대로 구현한다. #include #include #include using namespace std; int N, M, V; // 정점, 간선, 시작 노드 int map[1001][1001]; int visited[1001]; int backup[1001]; queue Q; stack S; void copy(int origin[1001], int backup[1001]) { for (int i = 1; i > N >> M >> V;..

바로 생각한 대로 실행하면 되는 문제다. https://www.acmicpc.net/problem/2003 우선 N~M번째 까지의 합은 1~M - 1~N-1 인것을 나는 이용했다. 하지만 이제부터는 잘한 사람들에게서도 나와 무엇이 다른지 공부하기로 했다 우선 나의 풀이를 보고 다른 잘한 사람들의 풀이를 비교해보자 #맞은 풀이 #include using namespace std; int N,M; int arr[10001]; int dp[10001]; // dp[i] -> 1~i번째까지의 합 // N~M 까지의 합은 1~M번째 까지의 합 - 1~N-1 번째까지의 합. int main(){ cin >> N >> M; int cnt = 0; for(int i=1; i> arr[i]; dp[i] = dp[i-1]..

https://www.acmicpc.net/problem/1094 처음에 생각했을 때.. 이진법? 생각났다. 문제를 읽고 예를 읽어보니 맞다. 즉, 이진법 수에서 1의 개수를 구하는 문제다. 즉, 우리가 이진법 변환을 어떻게 했는지 생각해봤다. 2로 나누면서 나머지를 세었다. 마지막까지 2로 나누어서 숫자를 판단했다. 코딩도 그렇게 했다. #include using namespace std; int N; int main() { cin >> N; int sum = 0; while (N >= 1) { sum += N % 2; N /= 2; } cout

1초지만 은근히 숫자가 적어서 해볼만하다 생각한 문제 https://www.acmicpc.net/problem/18111 처음에 든 생각은.. 다 조사해볼 생각은 안했고.. 어떠한 것이 가장 최소 시간을 가질지 계산해보기로 했다. 당연히 모든 블럭에 대한 평균 높이로 만드는 것이 최소시간이 걸릴 것이라 생각했다. 뭐 시간이 달라서 틀린 생각이 되었고 또한 답이 같을 경우 높이가 높은 것 까지 조사해봐야 했으므로 전수조사를 해야했다. brute force란다. 처음에 틀린 풀이를 보자 #include #include using namespace std; int N, M, B; //(1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 10^7) int minh = 257; int maxh = -1; int..

정의는 정점의 집합 V와 가중치를 갖는 간선의 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하시오 다시 쉽게 말하면 최소 비용으로 모두를 잇는 방법이라고 볼 수 있다. 아래 그림을 보자 어떤 알고리즘에 의해 만들어졌을까? **이 아이디어는 Kruskal's Algorithm이라고도 부른다. 매 반복마다 최소 값을 꺼내기 때문에 Greedy라고도 부른다. 1. 그래프의 주어진 모든 간선을 최소힙(Min Heap) H 에 추가한다. 2. H로부터 간선, e을 하나 꺼낸다. 3. 해당 간선의 양 끝점이 T에 있는 경우 e 때문에 cycle이 발생할 수 있으니 e를 버리고 다시 2 단계로 돌아간다. 4. 해당 간선을 T, 트리에 추가시키고 ..

백트래킹의 전형적인 문제 조건을 잘 읽어야 하는 문제 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에..