본문 바로가기

전체 글

 (426)
[Python] Heap & Heapq Heap 그리고 Heapq 모듈 본 문서에는 자료구조 힙(Heap)과 파이썬 모듈 Heapq에 관하여 공부한 내용을 기록한다. Heap 이란? 완전 이진 트리 중 하나로 우선순위 큐를 위하여 만들어진 자료구조다. 여러개의 값들 중 최댓값 또는 최솟값을 빠르게 찾아내기 위하여 고안된 자료구조다. (역시 모든 것은 필요에 의해 만들어진다.) 힙은 일종의 반정렬 상태를 유지한다. 큰 값이 상위 레벨에 있꼬 작은 값이 하위 레벨에 존재한다. 즉, 부모 노드의 키 값이 자식 노드의 키 값 보다 항상 큰(또는 작은) 이진 트리를 의미한다. 힙은 중복된 값을 허용한다. (이진 트리는 중복 값을 허용하지 않는다.) Heap의 종류 힙은 Max Heap, Min Heap으로 나뉘어진다. MaxHeap 부모 노드의 키 값..
[Algorithm] [Python] Programmers - 더 맵게 Programmers - 더 맵게 문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작..
[Algorithm] [Python] Programmers - 쇠막대기 Programmers - 쇠막대기 문제 설명 여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레이저의 배치는 다음 조건을 만족합니다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다. 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않습니다. 아래 그림은 위 조건을 만족하는 예를 보여줍니다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향입니다. 이러한 ..
[Algorithm] [Python] Programmers - 타겟 넘버 타겟 넘버 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연..
[Algorithm] [Python] Programmers - 124 나라의 숫자 Programmers - 124 나라의 숫자 문제 설명 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 자연수 n이 매개변수로 주어질 떄, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 작성해 주세요. 제한사항 n은 500,000,000 이하의 자연수 입니다. 제출 코드 1차 제출 코드 def solution(n): if n
[Algorithm] [Python] Programmers - 가장 큰 수 Programmers - 가장 큰 수 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 nu..
[Algorithm] [Python] Programmers - 피보나치 수 Programmers - 피보나치 수 문제 설명 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. 제한 사항 n은 1이상, 100000이하인 자연수입니다. 제출 코드 1차 제출 코드 def solution(n): if n == 0..
[Algorithm] [Python] 백준/BOJ - 4539 _ 반올림 Baekjoon - 4539 / 반올림 문제 정수 x가 주어졌을 때, 10보다 크다면, 1의 자리에서 반올림하고, 결과가 100보다 크면, 10의 자리에서 반올림하고, 1000보다 크면, 100의 자리에서 반올림하고... 이와 같이 계속 반올림하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 x가 주어진다. (0 ≤ x ≤ 99999999) 출력 각 테스트 케이스마다 입력으로 주어지는 정수를 문제 설명에 나온 것처럼 반올림한 결과를 출력한다. 제출 코드 from sys import stdin def _4539(x): x = list(map(int, str(x))) if len(x) == 1: # 1의 자리인 경우 prin..

티스토리툴바