본문 바로가기

알고리즘

 (138)
[프로그래머스][Python] 이중우선순위큐 문제를 정리해보자. l 숫자 => 큐에 숫자 삽입 D 1 => 큐에서 최댓값 삭제 D -1 => 큐에서 최솟값 삭제 단, 큐가 비어있는 상태에서 D 명령이 들어오면 무시한다. 최종 결과는 큐가 비어있다면 [0, 0]으로 아니라면, [최댓값, 최솟값]으로 출력한다. 리스트에 값을 넣을 때마다 정렬하는 방법을 선택했다. from collections import deque def solution(operations): li = [] for string in operations: alpha, num = string.split() if alpha == "I": # 삽입 li.append(int(num)) li = deque(sorted(li)) elif li: if alpha == "D" and num == "..
[프로그래머스][Python] H-Index 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 문제를 잘 이해해보자. 1) h번 이상 인용된 논문이 h편 이상이다. 2) 나머지 논문은 h번 이하 인용한다. 1), 2)를 만족하는 h의 최댓값을 구하여라 위 예시처럼, 먼저 배열을 오름차순으로 정렬한다. 정렬하면 n - index는 해당 값의 편 수가 된다. ( 물론 내림차순으로 하고 index + 1을 편 수로 잡아도 된다. ) 이때 각 값의 h값은 value와 n - index 중 더 작은 값이 된다. 예를 들어, 9번 이상은 4편이 있다. 여기서 h값으로 최대는 4이다. 그리고 2)는 고려할 필요가 없다. 무조건 만족하기 때문이다. 추..
[정렬] 병합 정렬 [Merge Sort] 병합 또는 합병 정렬에 대해 알아보자. 이는 분할 정복 방법을 통해 구현한다. (분할 정복은 큰 문제를 작은 문제 단위로 쪼개면서, 쉽게 풀 수 있는 문제 단위로 나눈 뒤 그것들을 다시 합치는 방식이다.) 퀵 정렬과 함께 빠른 정렬에 해당한다. 예를 들어보자. [6, 5, 3, 1, 8, 7, 2, 4] 숫자 1 ~ 8까지 들어있는 배열이 있다. 먼저 하나의 배열을 두 개로 쪼갠다. [6, 5, 3, 1] [8, 7, 2, 4] 그리고 다시 각 배열을 두 개로 쪼갠다. [6, 5] [3, 1] [8, 7] [2, 4] 또다시 각 배열을 두 개로 쪼갠다. [6] [5] [3] [1] [8] [7] [2] [4] 이제 더 이상 배열을 쪼갤 수 없다. 이제 두 개의 배열씩 합친다. 합칠 때는 둘 중에 값이 더..
[프로그래머스][Python] 가장 큰 수 문제를 정리해보자. "주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다." 주어진 정수를 이용해 가장 큰 수를 만들면 된다. 처음에는 완전 탐색을 시도했다. 하지만 시간초과로 실패했다. 두 번째에는 DFS를 시도했다. 하지만 구현에 어려움을 겪어 포기했다. 알고 보니 푸는 방법은 간단했다. 먼저 제한 사항을 보자. 예를 들어 [8, 883] 있다. 원소의 크기가 0이상 1,000 이하이므로, 각 원소를 문자열로 보고 3을 곱해준다. (1,000이 최대여서 4를 곱할 필요가 없다.) [888, 8838838883] 주의해야 할 점은 [0, 0, 0, 0] 같은 예이다. 0000이라는 수는 없다. 0으로..
[프로그래머스][Python] K번째수 조건에 따라서 array[i] ~ array[j]까지 정렬하고, k번째 원소가 무엇인지 찾으면 된다. def solution(array, commands): answer = [] for com in commands: i, j, k = com tmp = sorted(array[i-1:j]) answer.append(tmp[k-1]) return answer print(solution([1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]])) 다른 사람 풀이를 보자. def solution(array, commands): return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands)) lambda를..
[시간 복잡도] 빅오 표기법의 종류 1. O(1) : 상수형 2. O(logn) : 로그형 3. O(n) : 선형 4. O(n^2) : 2차형 5. O(n^3) : 3차형 6. O(n^k) : k차형 7. O(2^n) : 지수형 8. O(n!) : 팩토리얼형 1번에서 8번으로 갈수록 실행시간이 오래 걸린다. 크기가 가장 큰 항을 제외하고 나머지 항은 무시된다. (곱셈, 나눗셈 그리고 상수는 무시)
[프로그래머스][Python] 주식가격 주식가격이 내려가지 않은 기간은 몇 초인지 파악하는 문제이다. # 가격이 내려가지 않은 기간 from collections import deque def solution(prices): answer = [] prices = deque(prices) while prices: now = prices.popleft() result = 0 if not prices: result = 0 else: for val in prices: result += 1 if val < now: break answer.append(result) return answer print(solution([1, 2, 3, 2, 3])) 처음 들어간 값이 먼저나오는 Queue(FIFO)구조로 동작한다. 이렇게 풀게 되면 N + (N - 1) ..
[프로그래머스][Python] 더 맵게 문제를 정리해보자. 모든 음식의 지수를 K이상으로 만들어야 한다. 하나라도 K이상이 아니라면, 2개의 음식을 섞어서 새로운 음식을 만든다. 새로운 음식 = 가장 맵지 않은 음식의 지수 + (두 번째로 맵지 않은 음식의 지수 X 2) 모든 음식의 지수가 K라면 그만한다. 음식이 1개 남았는데, K보다 작다면 -1을 출력한다. Heap을 이용했다. import heapq def solution(scoville, K): answer = 0 heap = [] for num in scoville: heapq.heappush(heap, num) check = heap[0] while check < K: if len(heap) < 2: return -1 x = heapq.heappop(heap) y = heapq.h..
[프로그래머스][Python] 다리를 지나는 트럭 입력은 3개가 주어진다. bridge_length : 다리에 올라갈 수 있는 트럭 수 weight : 다리가 견딜 수 있는 무게 truck_weights : 트럭별 무게 문제는 '모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는가?'이다. 아래처럼 이해하면 편하다. bridge_length는 다리의 길이이다. 다리의 길이가 N이라면, N대가 올라갈 수 있다. 그리고 1대만 지나가는데 N초가 걸린다. 그리고 다리에서 완전히 나가야지 건넜다고 할 수 있다. [7, 4, 5, 6]를 스택형태로 이동시켜보자. 0 : [x,x] [] (시작) 1 : [x,7] [] 2 : [7,x] [] 3 :[x,4] [7] 4 : [4,5] [7] 5 : [5,x] [4,7] 6 : [x,6] [5,4,7] 7 : [6,x]..
[대회][BOJ][INU 코드페스티벌 2020] D번 20365 : 블로그2 문제를 정리해 보자. 문제를 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한다. 각 문제를 칠할 때 아래와 같은 과정을 한 번의 작업으로 수행한다. 1. 연속된 임의의 문제들을 선택한다. 2. 선택된 문제들을 전부 원하는 같은 색으로 칠한다. 단순히 위에서 아래로 칠해보자. 횟수 번호 1 1,2 2 3 3 4 4 5 5 6,7 6 8 최소한의 작업 횟수로 수행해보자. 이를 구현해야 한다. 횟수 번호 1 1,2,3,4,5,6,7 2 3 3 5 4 8 어떻게 구현해야 할까? 아래 방법처럼 하면 된다. (아래는 다른 예시이다.) 연속된 동일 알파벳은 하나의 알파벳으로 본다. 즉, 중복을 제거한다. (중복이 제거되었기 때문에 R과 B가 교차로 있게 된다.) R의 개수와 B의 개수 중, 더 큰 것은 한 ..

티스토리툴바