목록Algorithm/문제 (96)

기록공간

위장 (프로그래머스)

옷을 입는 경우의 수를 도출하는데에 애를 많이 먹은 문제였다;; 우선 해시를 이용하여 해당 종류의 맞는 옷의 갯수를 컨테이너에 기록한다. (key값은 옷의 종류 이름, value값은 그 종류의 옷 개수) 옷의 이름은 이 문제를 해결하는데에 전혀 필요가 없다. 옷의 종류별 갯수를 알았으니 이제 이 스파이가 위장할 옷을 입는 경우의 수를 구할 차례이다. 예를들어 얼굴 종류의 옷 5개와 하의 종류의 옷 4개가 있다고 하자. 만약 이 옷을 두가지 모두 입어야 한다면 5 * 4 = 20가지 조합이 나온다. 하지만 옷을 안입는 경우도 있으므로 안입은 경우를 추가해줘야 한다. 그래서 조합 수 는 (5 + 1) * (4 + 1) = 30가지이다. 하지만 30은 정답이 아니다! 위 조건에서 "스파이는 하루에 최소 한 개..
Algorithm/문제 2020. 5. 11. 15:27
전화번호 목록 (프로그래머스)

접두어가 있는지 없는지만 찾으면 되는 문제였다. 우선 phone_book을 순회를 돌며 모든 원소에 대해 비교를 진행한다. 검사가 끝난 원소는 string를 key값으로, string의 사이즈를 value값으로 하는 unordered_map인 d라는 컨테이너에 들어간다. phone_book의 원소는 이 컨테이너 d 안에 있는 원소들과 비교를 한다. 접두어를 찾는 것이므로, 비교하는 값 둘 중 사이즈가 더 작은 값을 기준으로 부분 문자열 비교를 진행한다. 만약 검사하는 부분이 같으면 false를 리턴한다. 코드는 다음과 같다. #include #include #include #include using namespace std; bool solution(vector phone_book) { bool answ..
Algorithm/문제 2020. 5. 11. 12:43
완주하지 못한 선수(프로그래머스)

우선 해결방법은 컨테이너에 마라톤 선수의 이름과 정수형 변수를 보관하는 것이다. 참가한 마라톤 선수를 원소로 집어넣을때 정수형 변수를 1 증가시킨다. 그 작업이 끝나면, 이제 완주한 마라톤 선수를 컨테이너에서 찾아 그 원소의 정수형 변수를 1 감소시킨다. 그리고 컨테이너를 순회돌며 정수형 변수가 0이 아닌 마라톤 선수 이름이 정답이 된다. STL의 컨테이너 형식으로 어떤 것을 쓸건지에 따라서 알고리즘의 시간 복잡도가 바뀌게 된다. 우선 첫번째는 STL의 map 컨테이너를 사용하는 것이다. map 컨테이너는 이진 탐색 트리(binary search tree)의 원리를 이용한 컨테이너로 항상 원소의 키값을 기준으로 정렬된 상태를 유지한다. 트리 검색 특성상 원소의 갯수가 N개 일때 검색 시간 복잡도는 O(l..
Algorithm/문제 2020. 5. 8. 18:25
가장 큰 수(프로그래머스)

정렬 조건을 정하여 정렬하는 문제이다. 위 설명처럼 순열을 모두 구해서 내림차순으로 정렬하는 방법을 생각해 볼 수 있다. 값은 정확하게 나오지만 순열의 개수는 (numbers의 원소의 개수)! (팩토리얼)이기 때문에 원소의 갯수가 많을수록 기하급수적으로 많아진다. 결국 시간 초과가 되므로 이 방법은 쓸 수 없다. (STL에서 제공하는 next_permutation을 사용하면 순열을 쉽게 구할 수 있으므로 한번 시도해보는 것도 나쁘지 않다) 정렬을 내림차순으로 하더라도 [6, 10, 2] 같은 경우 [10, 6, 2]로 1062가 되므로 가장 큰 수를 만족하지 못한다. 하지만 원소들을 string으로 바꾸고 서로의 조합을 통해 비교해서 정렬하면 어떨까? 예를 들어 [6, 10, 2]가 있다면 이를 stri..
Algorithm/문제 2020. 5. 5. 12:42
DNA (백준 - 1969번)

우선 Hamming Distance의 합이 가장 작은 DNA부터 구해야 한다. 입력받은 DNA들에서 각 번째마다 가장 많이 존재하는 뉴클레오티드를 종합하여 조합하면 Hamming Distance의 합이 가장 작은 DNA를 찾을 수 있다. TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 이 DNA를 예로 들어보자. 첫번째에 가장 많이 존재하는 뉴클레이오티드는 T이다. 두번째는 A, 세번째는 A, 네번째는 G, 다섯번째는 A, .... 이렇게 해서 우리가 찾는 DNA의 값은 TAAGATAC가 된다. 하지만 이 DNA가 여러개 존재 할 수 있다는 것에 주목하자. 각 번째에서 즉 존재하는 뉴클레오티드 횟수가 서로 동일할 수 있다는 것이다. 이 경우에는 사전 순으로 했을때 가장 처..
Algorithm/문제 2020. 3. 29. 01:00
멀티탭 스케줄링 (백준 - 1700번)

그리디 알고리즘으로 푸는 문제이다. 플러그가 꽂혀있지 않을 경우 사용하는 전기용품 순으로 꽂는다. 이미 플러그에 꽂혀있는 전기용품은 꽂는 작업을 할 필요가 없다. 만약 플러그를 빼야 하는 경우(즉, 멀티탭에 플러그가 모두 사용중인 경우) 가장 나중에 쓰이거나 쓰이지 않을 전기용품의 플러그를 빼야 빼는 횟수를 최소화 할 수 있다. 정리해보면 다음과 같다. 전기용품 사용 순서대로 빈 플러그에 꽂는다. 플러그가 모두 사용 중이며 현재 사용할 전기용품이 플러그에 꽂혀있지 않는 경우 꽂혀있는 플러그 중 가장 나중에 쓰이거나 더이상 쓰이지 않을 전기용품 플러그를 뺀다. 멀티탭에 모든 플러그가 꽂혀있는 경우 N개의 사용순서에서 i번째에 있는 다른 전기용품을 사용해야 한다고 가정하자. 꽂혀있는 전기용품들을 순회돌며 i..
Algorithm/문제 2020. 3. 29. 00:59
수리공 항승 (백준 - 1449번)

그리디 알고리즘을 사용하는 문제였다. 우선 물이 새는 곳의 위치를 입력받으면 그 정보를 정렬한다. 그 다음 처음 물이 새는 곳의 위치를 기록한다.(start값) 물이 새는 곳이 하나라도 있으면 테이프를 한 개는 써야 하므로 테이프의 갯수를 기록할때는 1부터 시작한다. 테이프를 최소로 쓰기 위해서 어떻게 해야 하는지 살펴보자. 물이 새는 위치를 순회하며 start에서 물이 새는 위치까지의 길이가 테이프의 길이 - 1(좌우 0.5만큼 간격을 줘야 하므로) 보다 큰 경우 이미 테이프의 길이를 넘어 갔으므로 start부분만 막고 새로운 테이프로 현재 위치를 막아야 한다. 그리고 start값을 현재 위치의 값으로 갱신한다. 모든 위치를 방문했을때 테이프의 갯수가 우리가 원하는 값이 된다. 코드는 다음과 같다. #..
Algorithm/문제 2020. 3. 29. 00:58
저울 (백준 - 2437번)

우선 입력받은 추의 무게를 오름차순으로 정렬해야 한다. 정렬된 상태에서 맨 처음 추의 무게가 1이 아닌 경우에 측정할 수 없는 최소 무게는 1이다. 만약 맨 처음 추의 무게가 1인 경우 1을 시작으로 두번째 추부터 마지막 추까지 무게를 차례대로 더해주도록 한다. 무게가 적은 추부터 차례대로 더하는 sum이라는 값이 있다고 하자. 차례대로 sum에 추의 무게를 더해주는 도중에 sum + 1이면서 sum + 1값이 입력받은 어떤 추에도 존재하지 않는 값이라면 그것은 측정할 수 없는 최소 무게가 될것이다. 코드는 다음과 같다. #include #include #include using namespace std; int main() { int N; cin >> N; vector sinkers; for (int ..
Algorithm/문제 2020. 3. 29. 00:58
Prev 1 ··· 5 6 7 8 9 10 11 12 Next