꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/4883 문제 정답률에 비해 쉬웠던 DP 문제였습니다.핵심은 4가지 방향을 고려해주는 문제였습니다: 오른쪽, 왼쪽 아래, 아래, 오른쪽 아래이 때, 범위를 벗어나는 경우 INF를 반환하게 하여 최소 비용을 찾게 해주면 쉽게 정답을 찾을 수 있는 문제였습니다.방심하고 문제 대충 읽다가 오른쪽을 고려안해서 정답률 하락에 보탬을 했던 것은 함정... #include #include #include //memset using namespace std; const int MAX = 100000; const int INF = 987654321; int N; int graph[MAX][3]; long long cache[MAX][3]; lon..

문제 링크입니다: https://www.acmicpc.net/problem/2666 벽장문의 이동 문제에서는 캐쉬에 변수가 세개가 필요합니다: 순서 인덱스, 열려있는 1번 문 인덱스 , 열려있는 2번 문 인덱스한번에 하나의 문을 이동하므로 두 가지 경우만 고려합니다.1. 1번 문을 이동하는 경우2. 2번 문을 이동하는 경우 이 때, 해당 순서 인덱스가 열려있는 문들의 인덱스보다 작을 수 있기 때문에 두 수의 뺄셈(이동 거리)를 절대값으로 처리해줘야합니다. #include #include #include //memsetusing namespace std; const int MAX = 20 + 1; int N, doorNum;int order[MAX];int cache[MAX][MAX][MAX]; //벽장 ..

문제 링크입니다: https://www.acmicpc.net/problem/2616 알고리즘 자체는 간단했습니다.1. 해당 칸을 끌고 가지 않거나2. 해당 칸을 최대 끌 수 있는만큼 끌고 간다. 그런데 여기서 간과한게 배열의 인덱스였습니다.계속 런타임 에러가 떠도 도저히 이유를 모르겠었는데 배열 인덱스 범위 초과 때문이라는 것을 깨닫고조건문에 if(idx + maxCarry - 1 = passengerCarNum) return 0; int &result = cache[trainNum][idx]; if (result != -1) return result; result = 0; //해당 객차를 끌고 가지 않을 경우 //해당 객차를 끌고 갈 경우 if(idx + maxCarry - 1 > passengerCa..

문제 링크입니다: https://www.acmicpc.net/problem/15483 Edit Distance 알고리즘 문제였습니다.간단하게 설명하기 위해 문자열 DOG와 SOL로 설명하겠습니다. 공백 D O G 공백 0 1 2 3 S 1 1 2 3 O 2 2 1 2 L 3 3 2 2 SOL을 기준으로 다음 과정을 설명하자면 (공백을 0으로 표현)i) 0a) 0->0: (0)b) 0->0D: D 삽입(1)c) 0->0DO: DO 삽입(2)d) 0->0DOG: DOG 삽입(3)ii) 0S a) 0S->0: S 삭제(1)b) 0S->0D: S->D 치환(1)c) 0S->0DO: S->D 치환 + O 추가(2)d) 0S->0DOG: S->D 치환 + OG 추가(3)iii) 0SO a) 0SO->0: SO 삭제..

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