알고리즘/프로그래머스
-
[탐욕법(Greedy)] 구명보트알고리즘/프로그래머스 2021. 10. 9. 18:17
https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제를 잘읽자... (구명보트에 한 번에 최대 2명씩 밖에 탈 수 없다고 한다.) 몸무게 순으로 정렬하고, 양 끝에 포인터를 두어 풀면된다. def solution(people, limit): answer = 0 people.sort() left, right = 0, len(people)-1 while left
-
[탐욕법(Greedy)] 큰 수 만들기알고리즘/프로그래머스 2021. 10. 9. 18:13
https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 뭔가 좋은 방법이 잘 생각안나서, 구글링의 도움을 받았다. 앞자릿수가 커야 큰 숫자가 된다는 것과 스택을 활용하면 된다. def solution(number, k): stack = [] for i in number: while stack and i > stack[-1]: #넣으려고 하는 값이 더 클 때 if k > 0: stack.pop() k -= 1 else: break stack.append(i) for i in range(k): stack.pop() return "".join(stack)
-
[탐욕법(Greedy)] 조이스틱알고리즘/프로그래머스 2021. 10. 9. 18:10
https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 상하 조이스틱과 좌우 조이스틱을 따로 계산한다. 상하 횟수는 구하기 쉽고, 좌우의 경우는 그리디 알고리즘에 따라, 그 순간순간 가장 가까운 위치로 커서를 이동하면서 해를 구하면된다. def solution(name): answer = 0 name = list(name) a = 'ABCDEFGHIJKLM_ ZYXWVUTSRQPON' #상하 계산..
-
[탐욕법(Greedy)] 체육복알고리즘/프로그래머스 2021. 10. 9. 18:09
https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 문제를 꼼꼼히 안 읽어서 고생했다. def solution(n, lost, reserve): l = [i for i in lost if i not in reserve] r = [i for i in reserve if i not in lost] for i in sorted(r): if i-1 in l: l.remove(i-1) elif i+1 in l: l.remo..
-
[힙(Heap)] 이중우선순위큐알고리즘/프로그래머스 2021. 10. 9. 17:54
https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. heapqueue 알고리즘 - https://docs.python.org/ko/3/library/heapq.html heapq.heapify(x) 리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다. heapq.nlargest(n, iterable, key=None) iterable에 의해 정의된 데이터 집합에서 n 개의 가장 큰 요소로 구성된 리스트를 반환..
-
[위클리 챌린지] 9주차알고리즘/프로그래머스 2021. 10. 5. 20:35
https://programmers.co.kr/learn/courses/30/lessons/86971?language=python3 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 그래프 탐색 문제..? 아무튼 뭐 트리 그래프의 간선을 하나 지워서 두개의 트리를 만들때, 정점이 개수의 차의 최소값을 구하면된다. - 풀이 1. 일단 어떤 간선을 지우는 것이 답인지 모르니까, 하나의 간선을 지운 graph를 만든다. 2. search함수에 graph와, 시작점(삭제한 간선의 정점 중 하나)를 인자로 넘겨준다. 3. stack을 ..
-
[힙(Heap)] 디스크 컨트롤러알고리즘/프로그래머스 2021. 10. 3. 15:47
https://programmers.co.kr/learn/courses/30/lessons/42627?language=python3# 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr - 풀이 * 해당 시점마다 가장 소요시간이 작은 작업을 우선적으로 선택 heapq 사용() 1. jobs를 작업이 요청되는 시점기준으로 정렬 >> jobs = [[0, 3], [1, 9], [2, 6]] 2. 만약 해당 sec이하에 요청된 작업들이 있으면, jobs에서 pop해서 queue에 (소요시간, 요청된 시점)의 딕셔..
-
[스택/큐] 다리를 지나는 트럭 / 프린터알고리즘/프로그래머스 2021. 10. 3. 14:07
https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr - 문제의 상황을 코드로 잘 표현하면, 해결가능하다. def solution(bridge_length, weight, truck_weights): time = 0 queue = [0] * bridge_length #다리길이 만큼의 queue, 비어있으면 0 while queue: time += 1 queue.pop(0) #다리 맨앞을 ..