꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/CANADATRIP이번에도 이분법을 이용하여 푸는 문제였습니다.표지판을 일일히 나열하면 언젠가는 찾을 수 있겠지만 표지판의 개수가 (2^31 - 1)개일수도 있기 때문에 이분법을 이용하여 풀어야 시간 안에 동작합니다. /* 중략 */ #include #include using namespace std; const int MAX = 5000; const int drive = 8030000; //총 주행 거리 int N, K; //도시의 수, K번째 표지판 //도시까지의 거리, markStart미터 전부터 표지판 시작, interval미터마다 표지판 int length[MAX], markStart[MAX], interv..

문제 링크입니다: https://algospot.com/judge/problem/read/ARCTIChttp://jaimemin.tistory.com/421?category=985009와 유사하게 이분법을 사용하여 푸는 문제였습니다.한가지 흠이라면 ARCTIC은 북극이므로 제목을 북극기지로 지었어야했다는 점입니다. /* 남극에는 N 개의 탐사 기지가 있습니다.남극의 겨울은 혹독하기 때문에, 남극의 겨울이 찾아오면 탐사 기지들간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, N 개의 무전기를 구입해 각 탐사 기지에 배치하려 합니다. 이 때, 두 탐사 기지 사이의 거리가 D 라고 하면, 무전기의 출력이 D 이상이어야만 통신이 가능합니다. 모든 탐사 기지에는 똑같은 무전기가 지급됩니다. ..

문제 링크입니다: https://algospot.com/judge/problem/read/DARPA답이 자연수로 표현 가능하더라도 소수 둘째자리까지 표현하는 것이 포인트이기 때문에 iomanip 헤더파일을 추가하고cout test_case; if (test_case 50) exit(-1); for (int i = 0; i > cameraNum >> installNum; for (int j = 0; j > coord; location.push_back(coord); } sort(location.begin(), location.end..

문제 링크입니다: https://algospot.com/judge/problem/read/KAKURO2상당히 흥미로운 문제였습니다.(물론 엄청 어려웠습니다...)책을 보면 볼수록 비트연산의 중요성을 깨닫고 있습니다. /* 카쿠로는 흔히 십자말풀이 수학 버전이라고 불리는 논리 퍼즐이다. 카쿠로는 위와 같이 생긴 정사각형의 게임판을 가지고 하는 퍼즐로, 이 게임판의 각 칸은 흰 칸이거나, 검은 칸이거나, 힌트 칸이다. (힌트 칸은, 대각선으로 갈라져 있고 숫자가 씌여 있는 칸을 말한다) 모든 흰 칸에 적절히 숫자를 채워 넣어 규칙을 만족시키는 것이 이 게임의 목표이다. 카쿠로의 규칙은 다음과 같다. 1. 모든 흰 칸에는 1 부터 9 까지의 정수를 써넣어야 한다. 2. 세로로 연속한 흰 칸들의 수를 모두 더하..

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