시험끝나고 알고리즘 재활을 시작하고 있는 코더빡입니다... 기말은 말아먹었지만 알고리즘까지 말아먹을순 없죠 ㅋㅋㄹㅃㅃ 실버로 감을 다시 잡아봅시다. 1439번 뒤집기는 이진수라는거에서 뇌절이 오면 안되는 문제였습니다. 이 문제의 핵심은 한번 뒤집을때 얼마나 효율적으로 뒤집을 수 있나 였습니다. 0에서 1로, 1에서 0으로 바뀌는 횟수를 세 줍니다 왜냐하면 뒤집는 구간을 제 맘대로 정할수 있기 때문에 1이 몇개있거나 0이 몇개있거나는 전혀 신경쓸 필요가 없기 때문입니다. 이제 다른 숫자가 등장한 횟수를 센 상태이고, xxxYYxx에서 변화횟수는 2, 가장 효율적이게 xxxxxxx로 바꾼 뒤의 변화횟수는 0임에서 착안하면 한번의 Y*k 를 x*k 로 뒤집는 연산은 변화횟수를 2만큼 줄여낼 수 있게 됩니다. ..

오늘은 세그 미는날~~ 평범한 최솟값 세그가 아니여서 좀 고생했다. www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 이 문제의 핵심은 세그트리가 반환해주는 값이 구간 내의 히스토그램 값의 최솟값 이 아니라, 히스토그램이 최솟값을 가지는 곳의 인덱스값이다. 이를 위해 세그트리를 살짝 수정해 준 뒤에, 구간에서의 최대값을 찾을때에는 분할정복을 이용해주었다. 분할을 할때는 반드시 딱 절반에서 나누는 것이 아..

프림 / 크루스칼 알고리즘을 사용하면 쉽게 해결할 수 있다. 나는 크루스칼 알고리즘을 사용했다. www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 크루스칼 알고리즘의 기본적인 구현을 묻는 문제 더보기 #include using namespace std; typedef long long int ll; struct line{ int s; int e; int w; }; vector g; int parent[12345] ..

www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 처음 보고 든 생각은 "R과 C의 범위가 작으니까 DFS등으로도 해결할 수 있을 거 같다" 였다. 구현 방법은 뭐 여러가지가 있겠지만, 나는 비트마스킹을 연습할 겸 비트마스킹으로 해결해 보기로 했다. 우선 들어오는 문자들에서 'A'만큼을 빼서 0부터 시작하는 숫자로 만들어준다음 각각 0 번째 비트, 1번째 비트, .... 등으로 각각의 비트에 방문여부를 기록해준다. 더보기 #include using na..

다익스트라 연습 (2) www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 각각의 좌표를 노드로, 각각의 좌표에 있는 도둑루피의 수를 가중치로 보자면 가중치합을 최소로 해서 (0,0) 에서 (n-1,n-1) 까지 이동하는 평범한 다익스트라 문제가 된다. 더보기 #include #define INF 123456789 #define st first #define nd second using namespace std; int arr[150][150]..

다익스트라 연습중 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 초(시간) 에 해당하는걸 간선의 가중치로, 각각의 점 위치를 노드로 보면 그래프에서의 N번 노드에서 K번 노드까지의 가중치의 최소값을 구해주면 되므로 다익스트라로 해결할 수 있다. 단순한 다익스트라에, 간선조건조차 그리 어려운 편이 아니므로 자세한 설명은 생략해도 괜찮을 것 같다. 더보기 #include #define INF 123456789 using nam..