[프로그래머스] 단속카메라(Java, Greedy, 사고력, Lv3)
programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr ## 접근방법 그리디 문제는 항상 코드는 단순하지만, 생각해내기가 쉽지 않다. 이 문제는 최소의 단속카메라를 통해서, 모든 운전자들을 단속할 수 있어야 한다. 어떤 운전자부터 카메라를 배치해야할까? 단속이 안된 운전자중에서, 가장 도착 거리가 작은 운전자를 확인해야 한다. 가장 도착 거리가 작은 운전자도 카메라에 찍혀야 되므로 카메라는 두는 것은 자명하며, 가장 도착 거리가 작은 운전자부터 확인해야 다른 운전자들이 해당 단속카메라로 단속이 된다면, 카메라를 불필요하게 설치할 일이 ..
[프로그래머스] 네트워크(Lv3, BFS/DFS, 시간복잡도, Java, 정답, 코드)
programmers.co.kr/learn/courses/30/lessons/43162?language=java 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr ## 접근방법 같은 네트워크들끼리는 무조건 연결되어 있다는 점을 착안해서 문제를 풀어보자. 어떤 컴퓨터에서 탐색을 시작하면, 연결된 컴퓨터들을 모두 찾을 수 있다. 완전 탐색 기법인, BFS와 DFS를 둘다 가능하며, 시간복잡도는 O(N * N)이다. 완전 탐색 시에, 네트워크가 정해진 컴퓨터는 방문하지 않도록 체크한다. 생각보다 간단한 문제이므..
[프로그래머스] 광고 삽입(Java, Lv3, 카카오, 누적합)
programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr ## 접근방법 광고를 삽입해서, 가장 많은 시간이 누적되도록 하는 구간을 찾아야 한다. 시청자들의 출입에 관한 로그 정보들이 있다. 출입에 관한 로그 정보들을 이용해서, 1초동안 누적된 시간들을 구할 수 있다. 만약에 1초에 시청을 시작하고, 10초에 시청을 종료한다고 생각해보자. 1초의 순간에 한 명이 ..
디스크 스케줄링(디스크 구조, 기법)
우선 디스크 스케줄링을 알아보기 전에, 실린더, 플래터, 헤더, 트랙, 섹터 등의 용어들에 대해서 정리하고 가자. 위의 그림이 가장 정확하게 하드 디스크를 설명했다. 모든 플래터에는 헤드가 모두 존재한다. 입력으로 주어지는 것들은 트랙 번호이다. 추가적으로, 하드디스크 구조를 눈으로 보고 싶은 분들을 위해서 유튜브 영상도 하나 링크한다. www.youtube.com/watch?v=NtPc0jI21i0 위의 영상을 보면서, 하드디스크 구조를 확실히 파악할 수 있을 것이다. 디스크 스케줄링은 주어진 트랙 번호들을 찾아가는 과정들을 의미하며, 이동 거리 비교를 통해서 각 상황에서 스케줄링의 우위를 판단하게 된다. FCFS(First Comes First Served) 스택과 동일하게, 선입 선출 구조 들어온 ..
N보다 작은 특정 수의 배수를 찾아보자[최대 공약수, 최소 공배수, 교집합, Ugly Number III]
## 접근방법 간단히 생각해보자, N보다 작은 2의 배수의 개수는 몇 개일까? 정답은, N / 2개이다. N / 2개가 된다는 사실은 자명하므로 증명은 생략하겠다. A와 B가 있을 때, 두 수의 최대 공약수는 얼마일까? GCD(A, B) = GCD(B, A % B)이다. 증명은 아래와 같다. GCD(A, B) = G일 때, GCD(B, A % B)의 최대공약수도 G일까? A = G * a B = G * b A = B * q + r A % B = r = A - B * q B = G * b r = A - B * q = G * a - G * b * q= G(a - bq) 으로 증명될 수 있다. 이제 최소 공배수에 대해서 알아보자, 최소 공배수는 두 수의 곱에다가 최대 공약수를 나눠주면 된다. LCM(A, B)..
