lv38 [Programmers] 단속카메라 문제 : https://programmers.co.kr/learn/courses/30/lessons/42884 그리디로 풀었다. 먼저 루트들을 시작위치를 기준으로 오름차순정렬한다. 변수를 만들어서 커버가능한 시작위치 종료위치(let, cover)를 저장한다. 루트들을 처음부터 탐색하면서 탐색 중인 루트(let, route)가 이전 가능한 카메라 위치로 커버가능한지 체크한다. 만약 route.시작위치 > cover.종료위치 이거나 route.종료위치 < cover.시작위치 라면 범위가 커버가 불가능하므로 카메라를 한 대 더 설치해야한다. 카메라 대수를 한 대 증가시키고 cover 변수를 현재 route 범위로 갱신한다. 이전 카메라로 커버가 가능하다면 현재 route 범위와 cover 범위의 교집합으로 c.. 2021. 6. 16. [Programmers] 섬 연결하기 문제 : https://programmers.co.kr/learn/courses/30/lessons/42861 오랜만에 푸는 최소신장트리문제~ 크루스칼 알고리즘으로 풀었다. 먼저 cost 오름차순으로 costs 배열을 정렬한다. costs 배열을 탐색하면서 Union-Find로 해당 간선을 연결하면 사이클이 생기는지 확인한다. 만일 두 정점의 부모노드가 같다면 연결하면 사이클이 생기기 때문에 해당 간선을 선택하지 않는다. 두 정점의 부모노드가 다르면 해당 간선을 연결해도 사이클이 생기지 않기 때문에 해당 간선을 선택하고 해당 간선의 비용을 정답에 더해준다. 시간복잡도는 간선들을 오름차순 정렬하는데 드는 시간인 O(ElogE) 소스코드 : https://github.com/fpdjsns/Algorithm/.. 2021. 6. 14. [Programmers][2020 카카오 인턴십] 보석 쇼핑 문제 : https://programmers.co.kr/learn/courses/30/lessons/67258 투포인터로 풀었다. gems를 돌면서 보석 종류 수를 구한다. 보석의 개수를 저장하는 cnts map을 하나 만든다. key = 보석이름, value = 보석 수. 그리고 탐색하면서 만난 보석들의 종류를 저장하는 set을 하나만든다. (let, exists) 투포인터의 오른쪽 인덱스(right)를 0부터 1씩 증가시키며 left 인덱스를 갱신한다. 탐색중인 보석의 수를 cnts 맵에 1더해서 갱신시킨다. exists set에 탐색한 보석을 추가한다. 정답가능한 배열의 크기를 최소화로 만들기 위해 left인덱스를 갱신한다. 만일 gems[left] 에 해당하는 보석의 개수(cnts 참고)가 1보다.. 2021. 6. 13. [Programmers] 디스크 컨트롤러 문제 : https://programmers.co.kr/learn/courses/30/lessons/42627 먼저 시작시간이 가장 빠르고, 시작시간이 같다면 소요시간이 적은 순으로 jobs를 정렬한다. 마지막 작업이 종료된 시간(let, 종료시간)을 저장하는 변수를 하나 만들고 0으로 초기화시킨다. 가장 먼저 시작되는건 jobs의 첫번째 요소일 것이다. 작업 소요시간이 적은 순으로 정렬되는 최소힙을 하나만들어서 가장 먼저 시작되는 jobs의첫번째 요소를 큐에 넣는다. 이제 최소힙 빌때까지 잡들의 최소 소요시간을 구해서 sum 변수에 더해나간다. 최소힙의 첫번째 요소를 꺼내서 job의 실제 시작시간을 구한다. 만일 이전 잡의 종료시간이 현재 job의 시작시간보다 작거나 같으면 현재 job의 시작시간이 실.. 2021. 6. 11. [Programmers] 순위 문제 : https://programmers.co.kr/learn/courses/30/lessons/49191 A가 B를 이겼는데 B가 C를 이겼다면 A가 C를 이긴것과 같다. 어디선가 많이 본 것 같은.. A에서 B로 가는 최단거리가 x1이고, B에서 C로 가는 최단거리가 x2라면 A에서 C로 가는 거리의 최단거리 중 하나가 x1 + x2 일 수 있다. 플로이드 워셜 알고리즘의 기본 이론이다. 알고리즘이론 글을 안쓴지 오래되었는데 다익스트라랑 벨만포드는 포스팅했는데 플로이드는 없네. 그렇지만 최단거리 알고리즘 중에 제일 좋아하는 알고리즘이다. (구현이 간단해서 ㅎㅎ) 플로이드 워셜을 돌려서 승부결과를 nxn 크기의 matches 배열에 채운다. matches[A][B] = A가 B를 이겼으면 true... 2021. 6. 11. [Programmers] 입국심사 문제 : https://programmers.co.kr/learn/courses/30/lessons/43238 문제 풀기전에 문제 분류를 봐버렸다.. 이분탐색 문제를 풀고싶었다기 보다는 레벨3 문제를 풀고싶었던건데 문제분류가 너무 잘보여버림. 이분탐색이란걸 알았으니 어떻게 이분탐색으로 해야하는지 분석해보자. 입국심사를 기다리는 사람은 최대 10억명. 한 명의 심사관이 걸리는 시간은 최대 10억분. 심사관의 수는 최대 10만. 이분탐색은 내부 조건이 정답이 가능한지 안한지를 판단할 수 있어야한다. 그럼 주어진 조건을 어떻게 정답이 되는지 안되는지 알 수 있을까. m분안에 모든 심사원이 최소 n명을 처리할 수 있다면 m분이 정답이 될 수 있다. 모든 심사원이 처리할 수 있는 시간 = 각 심사원들이 m분안에 .. 2021. 6. 10. 이전 1 2 다음