본문 바로가기

Algorithm

 (2139)
(C++) - 프로그래머스(연습문제) : 야근 지수 답 programmers.co.kr/learn/courses/30/lessons/12927?language=cpp 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr priority queue를 이용해 풀었습니다. 풀이방법 1. 작업시간들을 모두 max heap priority queue에 넣어줍니다. 2. n만큼 pq.top()은 항상 그 다음 최대의 작업시간이므로 해당 값이 양수일때 1씩 빼준 후 pop하고 1줄어든 값을 다시 push 해줍니다. 3. pq에 있는 원소를 모두 빼주면서 야근 지수를 ..
(C++) - 프로그래머스(고득점 kit - 스택/큐) : 주식가격 답 programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr stack을 이용한 문제였습니다. 풀이방법 두 인덱스 사이의 차이는 초로 환산될 수 있습니다. 예를 들어 0번 인덱스의 price와 1번 인덱스의 price는 1초의 차이가 있습니다. 이를 이용해 stack에 price의 인덱스를 넣는 방식을 사용했습니다. 1. price[stack.top()] > price[i] 인동안 즉 가격이 떨어졌다면 answer[stack.t..
(C++) - 프로그래머스(월간 코드 챌린지 시즌 1) : 삼각 달팽이 답 programmers.co.kr/learn/courses/30/lessons/68645?language=cpp 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr 재귀 또는 일반적인 구현으로 풀 수 있는 문제였습니다. 풀이방법 1. 먼저 삼각형을 적절히 변형해 생각합니다. 정삼각형이 아닌 직각삼각형이라고 생각하면 인덱싱이 편합니다. 2. 다음과 같은 높이가 n인 직각삼각형을 만들기 위해서는 3가지 방향으로 수를 채워야 합니다. 2-1. (1)번 방향 : 아래로 수직하강합니다. 2-2. (2)번 방향 : 우측으로 평행하게..
(C++) - 백준(BOJ) 2346번 : 풍선 터뜨리기 답 www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net deque을 이용하면 쉽게 풀 수 있는 문제였습니다. 풀이방법 풍선을 터뜨렸을 때 만약 움직이려는 숫자가 양수라면 먼저 터뜨리고 움직인다는 점을 고려해 1을 뺀 만큼 이동시킵니다. 음수라면 해당값에 음수를 취한 값만큼 이동시키면 됩니다. Code #include using namespace std; int n; int moveBalloon[1001]; deque balloon; vector ans; int main(){ cin >> n; f..
(C++) - 백준(BOJ) 1068번 : 트리 답 www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리를 만들고 dfs를 시행하는 문제였습니다. 풀이방법 1. tree를 생성합니다. 자식이 여러개일 경우를 대비해 자식이 추가될 때마다 vector push_back()을 이용합니다. 2. root node부터 dfs를 시행합니다. 지울 노드를 방문처리하게 되면 그 이하 자식들도 dfs를 하지않게 가능합니다. 2-1. 자식노드가 존재한다면 그 자식노드를 다음 dfs 호출의 인자로 넘겨줍니다. 2-2. 자식..
(C++) - 백준(BOJ) 14889번 : 스타트와 링크 답 www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net backtracking을 이용한 문제였습니다. 풀이방법 1. backtracking을 이용해 n/2인원을 뽑습니다. 이 때 뽑히지 않은 인원을 상대편 팀으로 생각하면 됩니다. 2. n/2인원을 뽑았다면 시너지를 계산합니다. Code #include using namespace std; int n; int team[20][20]; int check[20]; int ans = 0x7f7f7f7f; int getSynergy(vector..
(C++) - 백준(BOJ) 2304번 : 창고 다각형 답 www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 풀이 및 구현방법을 생각하기 어려웠던 brute force문제였습니다. 풀이방법 빛을 왼편에서 쬐었을 때와 오른편에서 쬐었을 때 빛이 부딪힌 후 그림자와 빛이 비춰지는 모습이 어떻게 구성이 되는가에 대한 생각에서 착안했습니다. 1. 1번으로 빛을 쪼였다고 가정해봅시다. 이 때 가장 긴 가운데 (높이가 10짜리) 봉은 갈색 빛이 그 오른편 기둥들의 꼭대기를 비출 수 없도록 하고 있습니다. 2. 2..
(C++) - 백준(BOJ) 2776번 : 암기왕 답 www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 입출력이 많기 때문에 c의 헤드들과 동기화를 끊어줘야 합니다. 그 후 이분탐색하시면 됩니다. 풀이방법 찾았다면 flag = 1로 만들어주고 찾기 못했다면 flag가 초기값 그대로인 0이므로 이분탐색 시행 후 flag를 return 해주면 됩니다. Code #include #define fastio ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); using namesp..

티스토리툴바