1. 문제 코딩테스트 연습 - 단속카메라 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 2. greedy 이 문제는 set 문제로 생각할 수 있다. 겹치는 부분이 생기면 한 set에 있다고 생각하는 것이다. 단 이때 set을 형성하는 순서가 중요하다. (그리디 => 제일 가까운 것이랑 set형성) lo 기준 hi기준 으로 적당히 순차적으로 set을 형성하면 된다. set(lo, hi) = lo ~ hi 인 범위를 포함하고 있는 원소들의 집합 이렇게 함수를 표현하고 나면 이제 set의 size를 리턴하게 하면 문제는 해결된다. 이때 set 자료구조는 오버라이딩된 ..

1. 문제 코딩테스트 연습 - 섬 연결하기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 2. Prim 알고리즘 prim 알고리즘은 그리디적으로 mst를 찾는 알고리즘이다. 따라서 이 문제에서 주어지는 입력을 인접 그래프 형태로 나타내고 우선순위 큐를 활용한 프림 알고리즘을 사용하면 문제는 해결된다. 프림 알고리즘말고도 크루스칼 알고리즘을 사용할 수 있으며, 이때 따로 정렬과, 유니온 파인드 자료구조를 사용해야한다, 하지만 이 경우 따로 그래프를 재구성할 필요가 없다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ..

1. 문제 코딩테스트 연습 - 여행경로 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 2. dfs 이 문제는 신경써야할 두가지 작은 문제가 있다 이를 map 자료구조를 활용하여 쉽게 해결하였다. 이 map을 모든 정점과 간선을 탐색하는 dfs돌리면 문제는 해결된다. - 모든 티켓을 사용 이 문제는 dfs의 일반적인 목적인 정점을 탐색하는 것과 는 다르게 모든 간선을 지나야하는것이다. 따라서 방문을 기록하는것을 정점이 아니라..

1. 문제 코딩테스트 연습 - 도둑질 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 2. dp - recursive 이 문제를 해결하려면 두 패턴을 비교해야한다. 첫 패턴은 0 에서부터 반복되는 패턴 두번째 패턴은 1에서부터 반복되는 패턴 두가지 패턴은 두 상황이 생긴다 현재 인덱스를 포함할 것인지 포함하지 않을 것인지 그리고 포함할 경우 다음 인덱스가 이전에 포함되어있으면 안된다 (순환할 경우 이런 경우가 생긴다. 이 경우는 첫 패턴에서만 생긴다) 이를 재..

1. 문제 코딩테스트 연습 - 프린터 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 2. priority queue 우선순위 큐를 만들고 대기목록의 인덱스를 증가시키면서 우선순위 큐랑 비교하며 top이랑 같지 않으면 대기 목록의 제일 뒤로 보낸다. 같으면 우선순위 큐를 pop한다. 그리고 만약 location == idx 일 경우 location을 새위치로 업데이트 시켜준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19..

1. 문제 코딩테스트 연습 - 베스트앨범 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 2. map 3개의 map으로 문제를 해결할 수 있다. 1. 장르 -> 해당 장르 노래의 모든 플레이 횟수 2. 장르 -> 해당 장르에서 플레이 횟수 가 가장 많은 두개의 노래 인덱스 3. 1 번을 뒤집은 map 장르 중에서 가장 큰 것을 먼저 선택해야하므로 1번 map에서 3번 map 으로의 변환이 필요하다. 그 장르 속에서 가장 큰것 두개를 선택해야하므로 2번 ma..