본문 바로가기

프로그래머스lv263

[프로그래머스 lv2] H-index 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 문제에는 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index 라고 나와있지만, 이걸 그대로 해석해서 풀면 삽질하기 쉽다. 문제에 나와있는 H-index 정의 대신 아래 글을 참고하자. [연구논문을 위한 핵심 10단계] H-지수(H-Index) 란 무엇인가? 일반적으로 특정 연구원의 연구성과를 평가하기 위해 얼마나 많은 논문을 발표 하였는지를 보게됩니다. 그러나 단순히 발표한 논문 수로만 그 연구원의 연구 업적을 평가 하기에는 발표한 논문 www.ibric.org 요약하면, H-index는 논문 인용 수를 내림차순으로 나열한후, 논문의 인용 수가 논문 수보다 클 때.. 2022. 8. 16.
[프로그래머스 lv2] 가장 큰 수 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 주어진 수들을 연결하여 만들 수 있는 가장 큰 수를 문자열로 리턴하는 문제이다. numbers를 올바른 방법으로 정렬 할 수 있다면, 정렬 된 수들을 모두 연결하여 리턴하면 된다. 그런데, 정렬 기준을 세우는게 생각보다 까다롭다. 각 자릿수를 비교하다가 큰 수가 더 앞에 나와야 하는 건 알겠는데, 3과 30을 보면, 330이 303보다 크므로, 무조건 크다고 해서 앞에 오는 건 아니다. 두 수를 비교할 때 무엇이 앞에 와야하는지 조금 더 간단하게 판단할 수는 없을까? 두 문자열(수) a, b가 있을 때, 두 수를 합친 결과는 a+b나 b+a 이다. 만약 a+b > b+a 라면 a가 앞에 오면 되고, a+b < b+a 라면 b가 앞에 오면 된다. 정렬 .. 2022. 8. 16.
[프로그래머스 lv2] 카펫 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 brown 카펫은 yellow 카펫들을 둘러싸고 있는 '한 층의' 테두리이다. 따라서 brown 카펫 수를 통해 가로와 세로 길이 합(s)을 구할 수 있다. 가로의 길이가 a, 세로의 길이가 b, s = a+b라 하자. 전체 테두리 길이 brown은 a*2 + (b-2)*2 이므로, 2*a+2*b-4 = brown 2*(a+b) = brown+4 a+b = (brown+4)/2 s = (brown+4)/2 가 된다. 가로와 세로 길이의 합을 알고 있으므로, 가로의 길이를 결정하면 세로의 길이를 바로 구할 수 있다. 가로는 세로보다 길어야 하므로, 가로는 (s+1)/2 (s를 2로 나눈 몫의 올림) 이상이어야 한다. 가로는 최소 세로 길이를 남겨야 하는.. 2022. 8. 15.
[프로그래머스 lv2] 이진 변환 반복하기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 s가 1이 되기 전까지 이진 변환을 반복하면서 반복횟수와 0의 제거 횟수를 카운트하는 문제이다. 간단하게 생각하면, 이진 변환은 결국 s에 있는 1을 개수를 세어 해당 수를 이진수로 나타내는 것이다. s를 순환하며 1의 개수를 카운트하고, 0이 될 때까지 2로 나누어 이진 변환을 수행한다. 이진수의 총 길이에서 1의 개수를 뺀 값이 곧 제거된 0의 개수이므로 이를 기록하여 추후에 제거된 총 0의 개수를 함께 리턴할 수 있도록 한다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #inc.. 2022. 8. 14.
[프로그래머스 lv2] 행렬의 곱셈 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 행렬의 곱셈 결과는 다음과 같다. 행렬 A의 크기가 l * m, 행렬 B의 크기가 m * n 라 할 때, 행렬 A * B 의 크기는 l * n 가 된다. 행렬 A*B의 i행, j열 원소(AB[i][j])는 행렬 A의 i행과 행렬 B의 j열의 원소들을 각각 곱하여 모두 더한 값이 된다. 예를 들어, 행렬 A의 0번째 행이 [1, 4] 이고 행렬 B의 0번째 열이 [3, 3] 일 때, AB[0][0] = 1*3 + 4*3 = 15가 된다. 크기가 l * m 인 새로운 행렬 AB에 대하여 모든 원소의 값을 구해주면 정답이다. 코드 #include #include #include #include #include #include #include #include.. 2022. 8. 14.
[프로그래머스 lv2] JadenCase 문자열 만들기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 문자열을 이루는 모든 단어들에 대하여 첫글자는 대문자로, 나머지 글자는 소문자로 변경하는 문제이다. 첫글자는 toupper(), 나머지 글자들은 tolower() 함수로 변경하면 정답이다. 참고 하면 좋을 것 toupper()는 소문자를 대문자로 변경하는 함수, tolower()는 대문자를 소문자로 변경하는 함수로 헤더파일 내에 있다. 영어 문자가 아닌 다른 문자에 대해서는 원래 문자를 그대로 반환한다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using names.. 2022. 8. 14.
[프로그래머스 lv2] N개의 최소공배수 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 n개의 수에 대하여 최소공배수를 구하는 문제이다. 두 수 A, B의 최소공배수(lcm)을 구하는 공식은 다음과 같다. lcm = A * B / gcd(A, B) (gcd는 A, B의 최대공약수) 모든 수의 최소공배수를 구해야 하므로 이전 수의 최소공배수 결과와 다음 수의 최소공배수를 구해나가면 된다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ii = pair; using iii = tuple; #define X fir.. 2022. 8. 13.
[프로그래머스 lv2] 모음사전 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 주어진 문자 A, E, I, O, U를 사전순으로 나열했을 때, 문자열 words가 몇 번째 단어인지 구하는 문제이다. 중복을 허용하여 최대 5글자까지 나열하면 되므로 모든 경우의 수를 탐색하여도 시간초과가 발생하지 않는다. 중복 순열은 백트래킹(재귀)를 활용하면 쉽게 구현할 수 있다. 아래의 코드에서 func(k)는 k번째 자리를 채우는 함수로, 각각의 자리를 채울 때마다 cnt를 1 증가시키고 문자열이 word와 같을 때 cnt를 기록하여 리턴한다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include u.. 2022. 8. 13.
[프로그래머스 lv2] 피로도 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 던전을 탐험하는 순서에 따라 최대로 이동할 수 있는 던전의 수가 달라진다. 던전을 탐험하는 모든 경우의 수에 대하여 이동할 수 있는 던전 수를 확인하고 이들 중 최댓값을 리턴하면 정답이다. 재귀를 이용해 모든 경우의 수를 확인할 수도 있지만, next_permutation() 함수를 활용하면 모든 던전 순서쌍을 간단히 확인할 수 있다. 각 던전 순서쌍에 대하여 남아있는 피로도가 최소 피로도보다 크거나 같을 때까지 cnt를 증가시키고, 계산된 cnt 값 중 최댓값을 리턴한다. 코드 #include #include #include #include #include #include #include #include #include #include #includ.. 2022. 8. 13.
[프로그래머스 lv2] 소수 찾기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 문자열에 주어진 숫자들로 만들 수 있는 모든 순열과 순열의 부분집합에 대하여 소수인 것의 개수를 리턴하는 문제이다. 먼저, 문자들로 만들 수 있는 모든 수들을 탐색하기 위해 백트래킹(재귀)를 사용한다. 배열에 저장된 인덱스를 숫자로 바꾼 뒤, 해당 수가 소수인지 확인한다. 소수인지 확인할 떄는, isPrime() 함수를 별도로 만들어 일일이 호출하기 보다, 에라토스테네스의 체를 활용하여 한번에 소수를 확인하는 배열을 만들어놓고 O(1)에 처리한다. 아래의 코드에서는 check 배열을 false로 초기화해 놓고, 소수가 아닐 경우와 이미 카운트 했을 경우에 check[i] 값을 true로 변환하였다. 함꼐 참고하면 좋을 포스트 바킹독님의 실전알고리즘-백.. 2022. 8. 12.

티스토리툴바