알고리즘 (25) 썸네일형 리스트형 BOJ-5397 문제풀이 1. vector 2개를 이용하면 쉽게 풀 수 있는 문제이다. 2. vector 하나는 왼쪽, 하나는 오른쪽에 위치한다고 생각하고 ""에 따라 왼쪽에서 오른쪽, 혹은 오른쪽에서 왼쪽으로 vector의 back에 존재하는 문자를 옮겨준다. 3. 위의 과정을 반복하고 첫번째 vector와 두번째 vector를 reverse한 결과를 출력한다. 4. 직접 그림을 그려보면서 생각하면 편함. 31분 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include #include us.. [C++] BOJ-2529 문제풀이 1. 기본적인 LIS(최장 증가 수열)를 찾는 문제이다. 2. 수열 v의 마지막 요소와 현재 입력받은 값을 비교하여 더 크면 v의 마지막에 넣고 그렇지 않으면 수열 v의 숫자들 중 가장 적당한 자리에 있는 숫자와 교체해준다. 3. 여기에서 적당한 자리라는 것은 만약 수열 v의 상태가 10, 30, 50 이고 현재 입력받은 값이 40이라면 50과 40을 교체한다. (이 문제는 수열 그 자체를 구하는것이 아니라 수열의 길이를 구하는것이기 때문에 이러한 방식으로 숫자를 교체해주어도 답을 출력하는데에 지장은 없다.) 38분 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include #include.. [C++] BOJ-1826 문제풀이 1. 우선순위큐 한개와 pair형 배열변수 한개를 선언한다. 2. 주유소의 정보가 담겨있는 배열을 오름차순으로 sort한다. 3. 현재 가지고있는 연료의 양으로 최대로 갈 수 있는 거리까지의 주유소에서 넣을 수 있는 연료량을 모두 우선순위 큐에 넣는다. 4. 우선순위큐의 top에 있는 연료량이 제일 높을 것이므로 top을 트럭에 있는 연료량에 더해준다. 그리고 그때마다 1씩 카운트해준다. 5. 트럭에 있는 연료량이 도착범위를 넘어가거나 혹은 우선순위큐가 비어있으면 반복문을 종료한다. 6. 마지막으로 트럭에 있는 연료량이 마을에 도착하는데에 충분하다면 cnt를 출력하고 그렇지 않으면 -1을 출력한다. 1시간 26분 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1.. [C++] BOJ-9576 문제풀이 1. pair형 배열변수에 신청서 정보를 넣고 bool 형 배열변수를 선언한다. 2. pair변수의 second의 크기에 따라 오름차순으로 정렬하되 만약 second의 크기가 같다면 first크기에 따라 내림차순으로 정렬을 해야한다. (그리디하게 문제를 해결해야 함) 3. 그 후 반복문을 통해서 만약 book 배열에 false로 남아있는 책 중 하나라도 학생이 원하는 책이 false라면 그 책을 true로 바꿔주고 다음 학생의 신청서로 넘어간다. p.s) 이 문제는 사실 정당성 증명을 하진 못했다. 그냥 뭔가 직관적으로 떠올라서 (왠지 이런 원리일 것 같은데..?) 그대로 구현해보니 정답이 떴다. 45분 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 .. [C++] BOJ-1202 문제풀이 1. pair형 변수에 보석의 정보를 입력하고, backpack 변수에 가방의 정보를 입력한다. 2. 보석배열은 무게에 따라 정렬을 해주고 backpack 배열도 마찬가지로 정렬을 해준다.(오름차순) 3. 가방의 개수에 따라 반복문을 돌리는데 여기서 현재 선택된 가방에 넣을 수 있는 모든 보석의 가격을 우선순위큐에 집어넣습니다. 4. 그렇게 되면 우선순위 큐의 top에 위치한 보석이 현재 선택된 가방에 넣을 수 있는 보석 중 가장 비싼 보석이기 때문에 sum 변수에 더해주고 pop 해줍니다. 5. 위의 과정을 모든 가방에 대해서 반복합니다. 1시간 6분 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30.. [C++] BOJ-1655 문제풀이 1. max_heap과 min_heap을 2개 선언한다. 2. min_heap의 top이 max_heap의 top보다 작으면 두 우선순위 큐의 탑을 스왑해준다. 3. 이 과정을 진행하면 max_heap의 top은 항상 가운데 숫자이기 때문에 max_heap의 top을 출력하면 된다. (직접 그려보면서 이해하면 쉽다.) 41분 01초 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); priority_queue max_.. [C++] BOJ-1715 문제풀이 1. 우선순위 큐에 각각의 카드 묶음의 크기를 집어넣는다. 2. 우선순위 큐에 들어있는 카드묶음 중 가장 작은 것들중 2개를 더하고 그 카드묶음을 다시 우선순위 큐에 넣는다. 3. 이 과정을 반복하면서 sum에 계속 더해주고 더 이상 비교할 수 있는 카드 묶음이 없다면 sum을 출력한다. 27분 14초 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); priority_queue pq; int N, num, sum = 0; cin >> N.. [C++] BOJ-2529 문제풀이 1. 재귀함수로 모든 경우의 수를 탐색해서 부등호의 조건에 맞는 수열을 찾는다. 2. k가 0일 경우를 제외하고 수열의 k-1번째 요소와 현재 들어갈 숫자를 비교해서 부등호의 조건에 맞다면 수열에 집어넣는다. 3. 제일 마지막에 저장된 수열과 제일 처음 저장된 수열을 출력한다. 4. 재귀함수를 통해 0부터 차근차근 탐색하기 때문에 처음과 마지막에 저장된 수열을 그대로 출력해도 답이 나온다. 57분 49초 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 .. 이전 1 2 3 4 다음
