일단 나는 이 문제를 LIS nlogn 구현 문제 밀다가 발견한거기 때문에 알고리즘 접근에 있어서의 문제는 없었다. https://www.acmicpc.net/problem/13711 13711번: LCS 4 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] www.acmicpc.net https://jason9319.tistory.com/113 [최장 증가 수열] LIS(Longest Increasing Subsequence) 이번 글에서는 DP중에서 특별한 케이스인 LIS에 대해 얘기해보..
노안이 왔나 '-' 이랑 '_' 를 구분을 못해서 맞왜틀했다 ㅠㅠㅠㅠ https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 출력 예시를 보고 잘 구현하라고 하는데 출력 예시를 보고 잘 구현하라고밖에 말을 못하는 문제 #include using namespace std; int n; void recur(int k){ for(int i=0; i
귀찮았던 문제. https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 그냥 너무나도 귀찮았던 나머지 입력이 홀수로 들어오면 2를 잘 빼줘서 5의 배수 꼴로 만들어준 다음 잘 계산했고 입력이 짝수로 들어오면 10의자리와 1의자리를 분리해서 계산해줬다. #include using namespace std; int main(){ int n; scanf("%d", &n); if(n==1 || n==3){ printf("-1"); return 0; } int ans = 0; if(n%10 == 1){ ans+=3; n-=6; } if(n%10 == 3){ ans+=4; n-=8..
실버작 2 Hamming Distance 자체는 좀 귀찮은 개념이긴 한데 이 문제에선 굳이 Hamming Distance를 구할 필요가 없다. 그냥 각 문자 자리에서 가장 많이 등장하는 문자를 Hamming Distance의 합이 가장 작은 DNA의 문자자리에 그대로 넣어주기만 하면 된다 #include using namespace std; char arr[1234][56] = {0}; char ans[56] = {0}; int a,c,g,t; int main(){ int n,m; scanf("%d %d", &n, &m); for(int i=0; i
시험끝나고 알고리즘 재활을 시작하고 있는 코더빡입니다... 기말은 말아먹었지만 알고리즘까지 말아먹을순 없죠 ㅋㅋㄹㅃㅃ 실버로 감을 다시 잡아봅시다. 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..