본문 바로가기

INT NUM

 (145)
algospot :: STRJOIN 문자열 합치기 문제 : https://algospot.com/judge/problem/read/STRJOIN알고리즘 문제 해결 전략 p. 382책을 참고하지 않고 코드를 작성함 [알고리즘 STEP. 1]문제의 예제에서 보여주듯, 짧은 문자열 부터 합쳐나가면서 완성해야 가장 효율적이다. 책에서는 이렇게 설명한다 각 비용을 분해해 보면, 한 문자열을 만드는 데 발생하는 총 비용은 이 문자열이 병합되는 횟수에 문자열의 길이를 곱한 것이라는 것을 알 수 있습니다.따라서 문자열의 길이가 길수록 트리의 윗쪽에 가깝고, 짧을수록 아래에 가까워야 한다는 직관을 얻을 수 있습니다.- 알고리즘 문제 해결 전략 p. 383 이를 구현하는 알고리즘은 다음과 같다. 문제에서 주어지는 문자열 길이 배열을 크기가 작은 순으로 Sort한 배열을 ..
algospot :: LUNCHBOX 도시락 데우기 문제 : https://algospot.com/judge/problem/read/LUNCHBOX알고리즘 문제 해결 전략 p.397책을 참고하지 않고 코드를 작성함 [알고리즘 SPEP. 1]최대한 효율적으로 도시락을 데워 먹으려면, 어차피 전자레인지는 계속 돌아가야 한다.전자레인지에 돌리는 시간의 합(A) + 먹는데 쓰는 것 중에 저 시간을 넘어가는 시간(B)을 최소화 해야 하는데, A는 어차피 고정값이고 B를 어떻게 최소화 할 지를 생각해야한다. 어차피 전자레인지를 다 돌린 후에야 도시락을 먹을 수 있으므로, 도시락 데우는 시간은 고려하지 않고, 먹는 시간이 짧은 순으로 도시락들을 정렬한다.그 다음에 그 순서의 역순으로 전자레인지를 돌리도록 하면 최적의 해를 구할 수 있다. 즉 "먹는 시간이 짧은 순으로..
algospot :: MATCHORDER 출전 순서 정하기 문제 : https://algospot.com/judge/problem/read/MATCHORDER알고리즘 문제 해결 전략 p. 371책을 참고하지 않고 코드를 작성함 [알고리즘 STEP. 1]러시아 선수들을 실력이 낮은 순에서 높은 순으로 정렬한 후에, 우리의 선수들로 이길 수 있는 가장 실력이 높은 순서까지만 이기면 된다. 일단 문제에서 주어진 선수들의 실력을 정렬하자. 러시아1900 2200 2500 2700 2800 3000한국 1800 2000 2600 2750 2800 2995 한국의 1800선수로는 1900선수를 이길 수 없다. 1800 선수는 아무도 이길 수 없으므로 제일 잘하는 사람이랑 붙어서 지든 말든 상관이 없다.그럼 일단 러시아 1900 선수는 한국 2000선수와 매칭시켜서 이기도록..
그리디 알고리즘 (탐욕법, Greedy Algorithm) 알고리즘 문제 해결 전략 p. 368 [탐욕법을 사용하는 이유]1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적 계획법보다 훨씬 수행시간이 빠르므로 유용2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면, 적당히 괜찮은 답을 찾는 것으로 타협할 수 있음. 탐욕법은 최적은 아니지만 임의의 답보다는 좋은 답을 구하는 용도로 유용하게 쓰임 [정당성의 증명]-문제- 회의실 예약. 회의 시간들이 주어졌을 때 가장 많은 회의를 열 수 있도록 회의실을 스케쥴링 한다. - 탐욕법을 이용한 해결-S = { 주어진 회의들 } = {s1, s2, ... }1. 목록 S중 가장 일찍 끝나는 회의 s(min)를 선택한다.2. S 중 s(min)과 겹치는 회의를 S에..
피보나치 수열과 행렬 거듭제곱 백준 블로그 글을 보며 공부한 내용입니다. 원래 코드 및 글 : https://www.acmicpc.net/blog/view/28 #include #include using namespace std; typedef vector matrix; const long long mod = 1000000007LL; //연산자 재 정의. // 정사각행렬의 곱셈 //c++는 객체에 따라서 연산자를 알아서 바꿔서 해석해주므로 그냥 * 로 이용할 수 있음 matrix operator * (const matrix &a, const matrix &b){ int n = a.size(); //vector v(n,0) means you're creating a vector of size n and initializing its e..
algospot :: NUMBERGAME 숫자게임 문제 : https://algospot.com/judge/problem/read/NUMBERGAME알고리즘 문제 해결 전략 p.342 [알고리즘 STEP. 1]어차피 숫자를 양 끝에서만 지울 수 있으므로, 지워진 숫자들을 고려할 범위 밖으로 밀어내는 방식으로 지울 수 있다.예를들어 처음에 5개 숫자가 들어왔다면 인덱스 0, 1, 2, 3, 4를 다 고려하다가왼쪽에서 하나를 지웠으면 1,2,3,4만,오른쪽에서 두개를 또 지우면 1,2 만이렇게 남은 인덱스들만 고려하여 문제를 풀면 된다. 남은 숫자 중 왼쪽 끝 인덱스를 st, 오른쪽 끝 인덱스를 ed로 잡고 다음 함수를 작성하였다. *int play(int st, int ed)이미 st부터 ed까지 남은 인덱스에서 게임을 플레이했다면 캐시에서 해당 값을 가..
algospot :: RESTORE 실험 데이터 복구하기 문제 : https://algospot.com/judge/problem/read/RESTORE알고리즘 문제 해결 전략 1권 p.329 [알고리즘 STEP. 1]결국 주어진 문자열 조각들을 모두 조합해서 이어보면서 총 길이가 최소가 되는 (= 겹치는 부분이 최대가 되는) 문자열을 출력하면 된다. 이는 외판원문제 (http://int-num.tistory.com/18)와 거의 똑같은 알고리즘이다. 거리 합의 최소를 반환하던걸 (겹치는)길이 합의 최대를 반환하도록 바꾸기만 하면 된다. 먼저 주어진 문자열 조각들의 겹치는 부분들의 길이를 먼저 구해서 행렬에 저장한다. *int calcCommon(int i , int j)i번째 문자열 뒤에 j번째 문자열을 붙일 때, 겹치는 길이를 반환한다. 1) i번째 문자열이..
algospot :: TSP2 Traveling Salesman Problem 2 문제 : https://algospot.com/judge/problem/read/TSP2알고리즘 문제 해결 전략 1권 p. 319주어진 문제와 책에 주어진 코드가 조금 다름 [알고리즘 STEP.1]지금 있는 도시와 지금까지 방문한 도시를 바탕으로, 남은 도시를 모두 방문하는 거리 합의 최소값을 재귀적으로 구해야 한다. *double cache[MAX][1

티스토리툴바