꾸준함

문제 링크입니다: 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://algospot.com/judge/problem/read/INSERTION 뒤에서부터 문제를 풀면 쉽게 접근할 수 있는 문제였습니다.마지막 숫자 A[N-1]이 왼쪽으로 몇 칸 움직였는지를 보면 A[N-1]에 어떤 숫자가 들어가야 하는지 알 수 있기 때문입니다.A[i]에 들어갈 수 있는 숫자들의 집합을 저장하기 위해 자료구조로 이진 탐색 트리를 사용할 수 있는데 알고리즘 문제를 풀 때는 직접 구현하는 것보다 보통 STL set나 map을 사용하지만 이들은 k번째 원소를 찾는 기능을 제공하지 않기 때문에 직접 구현한 자료구조 트립을 사용했습니다. 그냥 이진 탐색 트리를 구현했을 경우에는 오름차순이나 내림차순으로 자료가 제공이 된다면 linked list 형태를 띄기 때문에 탐..

문제 링크입니다: 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를 참고하는..