알고리즘 문제풀이/프로그래머스
-
[프로그래머스/Level 2] 다음 큰 숫자 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 6. 16:13
programmers.co.kr/learn/courses/30/lessons/12911 코딩테스트 연습 - 다음 큰 숫자 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니 programmers.co.kr 1. n을 2진수로 변경한 후, 1의 개수를 구하는 getCount() 함수 구현 2. 입력받은 n의 getCount()에 넣어 개수를 저장 3. n을 1씩 증가시키면서 1의 개수가 같은 경우를 찾으면 종료하고 n을 리턴 #include #include #include using namespace std; int getCount(int n) {..
-
[프로그래머스/Level 2] 가장 큰 정사각형 찾기 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 5. 17:40
programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr DP를 이용하여 푸는 문제, 정사각형 오른쪽 아래 점이 1이고, 그 점을 기준으로, 왼쪽, 위쪽, 왼쪽 가운데 점의 값이 1 이상이면 길이가 2이상인 정사각형 조건 성립 1. 처음 위치는 (1,1)에서 시작 2. 탐색 하는 점 위치를 기준으로 왼쪽, 위쪽, 왼쪽 대각선의 값 중 최소값에서 +1 (누적하며 계속해서 오른쪽 아래의 점을 갱신) 3. 최대값 = 가장 큰 정사각형의 넓이의 한 변 #include #include using namespace std; int s..
-
[프로그래머스/Level 2] 카펫 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 5. 16:29
programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 처음에 접근했을 때는 가로 세로의 길이가 갈색, 노란색 격자의 합의 약수 관계라는 규칙을 발견했고, 세로가 가로의 길이보다 같거나 작으므로 세로에 격자의 합의 제곱근 길이를 넣은 후, 합에서 세로를 나눠 가로를 구하였다. 그러나 위의 방법같은 경우 노란색 격자가 6개인 경우 문제점이 발생한다. 노란색 격자가 6개일 때, 다음과 같이 카펫이 위치할 수 있기 때문이다. BBB..
-
[프로그래머스/Level 2] 타겟 넘버 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 5. 16:23
programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 전형적인 DFS 문제였습니다. #include #include using namespace std; int answer; void DFS(int L, int sum, vector numbers, int target) { if(L == numbers.size()) { if(sum == target) answer++; retu..
-
[프로그래머스/Level 2] 구명보트 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 5. 02:15
programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 그리디가 세상에서 제일 어렵다. 1. 오름차순 정렬 2. idx가 0번(최소값)을 가리킨다. 3. 최소값과 최대값을 배에 넣어본다. 4. 최소값 + 최대값 = dq.front()) { dq.pop_back(); dq.pop_front(); } else { dq.pop_back(); } answer++; } return answer; }
-
[프로그래머스/Level 2] H-Index (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 4. 22:56
programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 인덱스의 크기가 해당 인덱스의 citations 값보다 크거나 같을 때 해당 인덱스가 H-Index가 된다. 예를들어 [3, 0, 6, 1, 5] 인 경우 내림차순으로 정렬하면 6, 5, 3, 1, 0이 되고, 인덱스 번호를 붙혀보면 0 6 1 5 2 3 3 1 -> 최초로 조건을 만족하므로 인덱스 번호 3이 H-Index 4 0 다른 예시로 ..
-
[프로그래머스/Level 2] 더 맵게 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 4. 21:12
programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 스코빌 지수가 낮은 순서대로 2개씩 리턴을 해야하는데, priority_queue를 이용한 최소 힙을 통해 쉽게 구현할 수 있다. 1. 최소 힙 우선순위 큐에 scoville 벡터의 요소들을 넣어주어 자동으로 오름차순 정렬한다. 2. 우선순위 큐의 맨 앞이 가리키는 값이 K보다 작으면서 동시에 우선순위 큐의 사이즈가 1이 아닐때까지 반복문을 진행한다. (우선순위 ..
-
[프로그래머스/Level 2] 소수 찾기 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 3. 17:03
programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 1. 문자열의 각 요소를 정수로 바꾸어 벡터에 넣어준다. 2. 정렬을 한 후, next_permutation을 이용하여 벡터의 순열을 구한다. (num = num * 10 + v[i] 식을 통해 한자리부터 n자리 까지의 수를 구할 수 있다.) 3. 순열을 통해 만들어지는 수를 set에 저장한다. (중복을 없애기 위해 set을 사용) 4. set의 iterator..