꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/TSP3http://jaimemin.tistory.com/365과 동일한 문제였지만 동적계획법보다 빠른 코드를 요구하는 문제였습니다.동적계획법보다 빠르게 동작하기 위해 휴리스틱 기법을 이용하여 완전탐색법에서 가지치기를 하며 실행속도를 단축시켰습니다.'조합 탐색' 기법이고 MST(Minimum Spanning Tree)를 이용하기 때문에 처음에 disjointSet 구조체를 정의하였습니다. /* 여행하는 외판원 문제 동적계획법보다 빠르게 수행하기 위해 휴리스틱 기법을 적용 */ #include #include #include #include #include using namespace std; const double ..

문제 링크입니다: https://www.acmicpc.net/problem/2163사실 메모이제이션으로 풀지 않고 간단한 곱셈을 통해 풀 수 있는 문제였습니다.하지만 문제를 푸는 과정이 중요하기 때문에 다이나믹 프로그래밍으로도 풀어봤습니다. /* 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 같이 초..

문제 링크입니다: https://www.acmicpc.net/problem/1699처음에 안일하게 생각했다가 틀린 문제였습니다.틀린 코드와 맞은 코드를 비교하면 쉽게 이해할 수 있는 문제입니다.우선 틀린 코드입니다./* 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게..

문제 링크입니다: https://www.acmicpc.net/problem/2294백준 2293번 동전 1(http://jaimemin.tistory.com/362)과 유사한 문제였습니다. /* n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.) */ #include #include #include //memset using namespace std; const int MAX = 10000 + 1; int coinNum, total; //동전 갯수, 총합 int coinValue[101], cache[MAX]; int m..

문제 링크입니다: https://www.acmicpc.net/problem/1006얼핏 보면 완전탐색법을 통해 쉽게 풀 수 있는 문제로 보이지만 사실 조건이 엄청 많은 문제였습니다.제가 풀었을 때는 무슨 이유인지 모르겠지만 계속 런타임 오류가 발생했습니다.그래서 다른 사람들의 코드를 참고해서 작성해보려고 했는데 우연히 들어가본 블로그에 너무나도 완벽한 코드가 있어서 그 코드에 주석을 추가해서 제 나름대로 해석해봤습니다.참고한 블로그 -> https://blog.naver.com/whgksdyd112/220956454574 /* 문제가 길기 때문에 생략 */ #include #include #include //memset using namespace std; const int MAX = 10000; int..

문제 링크입니다: https://www.acmicpc.net/problem/11047가치가 큰 동전부터 더해나가는 것이 핵심이였습니다. /* 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만드려고 한다. 이 때 필요한 동전 개수의 최소값을 구하는 프로그램을 작성하시오. */ #include #include using namespace std; int N; //동전 수 int total; //총합 vector v; int minCoin(void) { int cnt = 0; for(int i=v.size()-1; i>=0; i--) //가치가 큰 동전부터 빼야 최소 반환 while (total - v[i] >= 0) { tota..

문제 링크입니다: https://www.acmicpc.net/problem/11727http://jaimemin.tistory.com/323와 비슷한 문제였습니다.2*2 타일이 추가되었으므로 밑변의 길이가 2인 경우를 2배하는 것이 핵심이였습니다. /* 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. */ #include #include //memset using namespace std; const int MOD = 10007; int N; int cache[1001]; //2*width 크기의 사각형을 채우는 방법의 수를 MOD로 나눈 나머지 반환 int tiling(int width) { //기저 사례:width가 1 이하일 때 if (width > N; ..

문제 링크입니다: https://algospot.com/judge/problem/read/MINASTIRITH cmath 헤더파일이 존재한다는 것에 정말 감사함을 느낀 문제였습니다.공학수학처럼 arcsin과 arctan를 직접 구해야했다면... 생각만해도 끔찍합니다. 다음은 초소 반경들을 초소 중심점을 이용하여 미나스아노르의 구간(활꼴)으로 바꾸는 내용입니다.빨간색이 초소 반경이고, 검은색 원은 성의 반경입니다. #include #include #include using namespace std; const int INF = 987654321; const double pi = 2.0*acos(0); //cos(π/2)=0 -> 따라서 아크코사인(0)=π/2 int postNum; double y[100]..

문제 링크입니다: https://algospot.com/judge/problem/read/STRJOIN 허프만 코드와 비슷한 개념으로 문제를 풀면 됩니다.(https://ko.wikipedia.org/wiki/%ED%97%88%ED%94%84%EB%A7%8C_%EB%B6%80%ED%98%B8%ED%99%94) 허프만 코드는 출현빈도가 높은 문자를 트리 상단에 배치하는데 이 문제에서는 출현빈도 대신 문자열의 길이가 길수록 트리 상단에 배치하면 됩니다.예를 들어 두 번째 테스트 케이스를 그림으로 표현해봤습니다.원 안에 있는 숫자들이 초기에 입력된 문자열의 길이이고, 네모가 합쳤을 때 드는 비용입니다.즉, 네모를 모두 합치면(2+5+7+12) 문자열을 합치는데 드는 최소 비용(26)이 나옵니다. /* n개의 ..

문제 링크입니다: https://algospot.com/judge/problem/read/LUNCHBOX데우는 시간은 상관이 없고 먹는 시간이 식사시간을 좌지우지한다는 것이 핵심이였습니다. /* 유명한 도시락 업체에서 n개의 도시락을 주문했다. 주문량이 많아서 한가지 도시락만 주문할 수는 없었기 때문에 여러가지 종류의 도시락을 주문했다. 하지만 전자레인지는 하나뿐이고 출력량도 적어 한번에 한 도시락만 데울 수 있다. 이 때, 식사시간을 최소화 하려면 어떻게 해야할까? */ #include #include #include using namespace std; const int MAX = 10000; //boxNum> test_case; if (test_case 300) exi..