본문 바로가기
반응형

Python/알고리즘문제38

[프로그래머스][탐욕법(그리디)] 체육복 programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 해설 각 학생이 가지고 있는 체육복의 수를 dictionary를 이용하여 만든다 각 요소를 오른쪽 방향으로 순회한다. 체육복을 한개 이상 들고 있을시 왼쪽 학생먼저 체육복이 없을경우 빌려주고 그다음으로 오른쪽 학생을 체크 한다. def solution(n, lost, reserve): answer = n mydict = {} for i in range(1,n+1): mydict.. 2021. 4. 1.
[프로그래머스][힙] 디스크 컨트롤러 programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 해설 대기하는 작업들중 수행시간이 가장 작은작업을 먼저 처리해야 한다. 현재 작업중인 작업이 [0, 3] 라고 하자 대기 작업 [1, 9], [2, 6] 이 있다고 하자 저기서 대기작업들의 걸리는 시간을 생각해보면 간단하다. 만약 대기작업이 2개가 있다고 치자. 각각 걸리는 작업의 시간은 앞에오는놈 : (현재 작업중인 작업의 종료시간 - 앞에오는놈의 시작시간) + 앞에오.. 2021. 3. 31.
[프로그래머스][힙(heap)] 더 맵게 programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 해설 시키는대로 heap을 이용해 풀면 된다. 한번 스코빌 지수를 계산할때마다 전체 원소의 수가 하나씩 줄어드는데 이때 heap의 사이즈가 0이 되면 바로 return -1을 해주면 된다. import heapq def solution(scoville, K): answer = 0 q = [] for i in scoville: heapq.heappush(q,i) w.. 2021. 3. 25.
[프로그래머스][정렬] H-Index 해설 문제를 보면 x번 -> 세로축 x편 -> 가로축 이라고 생각 할 수 있다. 풀이방법 내림차순으로 정렬한다 가로세로가 h인 정사각형을 떠올리고 정사각형의 한 변의 길이가 가장 최대일때를 계산한다. def solution(citations): citations.sort(reverse=True) length = len(citations) answer = 0 for i in range(length): if citations[i] < i+1: break else: answer = i+1 return answer 다른사람 풀이를 보니 아래와 같이 개쩌는 풀이를 발견했다. 아이디어는 똑같은데 enumerate를 이용한게 참으로 멋있구만. def solution(citations): citations.sort(r.. 2021. 3. 25.
[프로그래머스][정렬] 가장 큰 수 programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 아이디어 문자열 A+B, 로 만든 숫자와 B+A로 만든 숫자를 비교하여 어느게 더 큰수인지 확인하고 정렬한다 파이썬 문자열 비교를 이용하면 사전순으로 정렬해주는데 이걸 수 비교수단으로 이용할 수 있다 답이 0일 경우에는 0만 리턴해준다.(마지막 테스트 케이스) from functools import cmp_to_.. 2021. 3. 24.
[프로그래머스][정렬] K번째수 해설 시키는대로 하면 된다. def solution(array, commands): answer = [] for i, j, k in commands: sorted_array = sorted(array[i-1:j]) answer.append(sorted_array[k-1]) return answer 2021. 3. 24.
[프로그래머스][스택/큐] 기능개발 programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 작업이 끝나는 날짜를 배열로 만든다. 그걸 큐에 담아서 첫번째 요소 기준으로 다음 요소가 작으면 하나하나 pop 해나가면서 카운트한다. from math import ceil from collections import deque def solution(progresses, speeds): answer = [] days = deque() for i, j in zip(pr.. 2021. 3. 19.
[프로그래머스][스택/큐] 주식가격 programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 스택/큐 문제라고 해서 계속 생각했는데 아닌거 같다. 문제 조건을 보면 10000 단위이다. 10000^2은 1억이니깐 cpu 가 Ghz(10억)인걸 감안하면 초단위 안으로 계산 가능하다 즉 N^2 으로 이중포문으로 풀어도 된다는 뜻 제출하고 다른사람 풀이 보니 역시나 N^2으로 풀었다. 어이..... def solution(price.. 2021. 3. 19.
[프로그래머스][해시] 베스트앨범 programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 이게 왜 해시문제이지... 전형적인 heap 문제인거 같은 느낌인데.... 일단 딕셔너리를 사용하긴 했다. 아이디어는 이렇다. zip으로 장르와 플레이수를 합친 리스트를 만든뒤 dictionary 자료형으로 장르별 플레이수를 만든다. 위에 나온 조건에 맞는 heap을 구현할 class를 생성한다. heappop()을 하면서 dictionary 자료형으로 장르당 2번 나왔는지.. 2021. 3. 17.
[프로그래머스][해시] 위장 programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 이걸 해시라고 해야하는게 맞는건지... 그냥 순열 문제이다. 모자가 3개, 옷이 5개, 신발이 4개 있다 치자 모자를 고르는 경우의수는 3+1 = 4 (+1은 선택하지 않음을 의미) 옷을 고르는 경우의수는 5+1 = 6 신발을 고르는 경우의수는 4+1 = 5 문제에서 아예 안고르는 경우의 수는 빼라 했으므로 마지막에 -1 해주면 된다. 4 * 6 * 5 - 1 이런식으로 풀면된다. def solution(clothes): answer = 0 mydict = {} for i in clothes: if i[1] in mydict: mydict[i[1]] = mydi.. 2021. 3. 17.
[프로그래머스][해시] 전화번호 목록 programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 문제는 풀었는데 다른사람이 파이썬 내장함수로 한줄로 푸는거 보고 충격... 정리 따로 해야겠다. 아이디어는 이렇다. 전화번호부로 set을 이용해 hash테이블을 만든다. 각번호를 순회하면서 이중포문을 통하여 번호의 부분문자열을 얻은뒤 hash 테이블에 있는지 확인한다. hashtable에 있다면 누군가의 접두어가 된다는 뜻이므로 False를 리턴한다 이렇게 하면 시간복잡도.. 2021. 3. 12.
[프로그래머스][스택/큐] 다리를 지나는 트럭 programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr 해결 아이디어 문제롤 보면 트럭 하나가 지나가는데 걸리는 시간은 다리의 길이 + 1 초이다. 큐에다가 트럭이 들어오지 않으면 0을 넣고 트럭이 들어오면 트럭의 무게를 넣어준다. 첫번째 트럭의 경우만 생각해보면 [ 0, 0, 7 ] 로 큐의길이인 3초만에 다리를 건너게 된다. 위와 똑같은 방법으로 다리의 길이만큼 따로 버퍼큐를 하나 빼서 다리의 현재 무게를 측정.. 2021. 3. 12.
[프로그래머스][해시] 완주하지 못한 선수 programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr c++스타일로 풀어봤다. completion 배열을 dictionary로 만들어준다. value값을 기본적으로 1로 주고 동명이인이 있는경우 value에 1을 더해주어 몇명이 있는지 세어준다. 이후 participant를 확인하면서 이름이 존재 할 때 마다 value값을 -1씩 해준다. value가 0이거나 dictionary에 없는경우가 답이므로 해당값 .. 2021. 3. 12.
[백준 1463] 1로 만들기 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net Top-Down으로 푸니깐 메모리 초과가 난다. 파이썬으로 알고리즘 풀면 뭔가 코드가 간결하긴 한데 이런거에 있어서 제약이 심한듯 ㅠ 재귀함수 사용할 때 recursion제한도 풀어주어야 하고... 고려할게 많다. bottom-up으로 풀면 쉽게 풀린다. x = int(input()) dp = [987654321 for _ in range(1000000+1)] dp[1] = 0 for i in range(2, x+1): if i % 3 == 0: dp[i] = min(dp[i], dp[i//3] + 1) if i % 2 ==.. 2021. 3. 11.
[백준 2606] 바이러스 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 간단한 bfs 문제이다. 답을 출력할때 1번에 의해 감염된 컴퓨터수 이니 카운팅할때 1번 컴퓨터는 제외해주자. import sys from collections import deque N = int(input()) M = int(input()) near = [[] for _ in range(N+1)] for _ in range(M): u, v = map(int, sys.stdin.readline().split()) .. 2021. 3. 11.
[백준 2805] 나무자르기 기억하자. 어떤 직선에서 특정값을 찾아야 한다 => 이분탐색 문제! logN 나무를 자르는 행위는 시간복잡도가 N이다 고로 이문제는 이분탐색 + 나무자르기로 NlogN에 풀 수 있다! 이분탐색 하는법 left와 right 값을 설정한다 mid값 기준으로 while(left > N >> M; int left = 1; int right = 0; for (int i = 1; i >tree[i]; right = right > tree[i] ? right : tree[i]; } long long ans = 0; while (left= M) { left = mid + 1; ans = ans > mid ? ans : mid; } else { right = mid - 1; } } cout mid else mid eli.. 2021. 3. 11.
[백준 1753] 최단경로 대표적인 다익스트라 알고리즘. c++에서는 우선순위 큐를 사용하고 파이썬에서는 heapq를 사용해주자. 이문제가 거지같은점은 cout으로 하면 시간초과나고 printf로 출력하면 통과한다는 것이다. 파이썬은 그냥 스무스하게 통과하는데.... #include #include #include #include using namespace std; vector adj[20001]; int V, E, s; #define INF 987654321 bool visit[20001]; void dikjstra(int start) { memset(visit, 0, sizeof(visit)); int dist[20001]; for (int i = 1; i dist[now])continue; for (pair nextnode.. 2021. 3. 11.
[백준 15649] N과 M (1) www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으.. 2021. 3. 11.
반응형

티스토리툴바