꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2167요구사항이 살짝 모호했던 문제였습니다. 처음에는 (i, j)~(x, y)까지의 배열의 합을 전부 구하는 문제인 줄 알았습니다.여기서 진짜 요구하는 답은 행번호 i 이상 x 이하 그리고 열번호 j 이상 y 이하인 인덱스의 합이였습니다.완전탐색법과 다이나믹 프로그래밍의 실행속도 차이가 명확하게 드러나는 문제였습니다. /* 2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. */ //완전 탐색법 /* #include #include //memset using namespace std; const int MAX = 300 + 1; int arr[MAX][..

문제 링크입니다: https://www.acmicpc.net/problem/9465동적계획법이라고는 했지만 거의 완전탐색법으로 푼 문제였습니다.(그 결과 실행속도...)핵심은 전 대각선과 전전 대각선만 비교하면 된다는 것이였습니다. /* 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림(a)와 같이 2행 n열로 배치되어 있다.상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이..

문제 링크입니다: https://algospot.com/judge/problem/read/BOARDCOVER2http://jaimemin.tistory.com/302와 유사한 문제였습니다.가지치기 조건을 찾는 것과 네가지 회전 형태를 미리 만들어보는 것이 핵심이였습니다. #include #include #include #include using namespace std; //게임판 정보 int boardH, boardW; //board Height(세로), board Width(가로) vector board; //블록의 크기 int blockSize; //게임판의 각 칸이 덮였는지를 나타낸다 //1이면 #이거나 이미 덮은 칸, 0이면 . int covered[10][10]; //블록의 회전된 형태를 계산..

문제 링크입니다: 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; ..