본문 바로가기

분류 전체보기209

[프로그래머스 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.
[프로그래머스 lv2] 소수 찾기 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 문자열에 주어진 숫자들로 만들 수 있는 모든 순열과 순열의 부분집합에 대하여 소수인 것의 개수를 리턴하는 문제이다. 먼저, 문자들로 만들 수 있는 모든 수들을 탐색하기 위해 백트래킹(재귀)를 사용한다. 배열에 저장된 인덱스를 숫자로 바꾼 뒤, 해당 수가 소수인지 확인한다. 소수인지 확인할 떄는, isPrime() 함수를 별도로 만들어 일일이 호출하기 보다, 에라토스테네스의 체를 활용하여 한번에 소수를 확인하는 배열을 만들어놓고 O(1)에 처리한다. 아래의 코드에서는 check 배열을 false로 초기화해 놓고, 소수가 아닐 경우와 이미 카운트 했을 경우에 check[i] 값을 true로 변환하였다. 함꼐 참고하면 좋을 포스트 바킹독님의 실전알고리즘-백.. 2022. 8. 12.
[프로그래머스 lv2] 다음 큰 숫자 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 n을 이진수로 변환했을 때 1의 개수를 카운트하여, 같은 1의 개수를 갖는 다음 이진수를 리턴하는 문제이다. n을 이진수로 변환했을 때 1의 개수를 세고, n+1 부터 숫자들을 탐색하며 같은 1의 개수를 갖는 수를 찾는다. 주의 백준의 경우 대부분 문제의 시간 제한이 1초라서, 해당 문제를 1초 내에 돌아가는 다른 풀이로 먼저 제출을 했었다. 그런데 TLE이 남... 고수님께도 질문을 해봤으나, 이 문제의 시간복잡도가 너무 타이트하다는 결론을 내렸다. 혹시 자신의 풀이가 1초(연산 횟수 10^8) 내에 들어오는데 자꾸 시간초과가 난다면 너무 자책하지말고 프로그래머스를 약간 탓해보자.(관계자님 보고 계시나요...!) 코드 #include #include.. 2022. 8. 12.
[프로그래머스 lv2] 주식 가격 풀이 ✅ 프로그래머스의 모든 문제와 해설 보기[클릭] 해설 각 인덱스에 대하여 처음으로 가격이 떨어지는 인덱스를 구해 리턴하는 문제이다. 가장 먼저 이중 for문을 사용한 풀이가 떠오른다. vector solution(vector prices) { vector v(prices.size(), 0); for (int i=0; i 2022. 8. 12.

티스토리툴바