컴굥일지

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42626 문제 내용 음식들의 지수가 모두 K 이상이 되기 위해 몇 번의 연산이 필요한지를 출력하면 된다. (불가능하면 -1 출력) 연산은 (가장 낮은 지수 + 그 다음으로 낮은 지수*2) 로 계산되며, 사용된 음식은 사라지고 연산에 의해 새로운 음식이 추가된다고 생각하면 된다. 문제 풀이 우선순위큐로 문제를 쉽게 해결할 수 있다.(heap) 이때 우선순위 큐의 사이즈에 주의하자. 원소가 없는데 top(), pop() 연산을 하면 에러가 난다. (한참 헤맸다) 코드 #include #include #include using namespace std; int solution(vector scovil..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/77484 문제 내용 로또 번호와 당첨 번호를 입력받아, 몇 등을 했는지를 파악하는 문제이다. 단, 일부 로또 번호가 지워져있기 때문에, 배열의 로또 최고 순위와 최저 순위를 담아서 return 하면 된다. 문제 풀이 몇 개가 일치하는지 파악한 후에, 최고 순위의 경우 지워진 번호가 모두 일치한다고 가정하고, 최저 순위의 경우 지워진 번호가 모두 불일치한다고 가정하면 된다. 일치하는 개수가 아닌 등수를 반환해야 하므로, 마지막에 처리가 필요하다. 코드 #include #include #include using namespace std; int returnScore(int n){ if(n==0 ||..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12938 문제 내용 n개의 숫자를 더하여 s를 만든다. 이때 해당 n개의 숫자의 곱이 가장 큰 경우를 구하면 된다. 문제 풀이 중복이 허용되기 때문에 그렇게 어렵지는 않다. 모든 값이 중앙에 몰려있어야 곱했을 때 가장 크게 나오기 때문에, s를 n으로 나눈 값을 기본하면 된다. 나머지가 발생한 경우, 크기 만큼 +1을 해주면 된다. 코드 #include #include #include using namespace std; vector solution(int n, int s) { int num=s/n; if(num == 0) return {-1}; vector answer(n, num); for(..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 문제 내용 N개의 송전탑과 이를 연결하는 N-1개의 전선이 있다. 입력으로 주어지는 송전탑들의 관계는, N-1개의 전선으로 모두 이어져있다. 이때, 전선 1개를 끊어서 송전탑을 2 부류로 나눈다. 양측의 탑의 개수의 차를 최소화 했을 때의 차이를 구하면 된다. 문제 풀이 주어진 N-1개의 전선을 한번씩 끊어보면 된다. 끊고 bfs를 돌리면 탑들이 2부류로 나뉘게 된다. 이때의 차를 구하는 것은 어렵지 않다. 코드 #include #include #include #include using namespace std; int divideTowerAndCalcNum(vectorarr[], in..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 문제 내용 table에 놓인 도형들을, 최대한 game_board에 채워 넣어야 한다. 단, 도형은 딱 맞는 곳에만 들어갈 수 있다. (넣었을 때 옆에 공백이 남으면 안 된다.) 도형을 집어넣을 때, 조각을 회전시킬 수는 있지만, 뒤집을 수는 없다. 최대한 많은 조각을 채워 넣었을 때, 몇 칸을 채워 넣은 것인지를 구하면 된다. 문제 풀이 table의 도형이, game_board의 빈칸에 완벽하게 들어가야 하기 때문에, table과 game_board에서 도형과 빈칸을 각각 추출해야 한다. 그리고 해당 도형들을 매칭시켜주면 되는데, 이때 도형을 돌릴 수도 있다. 1. 도형/빈칸 추출 i..

문제 https://school.programmers.co.kr/learn/courses/15009/lessons/121689 문제 내용 손님은 k초마다 카페에 들어온다. 각 메뉴를 만드는 시간을 담은 menu 배열을 입력받고, 카페에 오는 손님이 시키는 주문 내역인 order 배열을 입력받는다. 메뉴는 순서대로 만들어지며, 손님들은 자신의 음료가 나오면 바로 카페를 나간다. 최대 몇 명의 손님이 동시에 카페에 존재했는지를 구하면 된다. (같은 시각에 손님이 들어오고 나가는 경우, 카페에 있던 손님이 먼저 나가고, 그 이후에 새로운 손님이 들어온다.) 문제 풀이 음료 만드는 시간이 길어 여러 명의 손님이 기다리는 경우도 있지만, 음료 만드는 시간이 짧아 카페에 손님이 아무도 없는 경우도 생긴다. (손님은..

문제 https://school.programmers.co.kr/learn/courses/15009/lessons/121688 문제 내용 교육에는 신입사원 2명이 필요하다. 교육 이후에는 서로의 능력을 흡수하여, 두 신입사원의 능력치는 공부 전 두 사람의 능력치의 합이 된다. 신입사원들의 능력치와 총 교육 횟수를 입력받아, 모든 교육 이후에 능력치 합이 최소가 되도록 하고 싶다. (한 번 교육을 받은 사원은, 다시 선발될 수 있다.) 문제 풀이 모든 교육 이후에 능력치의 합이 최소가 되려면, 매 교육마다 능력치가 제일 작은 2명을 골라야 한다. 이를 위해 priority_queue를 사용하여, 매번 가장 작은 능력치를 뽑으면 된다. 코드 #include #include #include using name..

문제 https://school.programmers.co.kr/learn/courses/15009/lessons/121687 문제 내용 명령어 순서를 담은 문자열을 입력받아, 로봇이 해당 명령을 수행한 이후의 좌표를 구하면 된다. 문제 풀이 각각의 명령을 순차적으로 실행하여 이동을 하면 된다. 코드 #include #include using namespace std; int dy[4]={1,0,-1,0}; int dx[4]={0,1,0,-1}; vector solution(string command) { int dir=0; int y=0; int x=0; for(int i=0;i

문제 https://school.programmers.co.kr/learn/courses/15008/lessons/121685?language=cpp 문제 내용 완두콩의 세대와, 해당 세대에서 몇 번째 개체인지를 입력받아, 완두콩의 형질을 출력하면 되는 문제이다. 문제 풀이 가계도를 자세히 살펴보면, 재귀적인 부분을 찾을 수 있다. 완두콩이 자신의 형질을 알기 위해서는 부모의 형질을 알아야 하고, 부모의 형질은 그 윗세대의 형질을 알아야 한다. 코드 #include #include #include using namespace std; string calcBean(int level, int num){ // 몇레벨의 몇번째 개체 if(level == 1){ return "Rr"; }else if(level=..

문제 https://school.programmers.co.kr/learn/courses/15008/lessons/121684?language=cpp 문제 내용 각 학생별로 체육 대회 특정 종목에 나갔을 때의 능력치를 담은 2차원 배열이 주어진다. 종목마다 1명의 학생이 나갈 수 있고, 각 학생은 1개의 종목에만 나갈 수 있다. 능력치의 합이 최대가 되는 경우를 구하면 된다. 문제 풀이 각 종목별로 누가 나갈지를 정해야 한다. 이는 백트래킹으로 쉽게 구할 수 있다. 코드 #include #include using namespace std; vector studentOrder; vector used; int ex_num; int student; int mmax=-1; void decideStudent(in..