Whatever floats your boat

풀이 일단 시간제한이 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..

알고리즘 문제를 풀다보면 정렬을 해야할 때가 많으며 대부분 c++ 라이브러리를 사용하여 정렬을 하는 경우가 많다. 이번엔 sort함수를 간단하게 알아보고 정렬하기 위해 sort의 세번째 인자로 전달해 주는 함수 사용법을 알아보도록 하겠다. sort() 란 먼저 sort()를 사용하기 위해 algorithm 헤더파일을 include 해야한다. sort 함수는 내부적으로 IntroSort라는 정렬 방법으로 구현되어있다. 이 방법은 QuickSort와 HeapSort와 InsertionSort를 합쳐놓은 방식으로 평균 nlogn, 최악의 경우 n^2의 시간 복잡도를 가지는 QuickSort와는 달리, 최악의 경우에도 nlogn을 복잡도를 보장한다. https://en.wikipedia.org/wiki/Intr..

그리디 알고리즘 그리디 알고리즘은 탐욕 알고리즘이라고도 불리며 어떤 순간에 가장 최선의 선택을 하는것을 말한다. 특징은 local하게 최적의 선택을 하는것이 결국 global하게 최적의 해를 도출해준다. Activity-selection-problem이란? 그리디 알고리즘을 보여주는 한 예시이며 문제는 다음과 같다. 한개의 강의실에 n개의 수업들이 있다. 이때 각 수업은 시작시간 끝나는 시간이 주어진다. 이때, 한개의 강의실에서 수업이 최대 개수가 될 수 있도록 하는 수업 수를 찾으시오. 이때 문제를 해결하기 위해서는 끝나는 시간을 기준으로 오름차순 정렬한다. 그리고 겹치지 않는 선에서 수업을 선택하여준다. 다음은 위의 문제풀이 방식의 증명이다. 1 < x < y 이면서 수업의 최대 개수 집합이 A = ..