본문 바로가기

알고리즘

(138)
[프로그래머스][Python] 큰 수 만들기 문제를 정리해보자. 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하자. 예) 1924에서 2개를 제거하면 19, 12, 14, 92, 94, 24이다. 여기서 가장 큰 수는 94이다. 풀이를 생각해보자. '가장 큰 수'를 만들려면 어떻게 해야 할까? 앞자리에 큰 수가 있어야 한다. 따라서 k개만큼 제거하되 앞자리일수록 큰 수가 와야 한다. 1) 1924를 예로 들어보자. (k = 2) 9는 1보다 크다. 따라서 1보다 앞에 위치해야 한다. 따라서 1을 제거하고 9를 앞에 위치시킨다. 이제 제거할 수 있는 수는 1개이다. (결과 : 924) 4는 2보다 크다. 따라서 2보다 앞에 위치해야 한다. 따라서 2를 제거하고 4를 앞에 위치시킨다. 이제 제거할 수 있는 수는 0개이다. (..
[프로그래머스][Python] 구명보트 문제를 정리해보자. 구명보트를 이용해 모두를 탈출시켜야 한다. 구명보트에는 최대 2명이 탑승한다. 탑승자의 무게 합이 제한을 초과하면 안 된다. 모든 사람을 구출하는 데 필요한 구명보트의 최솟값을 구해야 한다. 풀이를 생각해보자. 1. 두 사람이 타는 경우 (가장 무거운 사람 + 가장 가벼운 사람)이 무게 제한을 초과하지 않으면 둘 다 태운다. 한 번 태운 사람은 두 번 다시 태우지 않는다. 2. 한 사람이 타는 경우 (가장 무거운 사람 + 가장 가벼운 사람)이 무게 제한을 초과한다면, 가장 무거운 사람만 태운다. 3. 마지막 사람 50은 70, 80이 나갔기 때문에 배열에 혼자 남겨졌다. 따라서 가장 무거운 사람도 아니고, 가장 가벼운 사람도 아니다. 이 경우는 '마지막 사람'이라고 생각한다. 그냥 내..
[대회][BOJ][INU 코드페스티벌 2021] C번 23843 : 콘센트 문제를 정리해보자. 1. N개의 전자기기를 충전해야 한다. 2. M개의 사용 가능한 콘센트가 있다. 전자기기 1개당 콘센트 1개가 필요하다. 그리고 전자기기마다 충전에 필요한 시간, T가 주어진다. 모든 전자기기를 충전하기 위한 최소 시간을 구해야 한다. 풀이를 생각해보자. 이 문제는 '최소 대기시간으로 충전해서 가져가는 최대 인원'을 구하는 게 아니라, '모든 기기를 충전하는 최소 시간'을 구하는 것이다. 문제의 예시로 전자와 후자를 비교해보자. 전자는 13시간이 걸리고, 후자는 9시간이 걸린다. 따라서 충전이 오래 걸리는 기기부터 충전해야 한다. 정리해보면, 넣을 때는 충전이 가장 오래 걸리는 기기를 넣는다. 그리고 콘센트 누적 충전 시간에 현재 기기 충전 시간을 더한다. (처음에는 0이다.) 그다음..
[대회][BOJ][INU 코드페스티벌 2021] B번 23842 : 성냥개비 문제를 정리해보자. 성냥개비를 이용해서 '올바른 수식'을 만들어야 한다. 올바른 수식이 되는 조건은 아래와 같다. 1. @@+@@=@@ 형태를 만족해야 한다. (모든 수는 항상 두 자릿수로 표현해야 한다. 예를 들면, 27은 27이다. 5는 05이다.) 2. N개의 성냥개비가 주어진다. 모두 사용해야 한다. (+와 =에도 각각 2개의 성냥개비가 필요하다.) 풀이를 생각해보자. 모든 경우의 수를 따져보면 된다. (0+0=0부터 99+99=99까지 완전 탐색한다.) 그리고 경우마다, 1. 수식이 성립하는가? 2. 수식이 N개의 성냥개비를 사용하는가? 를 따진다. 1, 2를 모두 만족하면 올바른 수식이다. 구현해보자. 숫자마다 사용되는 성냥개비 개수는 아래와 같다. 0은 6개 1은 2개 2는 5개 3은 5개 ..
[대회][BOJ][INU 코드페스티벌 2021] A번 23841 : 데칼코마니 문제를 정리해보자. N X M인 격자무늬의 사각형이 있다. N은 세로의 길이, M은 가로의 길이이다. 그리고 M은 짝수이다. 이 격자무늬 사각형의 칸에는 물감이 묻은 곳이 있다. 이 사각형을 반으로 접었을 때, 맞닿는 칸은 물감이 번진다. 번진 결과를 출력해야 한다. 풀이를 생각해보자. M이 짝수인 점이 중요하다. 만약 M이 6이고, N은 4라고 하자. 가로의 index를 보면 0 5 1 4 2 3 이렇게 맞닿게 된다. 즉, i (0
[프로그래머스][Python] 카펫 문제를 정리하자. 1. 안쪽은 노란색으로 칠해져 있고, 테두리 '1줄'은 갈색으로 칠해져 있는 격자 모양의 카펫이 있다. 2. 현재 노란색과 갈색으로 색칠된 격자의 개수를 알고 있다. 3. 가로 길이는 세로의 길이보다 길거나 같다. 전체 카펫의 가로와 세로의 길이를 구하여라. brown = 24, yellow = 24일 때를 생각해보자. 가로의 총합, 세로의 총합은 모두 짝수이다. (가로도, 세로도 변의 개수가 짝수이기 때문이다.) 따라서 brown 가로의 길이를 구하기 위해, 2씩 빼면서 경우의 수를 나열해보자. 주의할 점은 1. 가로 길이의 총합이 길이가 전체 길이가 되면 안 된다. 세로 길이의 총합이 0이 되기 때문이다. 2. 가로의 길이는 세로의 길이보다 길거나 같다. 가로 총합: 24(x) ->..
[프로그래머스][Python] 모의고사 문제를 정리해보자. 수포자 1, 2, 3 모두는 규칙적으로 정답을 찍는다. 실제 정답이 들어있는 배열과 수포자들의 정답을 비교해서 정답을 가장 많이 맞힌 수포자를 찾으면 된다. (1명 이상이다.) from collections import deque def solution(answers): l = len(answers) su_1 = deque([1, 2, 3, 4, 5]) # 5 su_2 = deque([2, 1, 2, 3, 2, 4, 2, 5]) # 8 su_3 = deque([3, 3, 1, 1, 2, 2, 4, 4, 5, 5]) # 10 result = [0, 0, 0] # 정답 비교 for num in answers: if num == su_1[0]: result[0] += 1 if num == ..
[정렬] in-place vs not in-place 1. in-place 원소의 개수에 비해 충분히 무시할 만한 저장 공간을 더 사용하는 정렬 알고리즘 2. not in-place 원소의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘
[정렬] stable vs not stable 1. stable vs not stable 중복된 키값이 있을 때 이를 원래 순서대로 정렬하는 알고리즘 정렬 전처럼 주황색 3이 초록색 3보다 앞에 있다. 2. in-place vs not in-place 중복된 키값이 있을 때 이를 원래 순서와 다르게 정렬하는 알고리즘 정렬 전과 다르게 주황색 3이 초록색 3보다 뒤에 있다.
[정렬] 퀵 정렬 [Quick Sort] 퀵 정렬에 대해 알아보자. 이는 분할 정복을 통해 구현한다. (분할 정복은 큰 문제를 작은 문제 단위로 쪼개면서, 쉽게 풀 수 있는 문제 단위로 나눈 뒤 그것들을 다시 합치는 방식이다.) 불안정 정렬이고 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다. 그리고 병합 정렬과 함께 빠른 정렬에 해당한다. 병합 정렬과는 분할 정복을 통해 해결한다는 공통점이 있다. 차이점은 아래와 같다. 1) 병합 정렬 : O(n)의 시간이 걸리는 과정을 재귀호출 후에 한다. (분할 후 병합 시점에서 비교 연산 발생) 2) 퀵 정렬 : O(n)의 시간이 걸리는 과정을 재귀호출 전에 한다. (분할 시점부터 비교 연산 발생) 따라서 퀵 정렬이 병합에 들어가는 비용이 적거나 구현 방법에 따라서 아예 병합하지 않을 수도 있다...