1. 아이디어 ▪ 아이디와 제재 아이디를 입력 받았을때 해당 아이디가 제재 대상인지 확인하는 함수 작성  ▪ dfs로 구현   - i는 현재까지 확인한 불량 사용자 아이디 목록 인덱스   - i가 불량 사용자 아이디 목록의 길이와 같으면       - chk 리스트를 정렬하고 하나의 문자열로 합쳐서 rs 리스트에 append -> 추후 중복값을 없애기 위함   - 아이디 목록에서 아이디를 하나씩 꺼내서 다음을 수행      - 해당 아이디를 방문하지 않았고, 현재 인덱스의 불량 사용자 아이디와 비교했을때 제재 대상에 해당할 경우         - 해당 아이디를 방문여부 리스트에 추가하기         - dfs(i+1) 수행         - 해당 아이디를 방문여부 리스트에서 제거하기    - set 함..

1. 아이디어 ▪ dp 알고리즘 사용 ▪ 첫번째 스티커를 뗀 경우와 안 뗀 경우를 구분해서 해야함 - why? 뗀 경우에 마지막 스티커는 사용할 수 없기 때문 ▪ dp[i]를 i번째까지 스티커 배열에서 얻을 수 있는 최대 값이라고 한다면, 두가지 경우의 수로부터 dp[i]를 구할 수 있음 - i-1번째 스티커를 뗀 경우 -> i번째 스티커는 뗄 수 없기 때문에 i-1번째까지의 최대값이 dp[i]가 됨 - i-1번째 스키터를 떼지 않은 경우 -> i-2번째까지의 최대값 + i번째 스티커 값이 dp[i]가 됨 ▪ 이를 점화식으로 나타내면 dp[i] = max(dp[i-1], dp[i-2] + sticker[i]) ▪ 첫번째 스티커를 뗀 경우와 안 뗀 경우를 나눠서 dp 배열을 0부터 순서대로 채워주고, 배열..

1. 아이디어 ▪ 장르별 재생횟수 합계 구하기 ▪ 장르별 노래리스트 만들기 (고유번호,재생횟수) ▪ 재생횟수 합계 기준 내림차순으로 장르 정렬하기 ▪ for 문으로 재생횟수 합계 기준 내림차순으로 장르를 꺼내며 다음을 수행 - 꺼낸 장르의 노래리스트를 (재생횟수, 고유번호) 기준 (내림차순, 오름차순)으로 정렬 - 재생횟수가 가장 많은 2곡만 answer에 append 2. 시간복잡도 ▪ O(N), N: 노래의 개수 3. 변수 ▪ 장르별 재생횟수: dict(장르 : int) ▪ 장르별 노래리스트: dict(장르 : [(고유번호,재생횟수)]) Code def solution(genres, plays): answer = [] plays_sum = {} genres_plays = {} for i, (genre..

1. 아이디어 ▪ 전파가 전달되지 않은 연결된 아파트의 수를 (w*2+1)으로 나누고 올림한 값 = 필요한 기지국 개수의 최솟값 -> Greedy ▪ 현재까지 확인한 아파트 인덱스를 저장할 변수 1로 초기화 ▪ 현재 기지국이 설치된 지점을 for문으로 꺼내옴 - 꺼내온 기지국을 기준으로 왼쪽에 있는 아파트들 중 전파가 전달되지 않는 아파트의 수를 구하고 (w*2+1)로 나누고 올림한 값을 answer에 더해줌 - 현재까지 확인한 아파트 인덱스 갱신 ▪ 현재까지 확인한 아파트 인덱스가 n보다 작거나 같으면 - 아직 확인하지 않은 아파트의 수에 (w*2+1)를 나누고 올림한 값을 answer에 더해줌 2. 시간복잡도 ▪ O(m), m: 현재 설치된 기지국의 개수 3. 변수 ▪ 현재까지 확인한 아파트 인덱스:..

1. 아이디어 ▪ 차량의 이동 경로를 나간 지점 기준으로 정렬하고, 나간 지점을 기준으로 겹치는 부분에 카메라를 설치하면 카메라를 최소로 설치할 수 있음 -> Greedy ▪ heap에 routes를 넣어서 나간지점 기준 오름차순으로 정렬 ▪ 현재 카메라가 설치된 지점 -30001으로 초기화 ▪ heap이 빌때까지 다음을 반복 - heap에서 차량의 이동경로 꺼내오기 - 현재 카메라가 설치된 지점이 차량의 이동경로 시작점보다 작으면 - answer += 1 - 현재 카메라 지점을 꺼내온 차량의 이동경로 나가는 지점으로 갱신하기 2. 시간복잡도 ▪ O(nlogn), n: 차량의 대수 3. 변수 ▪ routes를 저장할 heap: heap ▪ 현재 카메라가 설치된 지점: int 4. 오답노트 ▪ routes..

1. 아이디어 ▪ Greedy 알고리즘 사용 ▪ A, B 정렬하기 ▪ B에서 카드를 하나씩 뽑으며 A를 최소비용으로 이길 수 있는 카드 찾기 - B의 카드가 A의 카드보다 크면 - answer += 1 - A 카드 새로 뽑기 2. 시간복잡도 ▪ O(n) 3. 변수 ▪ 현재 A의 카드 index를 저장할 변수: int Code def solution(A, B): answer = 0 A.sort() B.sort() j = 0 for i in range(len(A)): if A[j] < B[i]: answer += 1 j += 1 return answer 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 ..

1. 아이디어 ▪ dp 알고리즘으로 구현 ▪ (i,j) 좌표로 가는 경로의 수는 다음의 점화식을 따름 -> dp[j][i] = dp[j-1][i] + dp[j][i-1] ▪ 경로의 수를 저장할 dp 리스트 0으로 초기화, 시작점인 (1,1)은 1로 초기화 ▪ 2중 for문 돌면서 경로의 수 리스트 채우기 - (1,1)인 경우 skip - (i,j)가 물에 잠긴 경우 해당 좌표로 가는 경로의 수는 0 - (i,j)로 가는 경로의 수는 (i-1,j)로 가는 경로의 수와 (i,j-1)로 가는 경로의 수를 더한 값에 % 1000000007 ▪ dp의 마지막 행, 마지막 열 값 return 2. 시간복잡도 ▪ O(n*m) 3. 변수 ▪ 경로의 수를 저장할 리스트: int[][] Code def solution(m..

1. 아이디어 ▪ n = 2, s = 6 일때 [3,3]가 최대 곱 ▪ n = 3, s = 9 일때 [3,3,3]가 최대 곱 ▪ 즉, 원소 n개의 분포가 고를수록 집합의 곱이 크다는 점을 이용 -> Greedy ▪ s보다 n이 클 경우 [-1] return ▪ s를 n으로 나눈 몫과 나머지 값 구하기 ▪ (n - 나머지 값) 번 만큼 answer 리스트에 몫을 append ▪ (나머지 값) 번 만큼 answer 리스트에 (몫+1)을 append 2. 시간복잡도 ▪ O(n) 3. 변수 ▪ 나머지, 몫: int Code def solution(n, s): answer = [] if n > s: return [-1] x = s // n remain = s % n for _ in range(n-remain): ..