꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/14921 백준 2470번 두 용액(http://jaimemin.tistory.com/680)과 동일한 문제였지만 용액의 합을 출력하는 문제였으므로 더 쉬운 문제였습니다. #include #include #include //LLONG_MAX using namespace std; const int MAX = 100000; int N, idx1, idx2; long long minimum; long long liquid[MAX]; long long sumOf2Liquid(void) { int i = 0, j = N - 1; while (i < j) { long long sum = liquid[i] + liquid[j]; //최소값 갱..

문제 링크입니다: https://www.acmicpc.net/problem/2470 백준 2473번 세 용액(http://jaimemin.tistory.com/679)과 동일한 방법으로 풀면 되는 문제였습니다.범위는 늘어났지만 구하는 용액의 수가 두개이니 비교적 더 쉬운 문제라고 할 수 있습니다. #include #include #include //LLONG_MAX using namespace std; const int MAX = 100000; int N, idx1, idx2; long long minimum; long long liquid[MAX]; void print2Liquid(void) { int i = 0, j = N - 1; while (i < j) { long long sum = liquid..

문제 링크입니다: https://www.acmicpc.net/problem/2473 첫 번째 용액을 기준으로 나머지 두 용액은 양방향 탐색을 통해 세 용액의 합의 최소값을 찾는 문제였습니다.사실 구현보다는 long long 자료형의 최대값을 정의하는데 애를 먹었던 문제였습니다.처음에는 numeric_limits::infinity()로 minimum을 초기화했는데 오답처리를 받아 minimum 값을 확인한 결과 0으로 초기화가 되어있었습니다.따라서, climits 헤더파일을 추가하고 minimum을 LLONG_MAX로 초기화했습니다! #include #include #include //LLONG_MAX using namespace std; const int MAX = 5000; int N, idx1, id..

문제 링크입니다: https://www.acmicpc.net/problem/2563 100 * 100 칸에서 칠해져 있는 칸의 갯수를 세면 되는 문제였습니다. #include #include using namespace std; const int MAX = 100 + 1; int coord[MAX][MAX]; int main(void){ int N; cin >> N; for (int k = 0; k > x >> y; for (int i = y + 1; i

문제 링크입니다: https://www.acmicpc.net/problem/2042 새그먼트 트리를 이용하여 푸는 문제였습니다.종만북 코드에서는 LCA(Longest Common Ancestor)를 구하는 코드이기 때문에 http://jaimemin.tistory.com/662 코드에서 조금 수정을 해야했습니다.주의할 점은, 반환형을 int가 아닌 long long으로 해야 AC를 받을 수 있다는 점입니다. #include #include #include using namespace std; int N, M, K; struct segmentTree { //배열의 길이 int n; //각 구간의 최소치 vector pSum; segmentTree(const vector &array) { n = array...

문제 링크입니다: 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