꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/ALLERGYhttp://jaimemin.tistory.com/414?category=985009에서 동일한 문제를 다뤘었습니다.책에서 최적화하는 방법에 먹을 수 있는 음식의 종류가 적은 친구들부터 찾으면 실행속도가 빨라질 것이라고 명시되어있어 그대로 프로그램을 작성해봤습니다.결과는 실행속도 8ms로 만족스러운 결과가 나왔습니다. #include #include #include #include #include #include //memset using namespace std; int friendNum, foodNum; //canEat[i]: i번 친구가 먹을 수 있는 음식의 집합 //eaters[i]= i번 음식을..

문제 링크입니다: https://algospot.com/judge/problem/read/ALLERGYslowSearch와 search의 코드 구성은 크게 다르지 않습니다.하지만 탐색순서가 다르기 때문에 다음과 같은 차이가 생겼습니다.1. search()는 항상 모든 친구가 먹을 음식이 있는 조합만을 찾아냅니다. 하지만 slowSearch()는 마지막 조각까지 결정한 뒤에도 배고픈 친구가 남는 경우들도 모두 탐색하게됩니다.2. search()는 한 번 호출될 때마다 항상 음식을 하나 하게 됩니다. (즉, 음식을 한다는 말은 음식이 필요한 친구가 반드시 있다는 의미) 반면 slowSearch()는 음식을 하지 않고도 재귀호출을 할 수 있습니다.(반드시 필요하지 않은 음식을 만드는 경우도 있다) #inclu..

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

http://jaimemin.tistory.com/391?category=988050과 비슷한 문제입니다.두가지 다른 점은 다음과 같습니다.1. 백준 1931번 문제와 달리 한 회의의 소요시간은 1 이상이고2. 한 회의의 끝과 그 다음 회의의 시작은 동일할 수 없다는 점입니다.(이런 경우 겹친다고 여긴다.) 물론 탐욕법(greedy method)를 사용하면 쉽게 풀리지만 동적계획법을 연습 중이기 때문에 동적계획법으로도 풀어봤습니다. /* 회사에 회의실이 하나밖에 없는데, n(0; i--) for(int j=i-1; j>0; j--) if (meeting[i].start > meeting[j].end) { before[i] = j; break; } } int schedule(int idx) { if (id..

문제 링크입니다: https://algospot.com/judge/problem/read/MATCHORDERN의 범위가 1~100이기 때문에 완전탐색법과 동적계획법을 사용하면 시간초과가 발생하는 문제였습니다.따라서 탐욕 알고리즘을 사용하여 프로그램을 작성했습니다. #include #include #include #include using namespace std; int order(const vector &russian, const vector &korean) { int length = russian.size(), wins = 0; //아직 남아 있는 선수들의 레이팅 multiset ratings(korean.begin(), korean.end()); //성적 순 정렬 for (int rus = 0; r..

문제 링크입니다: https://algospot.com/judge/problem/read/GENIUS두니발 박사의 탈옥(http://jaimemin.tistory.com/335)과 유사한 문제였습니다.다른 점이라면 다음 곡이 나올 확률이 다르다는 점이였습니다.직관적으로 해석해서 프로그래밍을 하면 편하지만 K(시간)의 범위가 크기 때문에 시간초과가 발생합니다.따라서 피보나치 수열처럼 행렬을 사용하여 푸는 것이 핵심입니다. #include #include #include using namespace std; int songNum, K, length[50]; //곡 갯수, K분 후, 곡의 길이 double T[50][50]; //다음에 나올 곡 확률 class SquareMatrix { private: vec..