본문 바로가기

알고리즘106

[프로그래머스 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] 최댓값과 최솟값 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 공백으로 구분된 숫자들 중 최솟값과 최댓값을 구하는 문제이다. 우리는 숫자 값을 비교하고 싶은데, 숫자들이 문자열 안에 파묻혀 있으므로 이를 숫자로 파싱하는 작업을 먼저 해주어야 한다. 문자열을 공백 기준으로 쪼개는 함수를 흔히 split() 함수라 하는데, c++에는 내장 split이 없으므로(python에는 있음) 직접 구현해보자. 문자열을 순회하면서 공백이 나올 때마다 단어들을 추출하여 vector에 넣어준다. 문자열 안에 있는 숫자들을 하나씩 split 한 후에는 각각의 숫자들을 순회하면서 최댓값과 최솟값을 구하면 정답이다. 코드 #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.

티스토리툴바