꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/7562 BFS(Breadth First Search) 알고리즘으로만 풀 수 있는 문제였습니다.(DFS 불가능)나이트가 움직일 수 있는 8 방향을 미리 정의한 뒤에 BFS를 통해 현재 위치에서 갈 수 있는 지점을 큐에 집어넣으면서 움직인 횟수를 업데이트하며 풀면 되는 문제였습니다.cache를 모두 INF로 초기화한 뒤에 min(다음 위치에 저장되어 있는 움직인 횟수, 현재 지점까지 움직인 횟수 + 1)을 통해 최소 이동횟수를 구하면 됩니다.pair를 통해 y와 x의 좌표를 저장하였고 start는 시작지점, destination은 도착지점, 그리고 currentPos는 현재 위치의 좌표입니다! #include #include #in..

문제 링크입니다: https://www.acmicpc.net/problem/2468 DFS(Depth First Search) 혹은 BFS(Breadth First Search) 알고리즘을 적용하여 풀 수 있는 문제였습니다.물에 잠기는 높이가 주어지지 않았기 때문에 1~100까지 모두 살피면서 연결된 요소들의 개수 즉, Component 최대 개수를 Brute Force 방식으로 찾아봐야하는 문제였습니다.copy 함수를 통해 물에 잠기지 않는 높이만 area 배열에서 temp 배열로 복사하고 DFS를 통해 Component 개수를 찾아보면 되는데 한 가지 주의할 점은 최소 연결 요소는 1이기 때문에 처음에 result=1로 초기화 한 상태에서 max(result, cnt);를 통해 최대 연결 요소 개수를..

문제 링크입니다: 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의 길이가 되게 ..