gaki gaki

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제 풀이 정수 N 을 최소로 사용해서 K 를 만들어야한다. 최대 8번까지 N 을 사용 할 수 있고, 8번이 넘어갈 경우 -1 을 리턴하면 된다. DP 를 사용해서 풀 수 있으며, N 을 1 번 사용했을 때, 2번 사용했을 때, 3번 사용했을 때 .... 8번 사용했을 때의 값들 중에서 K 가 있는지 확인하고 K 가 있으면 몇 번 사용했을때 K 가 나왔는지를 리턴하면 된다. n 이라는 배열을 사용했고, n[i] 는 n 을 i 번 사용했을 때 나올 수 있는 모든 경우의 수들의 집합이다. 또한, 중복되는 숫자의 방지를 위해서 tota..

100일 동안 매일 알고리즘을 하면? - 14일차 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 이 문제는 크루스칼(Kruskal) 알고리즘으로 풀 수 있는 문제이다. 크루스칼 알고리즘을 이해하기 위해서 2가지 배경지식이 필요한데, 첫번째는 spanning tree 이고, 두번째는 union-find 이다. 1. spanning tree 란? spanning tree 는 n 개의 정점을 (n-1) 개의 간선을 사용해서 모두 연결하는 트리이다. 여러 spanning tree 중, 모든 간선의 비용 합이 가장..

100일 동안 매일 알고리즘을 하면? - 13일차 https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 큰수 만들기문제는 오름차순및 내림차순을 활용한 문제였다. 이 문제에서 12번 테스트케이스 "999",2 를 통과하지 못했었다. 테스트를 통과하지 못했던 이유는 오름차순, 내림차순에만 신경쓰다보니 같은 숫자가 나왔을때 k 값을 어떻게 처리해야 하는지에 대해서는 고려하지 않았던게 패인이였다. 오름차순, 내림차순으로 값을 처리할때는 계속 같은 값이 나오는 상황을 반례로 만들어놓고 풀자. def ans(deleted, number): answer = ""; for idx,v in enumerate..

100일 동안 매일 알고리즘을 하면? - 12일차 https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr

https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 수학으로 풀었다. 약간 수학적 귀납법, DP 느낌으로 푼것같은데 이게 직관적인 풀이는 아닌것같긴하다. 다른 사람들의 코드를 보니깐 다 고만고만한데, 다들 시간복잡도 O(N^2) 으로 풀었다. 내 코드 또한 O(N^2) 이긴한데 break 문 덕분에 시간초과가 안난듯하다. def solution(prices): ret = ..

100일 동안 매일 알고리즘을 하면? - 10일차 https://programmers.co.kr/learn/courses/30/lessons/42628# 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 문제를 금방 풀 수 있었으나, 힙에 아무것도 없을경우 [0,0] 을 리턴하는 예외처리를 안해줘서 1시간동안 헤매다가 결국 풀었다. 되게 쉬운 문제였고 직관적인 문제였으나 짜잘한 실수들때문에 오래걸렸다. str 형 숫자를 Int 로 바꿔주지 않아서, 예외처리를 안해줘서 import heapq; def solution(operations): minHeap = []; maxHeap = []; for o in operations: order, num = o.split(' '); if (order..

https://programmers.co.kr/learn/courses/30/lessons/42627 이 문제는 우선순위 큐 ( 힙 ) 을 사용해서 푸는 문제였는데 몇가지 풀리지 않은 궁금증이 있다. 1. 실행 시간이 가장 작은걸 먼저 실행하는게 결과적으로 최소의 평균시간을 도출한다는 것을 어떻게 증명할 수 있는지? 2. heap 에 값을 push 할 때 실행시간은 같지만, 더 먼저 요청된 작업을 먼저 실행하든 말든 결과에는 영향이 없는데 이걸 어떻게 수학적으로 증명 할 수 있는지? ---> 수정 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 라는 조건때문에 이 모든게 성립한다. 즉, 현재 수행 할 수 있는 작업들을 heap에 넣는데, 정렬 기준은 작업 시간의 오..

100일 동안 매일 알고리즘을 하면? - 8일차 https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 이 문제는 dictionary 와 sort 에 대해서 묻는 문제였다. python 에서 딕셔너리와 2차원 배열에 대해서 sort 를 사용하는 방법에 대해서 배울 수 있었다. def solution(genres, plays): ret = []; info = {}; sum = {}; for i in range(len..