문제 링크 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 카메라 위치는 차량의 진입 시점으로 하되, 1. 카메라 위치를 갱신(카메라 개수 일정) 2. 카메라 개수 추가(카메라 개수 증가) 이렇게 나누었고, 카메라 개수를 추가하는 것에 대한 임계값을 차량의 나간 시점으로 하였다. (반복문을 돌면서 카메라를 최소 개수로 설치해야 하므로) // init 나간 시점으로 오름차순 정렬 --- 나간 시점(임계값)이 작은 것부터 비교해야 하므로 임계값 -30001로 초기화(차량 진입 시점은 -30000 이상이므로) --- 반복문을 0부터 돌면서 처음에 카메라 개수를 추가하기 위함 // process 반복문(모든 차량에 ..
문제 링크 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이 "처음에 어떻게 태우지?" 하다가 구명보트는 2명이 제한이라는 것을 발견하고 바로 풀었다. deque을 이용하여 pop_front()와 pop_back()을 유용하게 쓰며 진행 대신, 처음에 정렬에 대해서는 vector로 정렬하고 역방향 반복자를 이용해 내림차순으로 정렬하였다. (deque은 조회에 대해서는 느리다구 한다, 대신 앞, 뒤로 pop이나 push가 용이하다) // init 1. people 벡터 컨테이너를 ..
문제 링크 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 풀이 두 가지의 부분해가 존재한다. 1. 상, 하 커서를, 바뀔 알파벳이 디폴트 'A'에서 최소로 조작한다. 2. 좌, 우 커서를, 디폴트 'A'가 아닌 곳과의 거리가 최소로 조작한다. deque을 사용하여 pop_front()와 pop_back()을 사용하였다. // init 방향 결정을 위해서 'A'가 아닌 인덱스만 deque에 push dq가 빌 때까지 { 우 커서로 움직일 경우 거리(right)와 좌 커서로 움직일 경우 거리..
문제 링크 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 첫 번째 풀이로, 완전탐색으로 풀리나 해봤지만 역시나 시간초과가 걸렸다. 그리고 두 번째 풀이로, 최댓값을 골라서 같은지 비교했으나 테스트케이스 10번에서 시간이 초과된다. 세 번째 풀이는 제거할 개수 범위 내에 가장 앞 숫자보다 큰 숫자가 있는지 검사하는 방법이다. 예를 들어, 현재 인덱스는 5라면, 제거할 개수가 4개라면 [5]가 [6] ~ [9]까지 비교했을 때, 가장 큰 값인지 검사하면 된다. [6]~[9]까지 max_element로 찾았더니 테스트케이스 10번에서 시간이 초과된다. 중간에 찾으면 break; 로 시간을 줄여야 통과할 수 있다. 여기서, 반복문의 탈출 조건은 1. 제거할 개수가 0일 때 2. 제거할 ..
문제 링크 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 전형적인 크루스칼 + 유니온파인드 문제다. 최소신장트리(MST)를 만들고 간선에 대해서 모든 비용을 합한다. // cmp 함수 크루스칼 알고리즘을 이용하기 위해 간선(비용)에 대해서 오름차순 정렬한다. // find_root 함수 root 찾는 함수다. 1) root가 지금 나라면 바로 리턴 2) 아니면 나의 부모로 재귀로 호출 // solution 함수 map을 이용해 연결됨을 이용했다(어차피 정점에 대해서 중복하지 않으므로) 1) init - 각 정점은 자신을 루트로 지정 2) MST가 만들어질 때까지 반복문을 돌린다(MST는 간선의 수와 ..