다익스트라 알고리즘이란? 다익스트라 알고리즘은 DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 인공위성, GPS 등 현실 세계에서 굉장히 많이 사용되며, 다음과 같은 특징들이 있다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 음의 간선을 포함할 수 없다 (이 경우 벨만 포드 알고리즘 사용) $O(NlogN)$의 시간 복잡도를 가진다. 동작 단계 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 현재 위치한 노드의 인접 노드 중 아직 방문하지 않았고, 거리가 가장 짧은 노드를 선택한다. 4. 선택된 노드를 방문처리한다. 5. 해당 노드를 거쳐 다른 노드로 넘어가는 간선의 가중치를 통해 최단 거리 테이블을 업데이트한다. 6. 3~5 과정을 반복한다. 최..

https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 위 문제는 정규식에 관련된 문제인데, 분기를 나눠서 구현으로 풀다가 왠지 정규식과 관련된 헤더가 있을 것 같아서 찾아봤다. 역시나 regex 헤더를 사용하면 되는데, 사용법은 아래 코드를 참고하면 된다. 먼저 regex 변수를 선언하고, 사용하고 싶은 정규식을 입력해준다. 이후 regex_match 메서드를 통해 문자열이 해당 정규식을 만족하면 true, 아니면 false를 반환한다. ..

오늘은 오랜만에 그래프 알고리즘을 공부하려고 한다. 블로그에 글은 안썼지만, 그동안 프림, 크루스칼등 MST(최소 신장 트리) 그리고 다익스트라(한 정점에서 다른 정점까지의 최단 거리를 찾는 알고리즘) 등을 공부해왔었는데, 오늘은 플로이드-워셜 알고리즘을 공부해보았다. 오늘 풀어볼 BOJ 14938 문제이다. 알고리즘 분류를 보면 다익스트라와 플로이드-워셜 모두 사용 가능하다고 되어있지만, 노드의 개수가 100으로 시간복잡도의 부담이 적고, 모든 노드를 시작점으로 잡고 최단거리를 구해야 하는 점, 음수 간선이 없는 점을 근거로 플로이드-워셜을 적용해 푸는 것이 쉽고 빠르다. 💡플로이드 워셜 알고리즘이란? 모든 정점에서 다른 모든 노드로 향하는 최단 경로를 구하는 알고리즘 모든 노드간의 최단 거리를 구하기..

💡최대 유량이란? 그래프에서 두 정점 사이에 얼마나 많은 유량(flow)을 보낼 수 있는지 계산하는 알고리즘을 네트워크 유량(Network Flow) 혹은 최대 유량(Maximum Flow) 알고리즘이라고 한다. 아래 용어들은 최대 유량 알고리즘을 이해하는데 도움이 되므로, 미리 짚고 넘어가자. 용량(Capacity) Capacity[u][v]는 정점 u에서 v로 가는 간선의 용량이다. 유량(Flow) flow[u][v]는 정점 u에서 v로의 간선(파이프)에 실제로 흐르는 유량을 의미한다. 잔여 용량(Residual Capacity) 간선의 용량과 유량의 차이를 의미한다. ResidualCapacity[u][v] = Capacity[u][v] - flow[u][v] 즉, 해당 간선에 추가적으로 더 흘려 ..

소수를 판별하는 알고리즘 중에는 굉장히 유명한 에라토스테네스의 체라는 알고리즘이 존재한다. 소수 판별 문제는 대부분 이 알고리즘으로 풀기 때문에 잘 익혀두면 큰 도움이 된다. 오늘 풀어볼 문제인 boj 1929 번 문제다. 💡에라토스테네스의 체란? 배열을 원하는 범위만큼 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. 이때, 자기 자신은 지우지 않고, 이미 지워진 수인 경우 건너뛴다. 지워지지 않은 테이블이 소수로 판별된 테이블이다. 위 예시는 2의 배수를 모두 지우고, 3의 배수를 지우는 과정이다. 이런 식으로 $N/2$까지 진행하고 남은 테이블을 확인한다. ❓에라토스테네스의 체의 시간복잡도 naive한 방법으로는, 일반적으로 어떤 정수의 소수를 판별할때는 2부터 판..

2023.05.17 - [PS] - [세그먼트 트리] - BOJ_14427 : 수열과 쿼리 [세그먼트 트리] - BOJ_14427 : 수열과 쿼리 ※본 포스팅은 이전 블로그에서 다시 이전해온 글로서 기존 작성일은 23.04.25 입니다. 요즘들어 PS를 하면서 느끼는게, 내가 이전에 공부하고 완전히 이해했던 자료구조 / 알고리즘들이 몇개월 지 kangmanjoo.tistory.com 지난 포스팅에 이어, 다시 한 번 세그먼트 트리로 돌아왔다. 세그먼트 트리는 특정 구간의 합, 곱, 최솟값, 최댓값을 찾을 때 일반적인 배열에서 찾을 때보다 훨씬 빠른 O(logN)의 시간복잡도를 가진다고 하였다. 그렇다면 세그 트리는 무적이고 나는 신인가? 물론 아니다. 세그트리에도 치명적인 단점이 존재하는데, 바로 값의 ..

※본 포스팅은 이전 블로그에서 다시 이전해온 글로서 기존 작성일은 23.04.25 입니다. 요즘들어 PS를 하면서 느끼는게, 내가 이전에 공부하고 완전히 이해했던 자료구조 / 알고리즘들이 몇개월 지나면 기억이 휘발되어 다시 포스팅들을 찾아보고 있는 내 모습이 너무 바보같았다. 그래서 이왕이면 내가 쓴 글을 보고 다시 떠올리자! 하는게 재습득하기도 제일 빠르고 나에게도 도움이 더 될 것같아, 이곳에 정리하기로 결정했다! 오늘 학습한 자료구조는 바로 세그먼트 트리 도대체 세그먼트 트리는 어디에서 활용이 되는 자료구조인가? 가장 대표적으로 활용이 되는 곳은, 바로 구간합을 구할때이다. INDEX 0 1 2 3 4 5 6 7 VALUE 2 1 7 8 5 4 3 1 위와 같은 테이블이 있다고 하자. 이 배열에서 ..

첫 플래티넘 3 솔브다 !! 세그먼트 트리를 활용하는 자료구조 중 재밌는게 없나 찾던 중, 머지 소트 트리라는 이름만 들어도 흥미로운 태그를 찾았다. 심지어 수열과 쿼리 '1' 이라니 안풀 수가 없잖아 ! ❓머지 소트 트리(Merge Sort Tree)란? 일반적인 세그먼트 트리구조란, 해당 구간의 특징 (구간합이든, 최솟값이든.. 등등)을 각 범위를 지칭하는 노드에 저장을 한다. 머지 소트 트리도 마찬가지로, 특정 범위의 value들의 정렬 상태인 배열을 노드에 저장을 하는 구조이다. 사실 세그먼트 트리에 익숙하다면 크게 어렵지 않게 풀 수있다. 이번 문제에서는 개념을 묻는 느낌이라 갱신을 안해서 갱신부분은 고려를 안해보았는데, 이를 다루는 문제들도 풀어보면 좋을 듯싶다. 이 문제에서 한 번 실수했던 ..