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보다 커지면 계속 정..

https://www.acmicpc.net/problem/2162문제조건N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 그룹의 수, 가장 크기가 큰 그룹에 속한 선분의 개수를 구하시오.접근방법 선분끼리 만나는 경우를 하나하나 모두 체크를 해줘야하는지 생각해봤다.그리고 선분끼리 교차하는 건 코드로 어떻게 나타낼지 감이 안와서 검색을통해 알아냈다.https://bowbowbow.tistory.com/17 [기하] 외적을 이용해서 선분과 선분의 교차점 구하기[기하]외적을 이용해서 선분과 선분의 교차점 구하기 목차 [기하]외적을 이용해서 ..

https://www.acmicpc.net/problem/2463문제조건가중치그래프가 존재한다.서로다른 정점 u, v에 대해서 경로가 있다면 경로가 없을때까지 최소 가중치 간선을 제거한다. u 접근방법 딱봐도 MST(최소비용신장트리)와 정말 유사하게 동작하는 문제였다. 그리디한 접근법인 Prim, Kruskal 알고리즘을 떠올렸는데, 이 알고리즘의 핵심은 서로소 분리 집합으로 초기에 모든 노드(정점)을 각각 독립적인 집합으로 초기화 시킨후, 집합이 하나가 될때까지 최소비용인 간선들을 더해가는 것이다. Kruskal 알고리즘과 이 문제의 차이점은, 최대 가중치를 가진 간선부터 그래프에 추가한다는 점이다. 간선의 가중치를 내림차순으로 정렬한다.임의의 간선부터 시작해서 정점이 속해있는 집합이 서로다른 경우에만..

2024.05.13 - [Spring/대용량 트래픽] - Spring Session Spring Session2024.05.13 - [Spring/대용량 트래픽] - Spring cache abstraction, Vegeta 오픈소스 사용해보기 Spring cache abstraction, Vegeta 오픈소스 사용해보기2024.05.08 - [Spring/대용량 트래픽] - Spring Boot Cache Spring Boot Cache2024.05.lsdiary.tistory.com 이전글에서는 세션으로써의 Redis를 알아봤다.이번에는 Redis의 Pub/Sub 패턴에 대해 알아보겠다. 각 서버간의 느슨한 결합(loose coupling)을 위해 사용한다.여기서 Redis는 메세지 브로커 역할을 해..

2024.05.13 - [Spring/대용량 트래픽] - Spring cache abstraction, Vegeta 오픈소스 사용해보기 Spring cache abstraction, Vegeta 오픈소스 사용해보기2024.05.08 - [Spring/대용량 트래픽] - Spring Boot Cache Spring Boot Cache2024.05.08 - [Spring/대용량 트래픽] - Redis Cache로 실습하기 Redis Cache로 실습하기2024.05.07 - [Spring/대용량 트래픽] - Redis Cache 이론 Redis Cachelsdiary.tistory.com 이전글에서는 Redis를 Cache로써 활용해, 트래픽이 클 경우 대폭 성능향상과, Vegeta 오픈소스를 이용해서 트래..

https://www.acmicpc.net/problem/1446문제조건D킬로미터의 고속도로 길이 주어진다.지름길의 시작위치, 도착위치, 지름길의 길이가 주어진다.고속도로 끝지점까지 가는 최소거리를 구해라.접근방법 Brute Force로 봐야하나,,? 평소에 잘 접하지 않은 유형의 문제여서 당황스러웠다.최단거리를 구한다고 하면 다익스트라가 떠올랐지만 어떻게 적용시키지,,,? 계속 생각이 안나서 검색의 힘을 조금 빌렸다.  Dijkstra 최단경로를 구하는 대표적인 알고리즘이다.이중 for문을 이용한것과, priority_queue를 이용해서 구현을 선택할 수 있는데, 우선순위 큐가 시간복잡도가 훨씬 작으므로 우선순위 큐를 사용한다.알고리즘의 동작과정은 이와같다.방문하지 않은 노드 중에서 최단거리가 가장 ..