개발 블로그

다익스트라 알고리즘이란 무엇인가? 음의 가중치가 없는 그래프의 한 정점(V)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘입니다. 기존에는 O(V^2)의 시간복잡도를 가졌으나, 시간이 지나 우선순위 큐를 이용하여 더욱 개선된 알고리즘이 생겨났으며 O((V+E)logV)(V : 정점의 개수, E : 간선의 개수)의 시간 복잡도를 가질 수 있게 되었습니다. O(VlogV)(각 노드마다 미방문 노드 중 출발점으로 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 걸리는 시간) + O(ElogV) (각 노드마다 이웃한 노드의 최단거리를 갱신할 때 걸리는 시간)으로 보시면 될 것 같습니다. 출처 : https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9..

신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미 트리의 조건 : 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않아야 함 사이클(cycle)이란 ? 그래프에서 시작 노드에서 출발해서 다른 노드를 거쳐 다시 시작 노드로 돌아갈 수 있는 경로가 존재한다면, 이는 하나의 사이클이 됩니다. 최소 신장 트리 최소한의 비용으로 신장 트리를 찾기 위한 방법 1, 2, 3번 지역에 도로를 2개 놓아 전체 지역을 연결시키도록 하는 경우에서는 1->2, 2->3을 연결하는 것이 가장 저렴하게 연결할 수 있는 방법입니다. 즉, 최소 신장 트리는 말 그대로 최소한의 비용(가중치의 합이 최소==간선의 비용)으로 신장 트리를 찾아내는 알고리즘이고, 그리디 알고리즘으로 분류됩니다. ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 두 개의 포인터를 이용해서 원하는 값을 추출하는 투 포인터 알고리즘 문제 입니다. 연속된 수들의 부분합 중에서 합이 S이상이 되는 것들 중에서 수열의 최소 길이를 구해야 합니다. 테스트 케이스를 예시로 설명 드리겠습니다. 10 15 5 1 3 5 10 7 4 9 2 8 start, end 변수를 두어 이를 조작하여 원하는 수열의 최소 길이를 구해야 합니다. sum(부분합) < S(원..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 일반적인 BFS탐색 문제와 크게 틀에서 벗어나진 않지만, 벽(1)을 한 번 이동할 수 있는 조건에서 큰 차이를 보입니다. 그리고 이 조건으로 인해 조금 더 어려워졌습니다. 저는 입력을 2차원 배열로 받고, 구하고자 하는 최단경로를 3차원으로 만들어줘서 풀었습니다. 왜냐하면 벽을 부순 경우가 최단 경로가 될 수 있고, 부수지 않은 경우가 최단 경로가 될 수 있기 ..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net BFS +DFS알고리즘을 활용하면 되지만 조건이 굉장히 까다로운 문제입니다. 벽을 부순 후 벽을 기준으로 이동할 수 있는 영역이 몇 개 인지 탐색하는 문제입니다. 이것을 일일이 탐색한다면 시간 복잡도가 O((MN)^2)으로 매우 오래 걸리게 됩니다. 그래서 이동할 수 있는 영역에 대해서 그룹을 짓고 그룹의 크기가 담겨있는 vector를 만들어 줍니다. 그리고 해당 벽을 기점으..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 이 문제를 해결하기 위해 적용한 것은 에라토스테네스의 체, 투 포인터 알고리즘입니다. 에라토스테네스 체는 2의 배수(2는 제외, 소수이므로)부터 특정 수의 배수까지 걸러주는 알고리즘입니다. 출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 수학에서 에라토스테네스의 체는 ..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 이 문제는 c++의 set헤더를 이용하면 쉽게 풀 수 있는 문제였습니다. multiset 헤더는 set헤더와는 다르게 중복된 값을 저장할 수 있기에, 이중 우선순위 큐를 풀기 위해서는 multiset을 이용해야 합니다. 왜냐하면 문제에서 D -1 연산을 했을때 최소값이 중복되더라도 한 번만 제거하기 때문입니다. erase() 함수를 통해 원소를 삭제할 수 있다. (erase함수 안에 인자로 값..

기능 추가한 패키지는 다음과 같습니다. (기존 틀에서 벗어나진 않지만, Spring Security와 도메인 추가, 이미지 처리, 페이징 처리 등 다양한 기능들을 추가하였습니다) 우선 시큐리티 부분부터 차근차근 설명드리겠습니다. SecurityConfig.class @EnableWebSecurity @Configuration @RequiredArgsConstructor public class SecurityConfig { private final TokenProvider tokenProvider; private final CorsFilter corsFilter; private final JwtAuthenticationEntryPoint jwtAuthenticationEntryPoint; private f..

오늘도 N과 M 시리즈를 복습 차원에서 다시 풀어보았습니다. 유형마다 조금씩 차이도 있고, 함수 구현하는데 있어 도움이 많이 될 것 같아서 다시 풀어보았습니다. 6 ~ 12번 까지 문제 설명 드리겠습니다. 6번 : N개의 자연수 중에서 M개를 고른 수열, 고른 수열은 오름차순이어야 한다. 7번 : N개의 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다.(사전 순으로 증가하는 순서로 출력) 8번 : N개의 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 9번 : N개의 자연수 중에서 M개를 고른 수열(중복 수열 제거, set 사용..

오늘은 N과 M 시리즈를 다시 풀어보았습니다. 백트래킹(완전탐색)은 BFS, DFS에서도 굉장히 많이 응용되어서 나오기 때문에 잘 알아둬야 할 것 같습니다. 문제마다 조금씩 다른 유형이지만, 조건을 잘 보고 로직을 조금씩 다듬으면 수월하게 풀 수 있을 것 같다고 생각합니다. 1번부터 5번까지 문제 설명 드리겠습니다. (공통) 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1 : 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 2: 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열, 고른 수열은 오름차순이어야 한다. 3: 1부터 N까지 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다. 4: 1부터 N까지 자연수..