바야바네 움집

깔깔 📌문제 https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 📌풀이 '옷의 종류'를 key 값으로 하는 map을 생성해서 풀면 된다. vector의 처음부터 끝까지 탐색하면서 동일한 옷의 종류가 나올 때마다 map[옷의 종류] 값을 1씩 더해주면 끝! 개수 세기가 끝나면 언젠가 배웠던 경우의 수를 잘 떠올려서 계산하면 된다. 스파이는 1개 이상의 옷을 입는다고 했으니 (가능한 모든 경우의 수) - (아무 것도 입지 않았을 경우) 가 정답임. 📌코드 int solution(vector clothes) { int answer = 1; unordered_map map; for(int i=0; i

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들어있지 않습니다. < ..

📌풀이 에라토스테네스의 체를 사용해 푸는 문제인 것 같다. 에라토스테네스의 체는 아래와 같은 방식으로 진행된다. 가장 작은 소수인 2부터 자신의 배수들을 지워나가면서 소수를 찾아낸다. 📌코드 #include #include int main() { int input = -1, minus = 0; bool prime[1000000]; for(int i=2; i

📌풀이 기본 접근 : 2부터 N-1까지의 수로 주어진 수를 나눔으로서 소수인지 아닌지 판별. 에라토스테네스의 접근 : 제곱근을 사용해 주어진 수가 소수인지 아닌지를 판별. 에로토스테네스의 체 : 2부터 제곱근N까지 나눔으로주어진 수까지의 모든 소수를 구함. 멋들어지게 에라토스테네스의 접근을 사용해보고자 했지만 때려치웠다. 기본 접근으로 풀었음. 참고 : https://jongmin92.github.io/2017/11/05/Algorithm/Concept/prime/ 소수 구하기 (에라토스테네스의 체) 소수(Prime Number)는 약수로 1과 자기 자신만을 가지는 정수입니다. 정수론의 기본 정리에 의해 모든 자연수는 단 하나의 소수들의 곱으로 표현됩니다. 소수 구하는 알고리즘1. 기본적인 접근소수 jo..

📌풀이 입력된 값들의 모든 gcd 쌍을 구하면 되는 문제. 10번 정도 틀렸는데 그 이유는 자료형 문제 때문이었음. 변수 자료형 뿐만 아니라 서식지정자 또한 lld로 변경해주어야 함. 📌코드 #include long long GCD(long long D, long long B); int main(){ int testCase, count; long long valueArr[1000], sumArr[5000] = {0}; scanf("%d", &testCase); for(int i=0; i

📌코드 #include int GCD(int D, int B); int main() { int arr[1000]; int testCase, count; int a, b; scanf("%d", &testCase); count = testCase; while(testCase){ scanf("%d %d", &a, &b); arr[testCase-1] = a*b / GCD(a, b); testCase--; } for(int i=count-1; i>-1; i--) printf("%d\n", arr[i]); return 0; } int GCD(int D, int B) { int R; R = D % B; //D = B * (D/B) + R; if(R!=0) GCD(B, R); else return B; }

최대공약수와 최소공배수 구하는 법을 까먹었다. 초등학교부터 다시 다녀야할 것 같다. 📌최대공약수와 최소공배수 구하는 방법 1. 소인수분해 두 수를 소인수분해를 한다. 두 수의 공통된 소인수를 모두 곱하면 최대공약수, 두 수의 모든 소인수를 곱하면 최소공배수가 된다. 2. 유클리드 호제법 A와 B의 최대공약수를 구하기 위해서 A를 B로 나눈 나머지 R1을 구한다. B를 R1으로 나눈 나머지 R2를 구한다. R1을 R2로 나눈 나머지 R3를 구한다 이 과정을 계속 반복하여, 어느 한 쪽이 나누어떨어질 때까지 반복한다. 이 직전 얻은 나머지가 최대공약수. 예시로 1254와 582의 최대공약수를 구해보자. 1254=582×2+901254=582×2+90 582=90×6+42582=90×6+42 90=42×2+6..