꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2573 쉬운 난이도의 BFS(Breadth First Search) 혹은 DFS(Depth First Search) 알고리즘 문제였습니다.하지만, 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 조건을 확인하지 못한 저는 답이 0인 경우에 대해 처리하지 않아 왜맞틀을 반복하면서 8번 시간초과가 발생했습니다...소스코드에는 BFS, DFS 전부 선언이 되어있는데 저는 처음에 BFS 기법을 통해 풀었기 때문에 melt 함수도 BFS 기법과 유사하게 동서남북에 0이 몇개인지 탐색합니다.시간초과가 계속 발생해서 저는 실행시간을 줄이기 위해 stdio와 sync를 끊었고 첫 번째와 마지막의 열과 ..

문제 링크입니다: https://algospot.com/judge/problem/read/RUNNINGMEDIAN 수열의 크기가 정해져있지 않고 초기값과 다음 값의 공식만 주어졌기 때문에 ITES 문제(http://jaimemin.tistory.com/569)처럼 난수 생성기를 통해 숫자를 생성해야하는 문제였습니다.이후에는 숫자들을 정렬한 뒤 앞의 절반을 최대 힙에, 뒤의 절반을 최소 힙에 넣으면 최대 힙의 root에 중간값이 위치하게 됩니다. 따라서 아래와 같이 불변식을 세웁니다.1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다.(수열의 길이가 홀수일 경우 하나 더 큽니다.)2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다. runningMedian 함수가 위 두 조건을 ..

문제 링크입니다: https://www.acmicpc.net/problem/15881 겉보기에는 쉬운 문제 같지만 사실은 주어진 문자열에서 "pPAp" 형태를 띄는 부분 문자열을 찾는 KMP 알고리즘 문제였습니다.함정이 있기 때문에 문제의 주의사항을 주목해야합니다!단, 펜, 파인애플, 사과, 펜 순서로 연결된 네 개의 물건만을 펜-파인애플-애플-펜으로 인정하며, 하나의 펜이 두 개의 펜-파인애플-애플-펜에 포함될 수 없다. 또한 펜, 사과, 파인애플, 펜 순서로 연결된 네 개의 물건은 펜-파인애플-애플-펜이 아니다.즉, 기존에 풀던 KMP 알고리즘 문제와 달리 부분 문자열("pPAp")를 찾으면 마지막 p를 재활용하지 못하기 때문에 matched=pi[matched-1]로 초기화하지 않고 matched=..

문제 링크입니다: https://www.acmicpc.net/problem/2206 BFS(Breadth First Search) 알고리즘을 사용하여 푸는 문제였지만 벽을 한번 뚫을 수 있다는 조건이 있었기 때문에 살짝 까다로웠습니다.벽을 뚫었는지 여부를 확인하기 위해 cache 배열을 삼중배열로 선언하였습니다.(마지막 2는 벽을 뚫는 기술을 사용했는지 여부)따라서, 기존 문제들과는 다르게 갈 수 없는 벽이더라도 벽을 뚫는 기술이 있다면 큐에 넣으면서 최단거리를 확인하면 되는 문제였습니다.주의할 점은, 이 문제에서는 시작점과 끝점을 포함한 경로라고 했으므로 cache[y][x][block] - 1이 아닌 cache[y][x][block]을 반환해줘야 AC 처리를 받을 수 있습니다! #include #in..

문제 링크입니다: https://www.acmicpc.net/problem/3055 기존의 BFS(Breadth First Search) 알고리즘을 적용하는 문제들과 달리 이 문제는 두더지가 이동하면서 물도 차오르기 때문에 큐를 두개 사용해야하는 문제였습니다.두더지가 물이 차오를 예정인 위치까지도 움직일 수 없기 때문에 먼저 물이 차오르는 과정을 진행한 다음에 두더지를 움직이는 방식으로 진행했습니다.river와 mole의 크기만큼 반복문을 돌리는 것이 핵심이였습니다! #include #include #include using namespace std; const int MAX = 50; typedef struct { int y, x; }Dir; Dir moveDir[4] = { {1, 0}, {-1, 0..

문제 링크입니다: https://www.acmicpc.net/problem/1707 문제에서 이분 그래프(Bipartite Graph)를 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프라고 정의합니다.이분 그래프의 예시는 http://mathworld.wolfram.com/BipartiteGraph.html에서 확인할 수 있습니다.이는 즉, DFS(Depth First Search) 혹은 BFS(Breadth First Search) 알고리즘을 적용하여 서로 이어지는 노드끼리 같은 색깔이면 안 된다는 뜻입니다.(링크에서는 빨간색과 검은색으로 표시했습니다.)정점의 집합을 둘로 분할하기 때문에 색깔은 2가지이면 되고 아직 방문하지 않은 노드를 0..

문제 링크입니다: https://www.acmicpc.net/problem/10026 BFS(Breadth First Search) 알고리즘을 사용하는 간단한 문제였습니다.적록색약이 아닌 경우에는 기존의 BFS 알고리즘을 사용하고 적록색약이라면 빨간색과 초록색을 같은 색으로 처리하여 BFS 알고리즘을 적용하면 되는 문제였습니다.주의할 점은, 색약이 아닌 경우 BFS 알고리즘을 적용한 뒤 memset을 통해 visited 배열을 0으로 초기화해줘야한다는 점입니다! #include #include #include #include //memset using namespace std; const int MAX = 100; typedef struct { int y, x; }Dir; Dir moveDir[4] = ..

문제 링크입니다: https://www.acmicpc.net/problem/1963 오랜만에 에라토스테네스의 체와 함께 BFS(Breadth First Search) 알고리즘을 사용하여 푸는 문제였습니다.에라토스테네스의 체를 통해 우선 4자리 소수를 미리 구해놓은 뒤에 한자리씩 숫자를 바꿔가며 BFS를 적용하면 풀리는 문제였습니다.주의할 점은, 4자리 소수이기 떄문에 천의 자리 수가 0이면 안됩니다!! #include #include #include #include //memset using namespace std; const int MAX = 10000; int start, destination; int minFactor[MAX]; //minFactor[i] -> i의 가장 작은 소인수(i가 소수인 ..

문제 링크입니다: https://www.acmicpc.net/problem/5014 BFS(Breadth First Search) 알고리즘을 적용하여 푸는 문제였습니다.기존의 BFS 문제와는 달리 Dir 구조체와 Dir 배열을 미리 정의하지 않고 while문 내에서 다음 층(위로 갔을 경우, 아래로 갔을 경우) 두 가지만 고려해주면 되는 문제였습니다.결과는 백준 2589번 보물섬(http://jaimemin.tistory.com/644) 문제와 같이 cache[도달한 층] - 1을 출력해야합니다. #include #include using namespace std; const int MAX = 1000000 + 1; int F, S, G, U, D; int cache[MAX]; int BFS(void) ..

문제 링크입니다: https://www.acmicpc.net/problem/2589 기존의 BFS(Breadth First Search) 문제와 달리 시작점과 도착점이 정해져있지 않아서 Brute Force 방식으로 찾아봐야하는 문제였습니다.다행히 가로와 세로의 크기가 최대 50이기 때문에 전체 지도 크기가 50*50=2500이기 때문에 시간초과를 걱정하지 않아도 됩니다!그리고 cache 배열에는 시작점과 도착점까지의 칸 수이기 때문에 경로는 cache[시작점][도착점] - 1 입니다. #include #include #include #include #include //memset using namespace std; const int MAX = 50; typedef struct { int y, x; }..