꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/15484 알고리즘 학회에서 Edit Distance 알고리즘을 배운 뒤 15483번 최소편집(http://jaimemin.tistory.com/540) 문제를 풀고 신이 나서 15484번 문제를 시도했었는데 보기 좋게 실패했었습니다.그 당시에는 "Edit Distance 알고리즘에서 transpose만 추가된건데 어려울게 머가 있겠어?"라는 생각으로 시도를 했는데 생각만큼 만만한 문제가 아니였습니다.위키피디아에서 검색해보니 Edit Distance + transpose 알고리즘은 Damerau-Levenshtein distance 알고리즘(https://en.wikipedia.org/wiki/Damerau%E2%80%93Leve..

문제 링크입니다: https://www.acmicpc.net/problem/2228 인덱스, 구간의 수, 선택을 통해 메모이제이션하는 발상은 쉽게 떠올랐지만 구현하는데 애를 먹었던 문제였습니다.항상 기저사례를 먼저 작성한 뒤 조건 만족하는 경우를 고려했었는데 해당 문제는 조건 만족하는 경우를 먼저 고려해야지만 AC를 받을 수 있는 문제였습니다. 알고리즘 자체는 간단합니다.1. select==false 즉, 새로운 구간을 찾을 때는 해당 인덱스를 건너 뛰거나 해당 인덱스부터 새로운 구간이 시작됩니다.2. select==true 일 때는, 기존 구간을 끝내거나 해당 인덱스를 추가하는 경우가 있습니다.3. 구간의 수가 M이거나 구간의 수가 M-1이고 select==true일 때는 조건을 충족하고 그 외의 경우..

문제 링크입니다: https://www.acmicpc.net/problem/1920 자료구조 시간에 많이 다루던 이분 탐색, 혹은 이진 탐색 문제였습니다.네이버 사전에서는 이진 탐색이 올바른 표현인데 백준에서는 이분 탐색으로 표현을 하므로 논란이 생기지 않도록 BinarySearch라고 하겠습니다.BinarySearch는 배열 내 숫자가 정렬되어야 올바르게 탐색을 할 수 있습니다.처음부터 끝까지 모두 확인하며 탐색하는 방법은 시간복잡도가 O(N)이지만 BinarySearch는 시간복잡도가 O(logN)이기 때문에 웬만하면 BinarySearch를 통해 탐색하는 것이 효율적입니다.C++에서는 algorithm 헤더파일에 sort 함수를 제공하기 때문에 쉽게 정렬을 할 수 있습니다. 그리고 주의할 점은, c..

문제 링크입니다: https://www.acmicpc.net/problem/4803 DFS를 통해 정점의 개수와 간선의 개수를 구한 다음 조건 성립하는지 파악하는 문제였습니다.주의할 점은 DFS를 통해 구한 간선의 개수는 실제 간선의 개수의 두배라는 점입니다.왜냐하면, 노드를 삽입할 때 어느 노드가 부모노드인지 모르기 때문에 양방향으로 삽입했기 때문입니다!그리고 벡터 배열을 전역변수로 선언하였다면 while문이 돌 때마다 clear하는 것을 잊지 말아야합니다 ㅠ #include #include #include //memset using namespace std; const int MAX = 500 + 1; int N, M; bool visited[MAX]; bool passed[MAX]; //간선 지나갔..

문제 링크입니다: https://www.acmicpc.net/problem/11725 DFS를 통해 노드의 부모를 찾는 문제였습니다.주어진 노드들이 부모 - 자식 순서가 아니라 랜덤으로 주어지기 때문에 양방향으로 넣어줘야합니다.1은 무조건 루트이기 때문에 1부터 넣고 방문했다고 표시한 뒤 전형적인 DFS를 진행해주면 됩니다. #include #include using namespace std; const int MAX = 100000 + 1; int N; bool visited[MAX]; int parent[MAX]; vector tree[MAX]; void findParent(int nodeNum) { visited[nodeNum] = true; //방문한 노드 표시 //DFS for (int i = ..

문제 링크입니다: https://www.acmicpc.net/problem/13913 http://jaimemin.tistory.com/581, http://jaimemin.tistory.com/582, http://jaimemin.tistory.com/583와 유사한 문제였습니다.숨바꼭질 문제를 풀었다면 숨바꼭질 4는 쉽게 풀 수 있는 문제였습니다.해당 지점을 방문하기 직전에 있던 지점을 parent 배열에 저장해놓은 뒤 역순으로 출력하면 여태까지 방문했던 경로를 쉽게 파악할 수 있습니다.자료구조 시간에 과제로 작성한 지하철 노선도 문제에서의 경로도 위와 같은 방법으로 작성했던 적이 있었기 때문에 나름 쉽게 접근할 수 있었던 것 같습니다! #include #include #include using na..

문제 링크입니다: https://www.acmicpc.net/problem/13549 http://jaimemin.tistory.com/582, http://jaimemin.tistory.com/581과 유사한 문제였습니다.이번에는 순간이동하는데 0초가 걸리므로 그냥 queue가 아닌 priority queue 즉, 우선순위 큐를 통해 BFS 기법으로 풀어야하는 문제였습니다. 주의할 점은 경과시간을 기준으로 우선순위를 결정해야하며 경과시간이 짧을수록 더 높은 우선순위를 갖게 우선순위 큐를 정의해야한다는 점이였습니다.따라서, 위와 같은 조건으로 문제를 풀 경우 priority_queue q; 이렇게 선언해야합니다. #include #include #include #include using namespace..

문제 링크입니다: https://www.acmicpc.net/problem/12851 http://jaimemin.tistory.com/581과 비슷한 문제였지만 가장 빠른 시간내에 도착할 수 있는 방법의 가지수까지 출력해야하는 문제였습니다.숨바꼭질 문제에서는 이미 방문한 지점을 큐에 넣지 않았지만 숨바꼭질 2 문제에서는 방법의 가지수까지 고려해야하므로 큐에서 pop할 때 해당 지점을 방문했다고 표시하는 것이 핵심이였습니다.예를 들어, N=1 K=4를 입력할 경우,i) 1->(1+1)->(2*2)ii) 1->(1*2)->(2*2) 이렇게 총 두가지 방법이 있습니다.하지만, 숨바꼭질1에서처럼 큐에 집어넣을 때 방문지점을 표시하면 두 번째 경우를 고려하지 않게 되므로 오답이 됩니다.따라서, 큐에 push할 ..

문제 링크입니다: https://www.acmicpc.net/problem/1697 pair 형 큐를 통해 first에는 위치를 second에는 경과시간을 저장하여 BFS 기법을 통해 문제를 해결했습니다.한가지 주의할 점은 한번 도달한 지점은 다시 방문하지 않도록 visited 배열을 통해 도달여부를 파악하는 것입니다.방문한 지점을 다시 큐에 넣을 경우 메모리 초과 발생과 함께 어마어마한 실행시간을 요구하기 때문에 문제를 풀 수 없습니다! #include #include using namespace std; const int MAX = 100000 + 1;bool visited[MAX]; int minSecond(int N, int K){ queue q; q.push(make_pair(N, 0)); vi..

문제 링크입니다: https://www.acmicpc.net/problem/1966 전형적인 브루트 포스 문제였습니다.지저분하게 코드를 작성했지만 양해해주시면 감사하겠습니다! #include #include #include //memset using namespace std; const int MAX = 100; int N, M; int priority[MAX]; int order[MAX]; bool checked[MAX]; //몇등인지 체크했는지 여부 queue q; int Tth(void) { int rank = 1; while (!q.empty()) { int temp = q.front(); q.pop(); int idx = 0; bool top = true; while (1) { //범위 초과 i..