지나공 : 지식을 나누는 공간

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42895 #include #include #include #include using namespace std; //k개의 N을 붙여 만든 하나의 숫자를 반환. int get_basic_number(int N, int cnt){ int res = 0; while(cnt > 0){ cnt--; res += N * pow(10, cnt); } return res; } int solution(int N, int number) { if(N == number) return 1; vector dp(9); for(int k = 1; k 0) dp[k].insert(a-b); dp[k].insert(a*b); if(a/b>0) ..

programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 아악 내 반나절을 앗아간 문제..............너어어어어는 진짜.... 반나절을 앗아갔으므로 풀이를 해야 겠다. 나는 테스트 케이스 2번이 계속 통과가 안됐었는데, 찾아보니 반례가 아래 예제였다, ICN -> A, ICN -> B, B -> ICN 알파벳 순으로 가야 하니까 이걸 정렬해서 ICN 부터 들어가게 되면 ICN -> A로 ..

programmers.co.kr/learn/courses/30/lessons/59044 코딩테스트 연습 - 오랜 기간 보호한 동물(1) ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr -- 아직 입양 못 간 out에 없는 애들 중 가장 오래 보호소에 있던 동물 3마리 SELECT i.name, i.datetime from animal_ins i left outer join animal_outs o on i.animal_id = o.ani..

programmers.co.kr/learn/courses/30/lessons/59042 코딩테스트 연습 - 없어진 기록 찾기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 쉽고 직관적이어서 별 말 없이 코드만 올리려고 한다. #나간 기록은 있고 들어온 기록이 없는 데이터들 찾기 SELECT o.animal_id, o.name from animal_outs o left outer join animal_ins i on o.animal_id..

https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 1. 실패한 첫 번째 풀이 next_permutation을 통해 직접 조합을 만들어서 answer에 개수를 더했지만 조합을 만드는 과정에서 시간 초과가 났다. #include using namespace std; int mix_kind(vectorkinds, int i); int solution(vector clothes) { int answer = 0; vectorkinds; kinds.push_back(make_pair(clothes[0][1], 1)); for (int i = 1; i < clothes.size(); i++) { bool is..

https://programmers.co.kr/learn/courses/30/lessons/42629 코딩테스트 연습 - 라면공장 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니�� programmers.co.kr 우선순위 큐로 max heap을 구현해서 푸는 문제입니다. 이 문제에서 헷갈렸던 점은 공급받은 날짜와 상관없이 공급받은 양을 기준으로 max heap에 넣는 게 맞는지 였어요. 먼저, date를 계산하면서 stock을 하나씩 줄여가되, 해당 date에 공급받은 양을 우선순위 큐에 넣어야 합니다. 그렇게 되면 지금 공급을 받았더라도 이전에 공급받은 양보다 적으면..

문제 출처입니다. https://programmers.co.kr/learn/courses/30/lessons/43237 코딩테스트 연습 - 예산 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그�� programmers.co.kr 구하고자 하는 건 한 지방의 예산 상한액이고, 이 예산의 범위가 1이상 100,000이하인 걸 보면 for문을 돌려 일일이 계산하는 방식이 아니라는 걸 알 수 있습니다. 따라서 효율을 위해 이분탐색을 합니다. 이분탐색 문제는 유형이 거의 비슷해요. 구하고자 하는 것의 범위를 알 때, 이분탐색을 통해 그 값 중 가장 적절한 값이 뭔지 찾는 겁니다...

문제 출처 : https://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 ans; void dfs(vector &numbers, int target, int i, int sum)..

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr dfs로 풀었습니다. 재귀함수, dfs 기본 구현에 충실한 문제였습니다. dfs, bfs에 대해서는 추후에 포스팅을 할 예정입니다. [주석 없는 코드] #include #include #include using namespace std; int ans = 50; bool check[50]; bool diff..

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조�� programmers.co.kr 해시로 푸는 방식과 정렬로 푸는 방식 모두 통과됩니다. 두 코드 모두를 첨부합니다. 하지만 이 문제에서 phone_book의 길이가 1이상 1000000 이하인 것은 문제의도가 시간복잡도라는 걸 알 수 있습니다. 따라서 해시로 푸는 것을 권장합니다. 먼저 정렬 후 벡터로 푸는 코드입니다. 한 번호가 다른 번호 앞부분과 완전히 일치해야 합니다...