꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/11724 DFS(Depth First Search) 또는 BFS(Breadth First Search) 알고리즘을 사용하여 풀 수 있는 문제였습니다.무방향 그래프(Undirected Graph)이기 때문에 양쪽 정점을 모두 연결해주고 DFS를 통해 연결 요소들의 개수를 찾으면 쉽게 풀 수 있는 문제였습니다. #include #include using namespace std; const int MAX = 1000 + 1; int M, N; vector graph[MAX]; bool visited[MAX]; //전형적인 DFS void DFS(int node) { visited[node] = true; for (int i = 0;..

문제 링크입니다: https://www.acmicpc.net/problem/2583 전형적인 DFS(Depth First Search) 문제였습니다.사실 BFS(Breadth First Search)로도 풀 수 있는 문제였지만 저는 BFS보다 DFS를 더 좋아하는 것 같습니다.문제에서는 컴퓨터의 좌표와 달리 사람들이 주로 쓰는 좌표로 나오지만 회전시키면 컴퓨터에서 표현하는 좌표 형태가 나오기 때문에 딱히 문제 될 것은 없습니다! 주의할 점은 각 영역의 넓이를 구하기 위해 DFS 호출 전에 cnt를 0으로 초기화한 상태에서 호출해야한다는 점입니다. #include #include #include using namespace std; const int MAX = 100; typedef struct { int..

문제 링크입니다: https://www.acmicpc.net/problem/14888 모든 경우의 수를 고려해야하기 때문에 DFS(Depth First Search)를 통해 해결하는 문제였습니다.적절한 조건을 걸고 더하기, 빼기, 곱하기, 나누기를 진행하면 어렵지 않게 풀 수 있는 문제였습니다. #include #include using namespace std; const int MAX = 1000000000 + 1; int N; int number[12], Operator[4]; int maxResult = -MAX, minResult = MAX; void DFS(int plus, int minus, int multiply, int divide, int cnt, int sum) { //연산자를 모두 ..

문제 링크입니다: https://www.acmicpc.net/problem/10448 미리 삼각수를 계산해놓은 뒤에 삼각수 세개를 이용해 만들 수 있는지 판별해주면 되는 문제였습니다.Brute Force 방식으로 찾기 때문에 구현은 어렵지 않았습니다. #include #include using namespace std; vector eureka; //1000보다 작은 삼각수 미리 계산 void preCalculate(void) { int N = 1; while ((N)*(N + 1) / 2 < 1000) { eureka.push_back(N*(N + 1) / 2); N++; } } //삼각수 세개로 만들 수 있는 숫자인지 판별 bool triangleSum(int total) { for (int i = ..

문제 링크입니다: https://www.acmicpc.net/problem/11585 환형문자열에서 부분문자열이 몇 번 일치하는지 구하는 문제이므로 Algospot JAEHASAFE(http://jaimemin.tistory.com/599)의 문제와 상당히 유사한 문제였습니다.환형문자열 유형의 문제들은 주어진 문자열을 2배 즉, 한번 더 이어붙인 상태로 KMP 알고리즘을 수행하는 것이 핵심이였습니다.JAEHASAFE 문제와 달리 몇 번 일치하는지가 중요하므로 return kmpSearch2(doubleOriginal, target)[0]; 대신 return kmpSearch2(doubleOriginal, target).size();를 하여 일치한 횟수를 반환해주는 것이 중요했고 또 분수를 약분해야했기 때..

문제 링크입니다: https://www.acmicpc.net/problem/11403 플로이드-와샬 알고리즘을 적용하여 푸는 문제였습니다.여태까지 풀었던 플로이드 알고리즘 문제와는 달리 자기 자신한테도 가는 경우도 고려하는 것이 핵심이였습니다! #include using namespace std; const int MAX = 100; int N; int graph[MAX][MAX]; void floyd(void) { //i->j로 가는 길이 없어도 //k를 거쳐갈 수 있으면 갈 수 있다고 여긴다 for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (graph[i][k] && graph[k][j]) gr..

문제 링크입니다: https://www.acmicpc.net/problem/5585 그리디 알고리즘을 적용하여 푸는 문제였습니다.동전 배열을 내림차순으로 정렬하고 각 동전을 최대한 많이 사용하면 풀 수 있는 문제였습니다. #include using namespace std; int pay; int coin[] = { 500, 100, 50, 10, 5, 1 }; int minCoin(void) { int total = 1000 - pay; int cnt = 0; //greey하게 접근 for(int i=0; i= 0) { total -= coin[i]; cnt++; if (total == 0) //잔돈을 모두 반환했을 경우 반복문 탈출 break; } return cnt; } int main(void) ..

문제 링크입니다: https://www.acmicpc.net/problem/4354 백준 1701번 Cubeditor(http://jaimemin.tistory.com/629) 문제 처럼 접미사 배열(Suffix Array)를 사용하여 푸는 문제였습니다.문자열의 n 제곱이란 부분문자열을 n번 이어붙였을 때 해당 문자열이 나와야하기 때문에 접두사이면서 접미사인 부분문자열의 길이를 저장하는 벡터 pi를 구합니다.문자열이 S일 때 인덱스가 S.length() - 1 일 때 접두사이면서 접미사인 부분문자열의 길이는 이미 문자열 a를 n번 제곱했을 떄의 부분문자열의 길이일 수 있습니다.즉, S의 길이에서 인덱스가 S.length() - 1 일 때 부분문자열의 길이를 뺀 길이를 n번 제곱했을 때 S의 길이가 되게 ..

문제 링크입니다: https://www.acmicpc.net/problem/1701 접두사도 되면서 접미사도 되는 부분 문자열 중 최대 길이를 구하는 문제였습니다.즉, 백준 1786번 찾기(http://jaimemin.tistory.com/627)에서의 getPartialMatch 함수를 사용하면 되는 문제였습니다.하지만, 함정이 있다면 getPartialMatch 함수는 문자열이 S라고 할 때 S[0]을 시작으로 하는 접두사에 대해서만 조사를 하기 때문에 "abbcbba"와 같은 시스템 케이스가 주어진다면 AC를 받을 수 없습니다.왜냐하면, "abbcbba"에서 원하는 답은 "bb"의 길이 즉, 2인데 getPartialMatch 함수에서는 접두사와 접미사가 모두 되는 문자열은 "a" 뿐이기 때문에 1..

문제 링크입니다: https://www.acmicpc.net/problem/1786 백준 1305번 광고(http://jaimemin.tistory.com/625)와 마찬가지로 KMP 알고리즘을 사용하는 문제였습니다.문제에서 KMP 알고리즘을 설명하고 KMP 알고리즘을 그대로 구현하라고 하기 때문에 "프로그래밍 대회에서 배우는 알고리즘 문제해결전략" 책을 갖고 있다면 수월하게 풀 수 있는 문제라고 생각됩니다.주의할 점은 문제에서 문자열의 인덱스가 0이 아닌 1부터 시작한다고 간주한다는 점과 공백도 문자열에 포함되기 때문에 cin이 아닌 getline을 통해 T와 P를 입력받아야한다는 것입니다! KMP 알고리즘의 보다 자세한 설명은 https://kks227.blog.me/220917078260를 참고하는..