목록Algorithm (35)
지나공 : 지식을 나누는 공간
c언어에서는 보통 strcmp를 이용해서 문자열 두 개를 비교하지만, c++에서는 어떤 string내에서 원하는 string이 존재하는 지, 그 위치를 반환하는 함수를 사용할 수 있다. find() 함수이다.
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..
BFS로 풀었고, 난이도는 그렇게 어렵지 않지만 문제 풀이 절차를 잘 파악해야 하는 문제라고 생각합니다. 문제출처 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 저는 함수를 사용해서 복잡한 풀이 절차를 나눴습니다. 전체적인 풀이 방식 처음 입력 받은 배열(origin)을 다른 배열(map)에 복사하고, map에서 매번 다른 위치에 3개의 벽을 설치한 뒤 바이러스를 퍼뜨려 보면서 안전지대 크기를 비교합니다. 1. 맨 처음 배열을 origin에 저장하고 0..
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/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 문제가 매우 길어요. 여기서 문제 푸는 데 중요한 내용만 뽑으면 아래와 같습니다. (니니즈 친구들이 사람은 아니지만 편의를 위해 사람 수라고 표현했습니다. ㅎㅎ) 징검다리를 누군가 건널 때마다 해당 다리의 원소가 1 감소하고 0이 되면 건널 수 없으므로 징검다리의 각 원소 값은 그 다리를 건널 수 있는 사람의 수와 관련 있음 (매우 중요한 포인트입니다.) 우리는 결국 건널 수 있는 사람 수를 구하고 싶은 거고, stones 배열의 원소 값이 각각 1이상 200,00..
문제 출처입니다. 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 이하인 것은 문제의도가 시간복잡도라는 걸 알 수 있습니다. 따라서 해시로 푸는 것을 권장합니다. 먼저 정렬 후 벡터로 푸는 코드입니다. 한 번호가 다른 번호 앞부분과 완전히 일치해야 합니다...
문제출처 : https://programmers.co.kr/learn/courses/30/lessons/42576 순서가 상관이 없으므로 unordered_map을 사용하였습니다. unordered_map은 비정렬 연관컨테이너로, 중복을 허용하지 않고 map과 달리 key를 기준으로 자동정렬하지 않습니다. unordered_map과 map, hash_map 등의 개념을 다른 포스팅으로 정리했습니다. 맨 아래에 첨부한 링크를 참고해 주세요. 이제 문제를 살펴볼게요. 마라톤 경기에 참여한 선수의 수인 participant가 있고, 그보다 1 작은 크기의 completion 벡터에는 완주한 선수가 담겨있으니, 완주하지 못한 선수는 전체에서 1명입니다. 여기서 포인트는 '마라톤 경기에 참여한 선수의 수는 1명 ..