https://www.acmicpc.net/problem/1348문제조건R x C 모양의 주차장N개의 차와, M개의 주차 구역차는 주차장의 경계와 평행하게만 움직일 수 있고, 모든 차는 1초에 한 칸씩 움직일 수 있다.‘C’는 차이고, 'P‘는 주차 구역, 'X'는 벽이고, '.'은 빈 공간이다.한 칸에 여러 대의 차가 동시에 들어갈 수 있다. 모든 차가 주차하는데 걸리는 시간의 최솟값을 구하시오.접근방법 단순하게 BFS를 이용해서 탐색하면 되는 문젠줄 알았는데, 전혀 그렇게 풀리지 않는다. 일반적인 구현문제가 아니라 특수한 알고리즘이 필요한 문제다,,,  Bipartite matching 이분매칭이라는 알고리즘이 필요하다. 주차구역과 차를 연결해주면서 짝을짓고, 짝을 짓는 경우의 수에 따라 최솟값을 비..

https://www.acmicpc.net/problem/6086문제조건두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다.병렬로 연결돼 있는 배수관들은 각 용량의 합만큼의 물을 보낼 수 있다.어떤 것에도 연결돼 있지 않은 파이프는 물을 흐르게 하지 못하므로 제거된다. A에서 Z까지의 최대 유량을 구하시오. 접근방법 처음보는 종류의 문제였다. 그래프를 기반으로 하는문제인것은 알겠는데, 이것을 말로 구현하자고 하니 잘 안되었다. 검색을,,,, 해서 알아봤더니, 이런 문제에 쓰이는 알고리즘이 따로 있었다. 우선 각 노드간의 간선의 가중치를 capacity(수용량)으로 두고, m(흐른물의양)/n(가중치) 로 나타낸다.이때, 출발점부터 도착점까지 막힘없이 1이상의 유량이 흐를수 있..

https://www.acmicpc.net/problem/1738문제조건출발지부터 목적지까지 가야한다.단, 가는 경로에 깡패, 금품 두가지가 존재한다.목적지에 도착했을때, 금품의 양이 최대가 되는 경로를 구해라접근방법 다익스트라로 푸는 최단경로 문제인가? 라고 생각이 들었는데, 깡패가 금품을 갈취하면 음의 정수로 바뀌기 때문에, 다익스트라 알고리즘에서는 최단경로라고 판단된 노드는 더이상 갱신하지 않지만, 금품을 계속 반복해서 갈취당하면 음의 무한대로 짧아질수 있기 때문에 위 알고리즘은 아니다. 생각해보니 예전에 배웠던 음의 가중치가 있을때 최단거리를 구할수 있는 Bellman-Ford 알고리즘이 생각났다.Bellman-Ford 알고리즘 다익스트라 알고리즘과 더불어 최단경로를 구할 때 사용되는 대표적인 알..

https://www.acmicpc.net/problem/1162문제조건 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장포장하게 되면 도로를 지나는데 걸리는 시간이 0서울은 1번 도시, 포천은 N번 도시 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간은?접근방법 가중치가 있는 그래프에서 특정지점에서 시작해서 다른지점까지의 최단거리를 구하는 알고리즘인 다익스트라가 떠올랐다. 사실 이 문제는 푸는것 자체는 크게 어렵지 않았다. 다익스트라 알고리즘 자체가 dp를 기반으로 이때까지 계산된 거리와 새로운 거리를 비교해서 계속해서 기록하는 구조이므로, 엄청나게 큰값이 들어 갈수 있기때문엥 21억이 넘는 수 까지 처리해..

https://www.acmicpc.net/problem/14719문제조건2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.고이는 빗물의 총량을 출력접근방법 정해진 알고리즘을 이용해서 푸는게 아니라, 내가 좋아하는 조건에 맞게만 풀면 되는 구현문제이다.풀이법이 여러개가 떠올랐지만, 나는 블록들중 가장 높은 높이에서 부터 시작해서 아래로 스캔하는 방식을 선택했고, 한번 빗물을 채웠으면 더 이상 채울필요가 없으므로, visited배열을 통해서 이미 빗물이 고였음을 체크해줬다.가장 중요한 빗물이 채워질 조건은 양 옆을 감싸는 블록이 적어도 2개이상은 있어야한다는것이다. 소스코드#in..

https://www.acmicpc.net/problem/20437문제조건알파벳 소문자로 이루어진 문자열 W가 주어진다.양의 정수 K가 주어진다.어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.접근방법 그냥 투포인터를 써서 각 문자에 대한 갯수를 셀 수있도록 cnt배열을두고, [문자 - 'a'] 를 인덱스로 K개 이하일때, end포인터의 위치를 이동시켜주고, K개가 되었을때, start포인터의 위치를 이동시켜주는 방식으로 접근했지만 실패했다. 이때까지의 투포인터를 요구하는 문제는 이런방식이면 전부 풀렸는데 이 문제에는 왜 적용이 안될까?어떤 문자 하나만..

https://www.acmicpc.net/problem/17615문제조건파랑/빨강 볼이 일직선상에 놓여있다.같은색 볼끼리 인접하게 놓으려고한다.바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다옮길 수 있는 볼의 색깔은 한 가지이다.접근방법 이중 for문으로 단순하게 풀수 있겠다라고 생각했지만, 입력값이 무려 50만,,,, 무조건 O(n log n)시간안에는 끝내야한다.어떻게 깔끔한 방법이 없을까 생각을 해보다가 아무리 생각해도 방법이 떠오르지않아서, 경우의수 4가지를 하나씩 직접 구현하고, 비교해줬다.두개의 색깔만 존재하므로, 중간에 볼이 끼어서 존재할수 없고, 무조건 한쪽으로 몰려서 절반으로 나뉠수밖에없다.선형탐색을 진행하며 다른 색의 공이 있으면, 뛰어넘어서 위치를 뛰어넘을..

https://www.acmicpc.net/problem/1522 문제조건와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 최소 회수문자열은 원형이다.접근방법 사실 투포인터 라기보다는 슬라이딩윈도우 방식의 풀이이다.원형으로 이루어진 문자열이므로, 원형을 직선으로 펼친 배열로 보았을때, 모든 경우의수를 비교해서 최솟값을 찾는 방식으로 접근했다. 물론 주어진 문자열의 길이가 1000이므로, O(n^2)안에 탐색할수 있으므로 사용할수 있는 방법이다. 소스코드#include #define MAX 1001using namespace std;string s;int main() { cin >> s; int n = s.length(); int res = n; int a = 0;..

https://www.acmicpc.net/problem/3758문제조건총 k개의 문제풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장한 문제에 대해 여러번 제출한다면 가장 높은 점수가 그 문제의 최종점수 (좋은데,,?)최종 점수가 같은 경우풀이를 제출한 횟수가 적은 팀의 순위가 높다.제출 횟수도 같은 경우   마지막 제출 시간이 더 빠른 팀의 순위가 높다. 우리 팀의 순위는?접근방법 딱히 접근방법이라할게 없었다. 문제의 조건이 까다로운 만큼 문제에서 요구하는 그대로 구현만 잘 해주면 되는 문제였다. 그리고 나는 따로 구조체를 만들고 그에 맞게 정렬을 해주었다.  소스코드#include #include #include #define MAX 101using names..

https://www.acmicpc.net/problem/2075문제조건N×N의 표에서 N번째 큰 수를 구해라.모든 수는 자신의 칸(행)보다 위에 있는 수보다 크다.접근방법 접근방법이라 할것도 없었고, 입력받고 냅다 내림차순정렬해서 N번째 순서의 숫자를 찾았다. 메모리초과는 잘 나지 않아서 당황했지만 어디서 생긴걸까 생각해보면 1500 x 1500 x 4(Byte) = 대략 9MB여서 메모리에 대해서는 아예 초과가 안날줄 알았지만, 내부적으로 사용되는 변수, 내가 사용하는 또 다른 변수들을 고려한다면, 아리까리한 메모리라는 것이다. 일단 해결하기 위해선, 입력으로 받는 표에 대해 전부 저장하면 안된다는것이다. 풀이 배열, 벡터, 큐 등 어떤 자료구조 하나를 선택하고, 그것의 크기가 N보다 커지면 계속 정..