꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/9184 문제에서 기저 사례 2가지와 조건 2가지를 모두 제공했기 때문에 매우 쉬운 DP 문제였습니다. #include #include //memset using namespace std; const int MAX = 20 + 1; int a, b, c; int cache[MAX][MAX][MAX]; int w(int a, int b, int c) { //문제에서 제시한 기저 사례 2가지 if (a = MAX) return w(20, 20, 20); int &result = cache[a][b][c]; if (result != 0) return result; //나머지 조건 2가지 if (a < b && b < c) result ..

문제 링크입니다: https://www.acmicpc.net/problem/1793 http://jaimemin.tistory.com/401와 똑같은 문제였지만 모듈러 연산을 하는 대신 해당 경우의 수를 전부 출력해야했기 때문에 까다로운 문제였습니다.테스트 케이스 N=100, 200은 long long 자료형으로도 커버가 안되는 숫자이기 때문에 직접 string으로 구현해야하는 문제였습니다.밑변이 2인 사각형(2*2, 2*1) 두 가지, 밑변이 1인 사각형(1*2) 한 가지가 있기 때문에 string끼리 더하는 함수를 구현한 다음 bigNumAdd(bigNumAdd(cache[i - 2], cache[i - 2]), cache[i - 1])를 호출하여 모든 경우를 계산하면 되는 문제였습니다. 주의할 점은..

문제 링크입니다: https://www.acmicpc.net/problem/5719 알고리즘 자체를 구상하는데는 큰 어려움이 없는 문제입니다.1. 우선, 다익스트라 알고리즘을 통해 source->destination까지의 최단 경로를 구합니다.2. 해당 최단 경로를 삭제합니다.3. 다시 다익스트라 알고리즘을 통해 source->destination까지의 최단 경로를 구합니다. 1번은 http://jaimemin.tistory.com/555에서 이미 다익스트라 알고리즘을 구현한 적이 있기 때문에 쉽게 할 수 있었지만 2번이 문제였습니다.최단 경로를 어떻게 삭제할지 고민하다가 crocus님의 블로그(http://www.crocus.co.kr/682)를 참고한 결과 BFS를 이용해 최단 경로를 삭제할 수 있다..

겉보기에는 간단한 BFS 문제처럼 보이지만 메모리 제한이 128MB인 것이 함정인 문제였습니다.우선, 아래는 메모리 초과가 발생한 코드입니다. #include #include #include #include using namespace std; const int INF = 987654321; const int MAX = 100000 + 1; int N, K, M; vector station[MAX]; int hyperTube[1000 + 1]; int cache[MAX]; //해당 인덱스에 도달하는데 지나친 역 수 void initialize(void) { //min(cache[next], cache[here]+1)을 위해 INF로 초기화 for (int i = 0; i < 1001; i++) cache..

문제 링크입니다: https://www.acmicpc.net/problem/1058 전형적인 플로이드-와샬 알고리즘 문제였습니다. 우선, 자기 자신은 친구가 될 수 없기 때문에 i==j일 때는 0, 'Y'일 때는 1, 그리고 'N'일 때는 INF를 입력합니다.이후에는 플로이드 알고리즘을 수행한 뒤 모든 사람의 친구의 수를 세는데,1. 서로 친구이거나2. 한 다리 건너서 아는 친구까지 세기 때문에 friendsList[i][j] friendsList[i][k] + friendsList[k][j]) friendsList[i][j] = friendsList[i][k] + friendsList[k][j]; }} int main(void){ cin >> N; for (int i = 0; i < N; i++) { ..

문제 링크입니다: https://www.acmicpc.net/problem/2231 생성자를 1부터 시작해서 순차적으로 더해가면서 조건이 성립하는지 확인하는 Brute Force 문제였습니다.특별한 알고리즘을 요구하지 않았기 때문에 쉬운 문제였습니다. #include using namespace std; int N; int findCreator(void) { int creator = 1; //1부터 시작 while (1) { int copy = creator; int sum = creator; //합은 생성자와 생성자의 각 자리 숫자의 합 while (copy) //각 자리 숫자의 합을 구한다 { sum += copy % 10; copy /= 10; } //조건 성립시 혹은 생성자가 없을 경우 if (c..

문제 링크입니다: https://www.acmicpc.net/problem/1012 쉬운 문제였는데 사소한 부분에서 고생한 문제였습니다.저는 그래프에서 좌표를 (y, x) 기준으로 문제를 푸는데 문제는 (x, y) 기준으로 제시되어서 좌표를 입력 받을 때 int x, y; cin >> x >> y; lettuce[y][x] = 1;이런 식으로 입력받아야했습니다.물론, (x, y) 기준으로 문제를 푸시는 분들은 고려하지 않아도 되는 문제입니다. 이후에는, 간단한 DFS로 문제를 해결하면 됩니다!결국, 컴포넌트가 몇개인지 구하는 문제였습니다. #include #include //memset using namespace std; const int MAX = 50; typedef struct { int y, x..

문제 링크입니다: https://www.acmicpc.net/problem/1507 플로이드-와샬 알고리즘을 사용하여 최소의 도로를 선택하는 문제였습니다.플로이드 알고리즘을 적용하여 i에서 j로 가는데 k를 거쳐가는 경우와 같다면 보다 많은 도시를 커버해야하기 때문에 i->j 도로를 선택하지 않고 i->k, k->j 도로를 선택합니다.반면, i->j로 가는 경로의 길이가 k를 거쳐가는 길이보다 크다면 최소 이동거리가 성립하지 않기 때문에 -1을 출력합니다. #include #include //memset using namespace std; const int MAX = 20; int N; int graph[MAX][MAX]; int road[MAX][MAX]; int result; void floyd(v..

문제 링크입니다: https://algospot.com/judge/problem/read/FORTRESS 언뜻 보기에는 트리 문제로 보이지 않지만, 성벽끼리의 접촉이 없다는 조건에 주목하면 성이 계층적 구조로 구성되어 있음을 알 수 있습니다.이 문제에서 핵심은 트리 내에서 가장 긴 경로를 찾는 것이였습니다. 트리 내에서 가장 긴 경로는 다음과 두 가지 경로 중 최대인 경로입니다.1. 가장 긴 root ~ leaf 경로의 길이2. 가장 긴 leaf ~ leaf 경로의 길이 소스코드에서 //root를 최상위 노드로 하는 경로를 고려하자 if (heights.size() >= 2) longest = max(longest, 2 + heights[heights.size() - 2] + heights[heights..

문제 링크입니다: https://algospot.com/judge/problem/read/TRAVERSAL 소스코드에 앞서서 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)의 Pseudo Code를 간단히 소개하겠습니다. 전위 순회if (currentNode){ Visit(currentNode); Preorder(currentNode->leftChild); Preorder(currentNode->rightChild); }중위 순회if (currentNode){ Inorder(currentNode->leftChild); Visit(currentNode); Inorder(currentNode->rightChild)..