꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/MEASURETIME 입력하는 숫자의 수가 많기 때문에 삽입정렬을 이용해서 풀 경우 TLE가 발생하지만, 구간합을 간단하게 구할 수 있는 펜윅 트리를 이용해 문제를 해결합니다.각 원소 A[i]에 대해 A[0..i - 1] 구간에 A[i]보다 큰 숫자가 몇 개 있는지 알게 된다면 옆으로 몇 칸 움직일지 계산할 수 있습니다.따라서, 각 숫자의 출현 횟수를 저장하는 펜윅 트리를 만들면 AC를 받을 수 있습니다! #include #include using namespace std; //펜윅 트리의 구현, 가상의 배열 A[]의 부분 합을 //빠르게 구현할 수 있도록 한다. 초기화시에는 A[]의 //원소가 전부 0이라고 생각한..

문제 링크입니다: https://www.acmicpc.net/problem/1987 DFS(Depth First Search) 알고리즘과 백트래킹 기법을 요구하는 문제였기 때문에 visited 배열을 사용하지 않아도 되는 문제였습니다.대신, 문제 조건에 같은 알파벳이 적힌 칸을 두 번 지날 수 없다고 하였으므로 매개변수로 alphabet을 전달하여 비트마스킹 기법을 사용해야하는 문제였습니다.저는 A를 (1 board[i]; result = -1; DFS(0, 0, (long long)1

문제 링크입니다: https://www.acmicpc.net/problem/9466 DFS(Depth First Search) 알고리즘을 사용하여 사이클을 이루지 않는 사람의 수를 구하는 문제였습니다.visited 배열은 기존에 풀었던 DFS 문제들에서도 사용하는 배열이였지만 done 배열은 처음 등장하는 배열입니다.done 배열은 더 이상 이 노드를 방문하지 않을 것을 확신하는 경우에만 true가 됩니다.즉, 이미 방문한 노드이지만(visited[노드] = true) 사이클을 이룰 경우 다시 방문할 가능성이 있기 때문에 (visited[노드] = true && !done[노드])라면 사이클을 이룹니다.사이클이 형성될 경우 사이클에 포함된 노드들의 수를 더하고 전체 학생 수에서 빼면 답을 구할 수 있는 ..

문제 링크입니다: https://www.acmicpc.net/problem/1613 전형적인 플로이드-와샬 알고리즘을 사용하는 문제였습니다.입력을 받을 때 history[일찍 발생한 사건][늦게 발생한 사건] = -1 로 초기화 하고 history[늦게 발생한 사건][일찍 발생한 사건] = 1로 초기화합니다.그리고 플로이드-와샬 알고리즘을 적용하면 간단하게 풀리는 문제였습니다. #include using namespace std; const int MAX = 400 + 1; int N, K; int history[MAX][MAX]; //전형적인 플로이드 void floyd(void) { for(int k=1; k> K; for (int i = 0; i < K; i++) { int first, second..

문제 링크입니다: https://www.acmicpc.net/problem/1764 정렬된 듣도 못한 사람의 리스트를 탐색할 때 시간 복잡도가 O(N)인 find 함수를 사용하면 TLE가 발생하는 문제였습니다.따라서 이진 탐색(binary search) 함수를 직접 구현하여 듣도 못하고 보도 못한 사람을 result 벡터에 추가했습니다,주의할 점은, 이진 탐색을 하기 때문에 v 벡터도 정렬해야하고 사전 순서대로 출력해야하기 때문에 result 벡터도 정렬해야한다는 점입니다! #include #include #include #include using namespace std; int N, M; vector v; //듣도 못한 사람의 리스트 //이진 탐색 bool binarySearch(int low, in..

문제 링크입니다: https://www.acmicpc.net/problem/2960 기존에 구현을 한 에라토스테네스의 체 코드에서 살짝 변형만 시키면 쉽게 AC를 받을 수 있는 코드였습니다.기존의 에라토스테네스의 체 코드는 소수를 찾는 것이 목적이였다면 이번 문제는 해당 숫자가 몇 번째로 지워지는지를 찾기 때문에 반복문에서 종결 조건을 i * i K; cout

문제 링크입니다: https://www.acmicpc.net/problem/4948 간단한 에라토스테네스의 체를 사용하여 소수를 찾는 문제였습니다.주의할 점은 입력 받은 숫자부터 시작이 아닌 (입력 받은 숫자 + 1)부터 소수의 갯수를 센다는 점입니다! #include using namespace std; const int MAX = 123456 * 2 + 1; int minFactor[MAX]; //minFactor[i] -> i의 가장 작은 소인수(i가 소수인 경우 자기 자신) //에라토스테네스의 체 void eratosthenes(void) { //1은 항상 예외 minFactor[0] = minFactor[1] = -1; //모든 숫자를 처음에는 소수로 표시 for (int i = 2; i < M..

문제 링크입니다: https://www.acmicpc.net/problem/10798 생각보다 구현하기 힘든 구현 문제였습니다.코드 자체는 간단하니 코드를 참고하면 쉽게 이해가 가는 문제입니다. #include #include #include using namespace std; string word[5]; int main(void) { for (int i = 0; i > word[i]; for (int i = 0; i < 15; i++) //최대 15 글자 for (int j = 0; j < 5; j++) if (i < word[j].size()) //word[j]의 인덱스 범위 내에서만 출력 cout

문제 링크입니다: https://www.acmicpc.net/problem/1924 간단한 구현 문제였습니다.1. 해당 달 전까지의 누적 일 수를 더합니다.2. 해당 달의 일 수를 더합니다.3. 모듈러 연산을 통해 요일을 출력합니다. #include using namespace std; int x, y; int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; int main(void) { cin >> x >> y; int day = 0; for (int i = 0; i < x; i++) day += month[i]; //우선 해당 달 전까지 누적 일 수를 더하고 day += (y - 1); //해당 달의 일 수를 더한다 switch (..

문제 링크입니다: https://www.acmicpc.net/problem/1018 체스판은 (0,0)에 W가 오는 경우가 있고 B가 오는 경우가 있습니다.따라서 두 가지 경우의 체스판을 미리 선언해놓고 하나하나 Brute Force 방식으로 비교하면 쉽게 풀 수 있는 문제였습니다.비교하는 범위가 초과하지 않도록만 한다면 딱히 주의할 점은 없는 것 같습니다! #include #include #include using namespace std; const int INF = 987654321; const int MAX = 50; int M, N; string board[MAX]; //(0, 0)이 W인 체스보드 string whiteFirst[8] = { { "WBWBWBWB" }, { "BWBWBWBW" ..