Whatever floats your boat

알고리즘 풀 때, 문자열에 대한 문제가 나오는 경우가 많다. 이때 마다 인터넷을 검색해서 풀 수 없으니 정리를 해보고자 한다. C++ string 변수에서 특정 문자열을 찾을 때, std::string의 find() 함수를 사용한다. 예시1#include #include using namespace std;int main(){ string s = "Enter ui1234 Muzi"; size_t index = s.find("ui1234");//size_t는 unsigned long type printf("%zu\n", index); // zu는 unsigned long에 대한 type specifier //출력 : 6 }위 코드에서 index의 값은 찾고자 하는 문자열의..

내 생각 다이나믹 프로그래밍에 점화식은 바로 세울수 있었다. 너무 기쁜나머지 메모리에 대한 에러를 해결하는데 오래걸렸다... 하나가 되면 하나가 안되는 매직. 아이디어는 떠올렸으니 메모리 제한에 대해 계산하는 법을 정리하겠다. 메모리 계산하기 대략적인 메모리 계산법은 다음과 같다. 1MB = 1000KB 1KB = 1000byte 따라서 1MB = 1000000byte이다. 과연 1MB에서 int형 배열은 몇개까지 선언할 수 있을까?? int는 4바이트이기 때문에 1000000/4 = 250000개 선언할 수 있다. 코드 #include #include #include #include #include using namespace std; int dp_max[3],dp_min[3]; int max(int ..

풀이 일단 시간제한이 0.1초이기 때문에 규칙을 찾는 문제라는것은 이해하였다. 규칙을 찾기 위해서는 직접 써가면서 푸는것이 나에겐 가장 효과적이다. n = 1일 때, (즉 고리를 한 개 끊을 경우) X 1 Y 라고 생각할 수 있다. (X와 Y는 고리의 개수) 이제 여기서 생각을 해보자 1은 만들 수 있고(잘라진 chain으로 1g 만들기) 2부터 만들 수 없다. 따라서 X = 2이다. X가 2이면 1, 2, 3(1 + 2)g 까지 만들 수 있다. 이제 만들지 못하는 것은 4g 부터이다. 따라서 Y= 4g. n = 1일때 7g까지 만들 수 있다. 1, 2, 3(2 + 1), 4, 5(4 + 1), 6(4 + 2), 7(2 + 1 +4) n = 2일 때, (즉 고리를 두 개 끊을 경우) A 1 B 1 C 라..

풀이 처음문제를 읽고 허프만 코드를 만드는것 처럼 priority queue를 이용해 구현하였다. 하지만 제대로 된 답이 나오지 않았고 찾아보니 소설의 chapter를 인접한 페이지끼리만 합치는것이었다. 그 후 문제를 이해하고 DP라는 것 까지 알았지만 코드를 짜는것이 쉽지않다. dp[i][j] = i번째 장부터 j번째 장까지 합치는데 드는 최소한의 비용. dp[i][j] = min{dp[i][k] + dp[k+1][j]} + sum[end] - sum[start-1]. 단, (start

풀이 브루투포스 알고리즘으로 푸는 문제이다. 따라서 for문을 통해 각 진법으로 바꾸고 거꾸로 뒤집어도 회문인 수인지 판별 해주면 되었다. 처음에 각 진법으로 변환할때 문자를 이용해 비교하려고 하였으나 그냥 나머지 값이 같은지 비교하도록 하였다. 코드 #include #include #include #include using namespace std; int main() { int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); vector v; v.clear(); bool flag = true; for(int b = 2; b

21.11.14일 추가함. 문제를 보고 인공지능 시간에 배운 게임이론이라는 것을 알았다. min max 트리를 그려서 풀려고 했는데 역시 이론만 아는것이랑 실제 코드를 짜는것은 다르다는것을 느꼈다.. 그리고 재귀 호출시에 vector를 복사해주었는데 이부분에서도 시간초과가 발생하였다. 사소한 것이라 생각했지만 문제풀이에 크게 차이난다는 것을 느꼈다. 이번 문제에서 알게된 것 재귀함수 호출시에 배열, 벡터 등의 값을 복사할 떄는 시간과 메모리 공간이 많이 소모되기 때문에 레페런스로 호출해주도록 한다. 이론을 아는것과 구현은 다르다. min max 알고리즘(게임이론)에서 나를 기준으로 보고 상대의 점수가 min이 되도록 선택하도록 해야한다. dp[left][right]는 내가 얻을 수 있는 점수이기 때문에 ..

유클리드 호제법 유클리드 호제법은 유클리드가 발견한 두 수의 최대공약수를 구하는 방법이다. 원래 우리가 초등학교때 배운 방법은 컴퓨터에서 실행하려고 할 때, 두 수가 커지면 비효율적으로 동작하게 된다. 따라서 유클리드 호제법을 이용해 최대공약수를 구하고 그 다음 최소공배수를 구해야한다. 최대공약수 반복문을 이용해 구현한 유클리드 호제법은 다음과 같다. int GCD(int a, int b) { while(b!=0) { int c = a % b; a = b; b = c; } return a; } 최소공배수 두 수의 곱은 두 수의 최대공약수와 최소공배수와 같다는 수학적 성질을 이용해 최소공배수를 구한다. 예를 들어 10와 15의 최대공약수는 5이다. 따라서 최소공배수를 구하기 위해서 다음과 같은 식을 만족한..

풀이 먼저 문제에서 이해한것을 바탕으로 구현하였더니 시간초과가 났다. 그 이유는 for문을 2부터 증가시키면서 매번 lcm을 찾아 계산해주었기 때문이다. 이제 생각을 바꿔 반복문의 수를 줄여야 한다. 다음의 값을 x1에 대해 정리해 왼쪽으로 이동시킨다. (x1 >= b / a) 이러면 x1은 다음값을 만족시키는 가장 작은 정수가 된다. 따라서 x1 = b / a + 1의 값이 분자가 1이면서 가장 큰 단위분수를 구한것이다. 이 과정을 a가 1이 될때까지 반복한다. 코드 #include #include #include int gcd(int a, int b) { while(b!=0) { int c = a % b; a = b; b = c; } return a; } int lcm(int a, int b) { r..

문제 설명 문제를 이해하는데 조금 걸렸다. k번 이상 인용된 논문이 k편 이상이고 나머지 n − k 편의 논문들 인용회수가 각각 k 번 이하라면, 해당 학생의 q-인덱스는 k이다. 위의 말은 논문 인용 횟수를 오름차순으로 정렬하고(밑의 코드의 vector v), k가 인용횟수의 어느 위치에 있는지 찾아준다(내부 for문). 이 부분은 k를 기준으로 인용횟수의 왼쪽과 오른쪽이 나누어서 조건을 파악하기 위해서이다. 이부분을 만족하는 최대의 k값을 구한다. 코드 #include #include #include #include using namespace std; int main() { int n; scanf("%d", &n); vector v; v.resize(n); for(int i = 0; i < n ; ..

이 문제는 다이나믹 프로그래밍으로 분류되어있지만 문제의 이해와 원리를 파악하면 풀 수 있는 문제입니다. 이진포화트리는 Perfect binary tree로 불리며 꽉꽉채워진 이진트리 입니다. 자세한 설명은 다음링크로 남겨놓도록 하겠습니다. https://yaboong.github.io/data-structures/2018/02/10/1_binary-tree-1/ Binary Tree 종류 - Heap 구현 사전지식 개요 Heap 구현을 위한 Binary Tree 의 기초적인 개념에 대해 알아본다. yaboong.github.io 풀이 저는 weight와 node 두가지 vector를 int형으로 선언해 사용하였습니다. 먼저 weight에 각 edge들의 가중치를 입력받았고 node는 각 edge들의 we..