SM's Development Log

복기전형적인 BFS 문제다. Python3에서 입력 받을 때, list comprehension을 쓰는 것보다 append() 하는 것이 좀 더 빠르게 나왔다. 코드C++ 17 #include #include using namespace std; struct Elem{ int R, C, hadDestructed;}; int N, M;char Map[1001][1001];int Dist[1000][1000][2]; int bfs(){ int dr[] = { -1, 1, 0, 0 }; int dc[] = { 0, 0, -1, 1 }; Dist[0][0][0] = 1; queue q; q.push({ 0, 0, 0 }); while (false == q.empty()) { auto [r, c, hadDestr..

복기세그먼트 트리 문제에 대표적인 문제다. 세그먼트 트리에 대해서는 이 문서를 참고하라. 노드의 의미를 어떻게 설정할지가 관건이다. 코드C++ 17 #include using ll = long long; #define MAX_N 1000000 size_t N, M, K;ll Arr[MAX_N + 1];ll Tree[MAX_N * 4]; // @Desc : Arr의 [s, e]의 합으로 세그먼트 트리를 초기화한다.// @Return : node의 값// @Param// node : 노드 번호// s : 범위의 시작// e : 범위의 마지막ll Init(size_t node, size_t s, size_t e){ // 단말 노드라면 if (s == e) Tree[node] = Arr[s]; // 단말 노드가..

복기처음엔 메모이제이션을 생각했는데, 수학 문제는 해당 수의 규칙성을 잘 발견해야겠다. 코드C++ 17 #include #define M 10007 using uint = unsigned; int main(){ uint n = 0; scanf("%u", &n); // N이 5 미만이라면 분해를 하지 않고 그대로 곱하는 것이 이득이고 // N이 5 이상이라면 3을 가능한 많이 곱하는 것이 이득이다. uint k = 1; while (n >= 5) { k *= 3; k %= M; n -= 3; } printf("%u", (n * k) % M);} C# 6.0 using System;using System.Diagnostics.CodeAnalysis; namespace Csharp{ class Program ..

복기끝나는 시간으로 정렬할 것 코드C++ 17 #include #include using uint = unsigned; struct Meeting{ uint Start; uint End; bool operator

복기- 코드C++ 17 #include #define Max(lhs, rhs) ((lhs) > (rhs) ? (lhs) : (rhs)) int N;int Map[502][502];int Memo[502][502]; // 각 좌표마다 며칠동안 생존 가능한지 메모이제이션한다. int Search(int r, int c){ if (Memo[r][c]) return Memo[r][c]; // 상 if (Map[r - 1][c] > Map[r][c]) Memo[r][c] = Max(Memo[r][c], Search(r - 1, c) + 1); // 하 if (Map[r + 1][c] > Map[r][c]) Memo[r][c] = Max(Memo[r][c], Search(r + 1, c) + 1); // 좌 if ..

복기체스판 문제는 흑과 백으로 나눠서 생각하도록 하자. 또, 말들의 범위를 검사할 때 메모리를 이용하는 방법도 고려해보자. 코드C++ 17 #define _CRT_SECURE_NO_WARNINGS #include #define max(a, b) ((a) > (b) ? (a) : (b)) int N;int Chess[10][10];int Ans[2]; // 아래 변수는 비숍의 범위가 겹치는지 나타내는 변수다.// 이 값이 1이면 다른 비숍과 범위가 겹쳐 거기에 위치시킬 수 없다.int Left[21]; // 좌하단 방향의 대각선int Right[21]; // 우하단 방향의 대각선 // 흑과 백을 구분하기 위한 변수int Criterion; void dfs(int r, int c, int cnt){ // 비..

복기C#의 표준 파일 입출력은 충분히 빠르다. 코드C++ 17 #include #include #include using namespace std; int N;int Permutation[81]; bool IsPromising(int index){ // 검사해야 할 수열의 개수는 N이 2의 배수가 될 때마다 늘어난다. for (size_t i = 1; i N) { for (size_t i = 1; i

복기C#의 String.Split()은 공백 문자 전체를 제거하여 주지는 않으니 유의하자. 코드C++ 17 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); string word; int lineSize = 0; while (cin >> word) { if (word == " ") { cout 80) { cout 80: print('\n') lineSize = 0 print(f"{word} ") lineSize += len(word) + 1

복기- 코드C++ 17 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; cin.ignore(); while (n--) { string line; getline(cin, line); int len = line.size(); bool isPalindrome = true; for (size_t i = 0; i < len / 2; i++) { char left = tolower(line[i]); char right = tolower(line[len - 1 - i]); if (left != right) { isPalindro..

복기버블정렬은 내부 반복문이 끝날 때마다 자리 하나가 고정이 된다. 코드C++ 17 #include #define min(a, b) (a > N; for (size_t i = 0; i > Arr[i]; cin >> S; // 본 문제는 버블정렬을 이용하는 것이다. // 반복이 끝나는 것은 정렬이 다 되었거나, // 교환을 더 이상 할 수 없을 때다. for (size_t i = 0; i < N; i++) { // 교환을 더 할 수 없으면 반복을 종료한다. if (S == 0) break; // 현재 값을 최댓값으로 설정한다. int max = Arr[i], maxIdx = i; // 교환할 수 있는 횟수는 아래와 같다. size_t count = min(N, i + 1 + S)..