알고리즘/프로그래머스 (22) 썸네일형 리스트형 [프로그래머스] 예산 예산 1. 이해하기 정해진 총액 이하에서 가능한 한 최대의 총 예산을 배정한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 이분탐색 문제이다. 2. 구현하기 이분탐색을 하기 위해서 요청중 가장 큰 금액을 찾아서 그 금액과 제일 낮은 금액인 1을 비교한다. 상한액을 만들고 이에 맞춰 예산을 계산해본다. 총액과 비교하고 작으면 낮은 금액을 중간 값+1으로, 크면 큰 금액을 중간 값-1으로 바꿔 다시 계산한다. long long l = 1, r = 0; for(int i = 0; i < budgets... [프로그래머스] 디스크 컨트롤러 디스크 컨트롤러 1. 이해하기 하드디스크는 한 번에 하나의 작업만 수행할 수 있다. 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리할때 평균을 구하는 문제. 2. 구현하기 우선순위 큐를 이용하여 처리 시간이 가장 짧은 것부터 처리하게 한다. 이때 큐를 이용하면 원하는 위치의 삭제가 힘드니 우선순위 큐의 결과를 벡터에 담는다. priority_queue pq; for(int i = 0; i < jobs.size(); i++) pq.push({-jobs[i][1],jobs[i][0]}); vector job; for(int i = 0; i < jobs.size(); i++) { job.push_back(pq.top()); pq.pop(); } 시간과 일의 시작시간을 비교하여 시작시간이.. [프로그래머스] 가장 먼 노드 가장 먼 노드 1. 이해하기 1번 노드에서 가장 먼 노드의 갯수를 구한다. 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미한다. bfs를 이용해서 구할 수 있다. 2. 구현하기 bfs를 이용하여 1번에서 각 노드까지의 거리를 구한다. 그 이전에 edge로 주어진 각 노드들의 연결관계를 인접리스트로 바꾼다. void bfs() { queue q; q.push(1); visited[1] = true; dist[1] = 0; while(!q.empty()) { int here = q.front(); q.pop(); for(int i = 0; i < adj[here].size(); i++) { int there = adj[here][i]; if(visited[there].. [프로그래머스] 단어 변환 단어 변환 1. 이해하기 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾는 것이다. 한 번에 한 개의 알파벳만 바꿀 수 있다. words에 있는 단어로만 변환할 수 있다. dfs를 이용하여 찾을 수 있다. 2. 구현하기 dfs함수를 만든다. dfs(now,target,depth,visited,words): 현재와 target을 비교해서 같으면 최소 과정을 반환해준다. 현재까지 찾은 과정보다 더 많은 과정을 찾으려고 하는 경우에는 바로 끝나도록 해준다. 있는 단어들을 모두 살펴보면서 이미 지나온 경우는 패스할 수 있도록 visited를 이용한다. 또한 고른 단어와 현재 단어가 한글자만 다른지 확인하고 맞다면 dfs를 반복한다. void dfs(string now, string target.. 타일 장식물 1234567891011121314151617#include #include using namespace std; long long dp[80] = {0}; long long solution(int N) { if(N == 1) return 4; dp[0] = 1; dp[1] = 1; for(int i = 2; i 카펫 12345678910111213141516171819202122232425262728#include #include using namespace std; vector solution(int brown, int red) { vector answer; int sum = brown + red; for(int i = 3; i * i j) { answer.push_back(i); answer.push_back(j); } else { answer.push_back(j); answer.push_back(i); } } } } return answer;}Colored by Color Scriptercs 이 문제는 규칙을 찾으면 간단한 문제이다. 먼저 첫번째 예시를 기준으로 설명하면 갈색이 10개, 빨간색이 2개이다. 그.. 전화번호 목록 12345678910111213141516171819202122232425262728#include #include #include #include using namespace std; bool solution(vector phone_book) { if(phone_book.size() == 1) return true; int size = phone_book.size(); for(int i = 0; i 2 x n 타일링 12345678910111213141516#include #include using namespace std; int solution(int n) { int i, tale[60000]; tale[0] = 0; tale[1] = 1; tale[2] = 2; for(i = 3; i 이전 1 2 3 다음
