IT-garden

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 지난주에 너무 많은 돈을 써 버렸다. 그래서 오늘은 돈을 최소로 지불해서 카드 N개를 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최솟값은 4원이다. 1개 들어있는 카드팩을 4번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 2개 들어있는 카드팩을 2번 사면 4원이고, 이 경우가 민규가 지불해야 하는 금액의 최솟값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최솟값을 출력한다.

예제 입력과 출력

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))
a=[0]+a
dp=a

for i in range(1,n+1):
    for j in range(1,i):
        print(i-j,j)
        dp[i]=min(dp[i],dp[i-j]+a[j])

print(dp[n])

dp[n]을 입력받은 리스트 a로 만듭니다. (ex. dp[2]=카드 2개를 2개팩으로 샀을 때의 가격)

dp[n]=
dp[n-1]+a[1]
dp[n-2]+a[2]
dp[n-3]+a[3]
dp[n-4]+a[4]
.
.
.
dp[1]+a[n-1] 중 가장 작은 값을 선택합니다.

백준 알고리즘 16194번 : https://www.acmicpc.net/problem/16194

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))
a=[0]+a
dp = [0]*(n+1)

for i in range(1,n+1):
    for j in range(1,i+1):
        dp[i]=max(dp[i],dp[i-j]+a[j])

print(dp[n])

dp[n]=
dp[n-1]+a[1]
dp[n-2]+a[2]
dp[n-3]+a[3]
dp[n-4]+a[4]
.
.
.
dp[n-n]+a[n] 중 가장 큰 값을 선택합니다.

백준 알고리즘 11052번 : www.acmicpc.net/problem/11052

원형연결리스트(Circular Linked List)는 단순연결리스트에서 첫 노드와 마지막 노드를 연결한 연결리스트를 구현한 자료구조입니다.

마지막 노드를 참조하는 last가 단순연결리스트의 head 역할을 하기 때문에 마지막 노드와 첫 노드를 O(1) 시간에 방문할 수 있습니다.

리스트가 비어있지 않으면 어떤 노드도 None를 가지고 있지 않기 때문에 프로그램에서 None 조건을 검사하지 않아도 된다는 장점을 가집니다.

하지만 원형연결리스트에서는 반대 방향으로 노드들을 방문하기 쉽지 않으며 무한 루프가 발생할 수 있다는 단점이 있습니다.

원형연결리스트의 기본 구조입니다.

last는 원형연결리스트의 첫 번째 노드가 무엇인가 의미하는 정보입니다.

node는 아이템과 레퍼런스를 가집니다.

item은 항목으로 node값이 저장됩니다.

reference는 메모리 주소를 의미하며 다음 노드의 위치를 알려줍니다.

insert() : 리스트가 empty인 경우, 일반적인 경우

delete() : 한 개의 노드만 있는 경우, 노드가 2개 이상 있는 일반적인 경우

원형연결리스트의 파이썬 코드입니다.

class CList:
    class Node:
        def __init__(self, item, link): # 노드 생성자
            self.item = item  # 항목
            self.next = link  # 다음 노드 레퍼런스

    def __init__(self):  # 원형 연결 리스트 생성자
        self.last = None  # 마지막 노드를 가리킴
        self.size = 0

    def no_items(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def insert(self, item):  # 새 항목을 리스트의 첫 노드로 삽입
        n = self.Node(item, None)  # 새 노드를 생성하여 n이 참조
        if self.is_empty():  # 연결 리스트가 empty인 경우
            n.next = n  # 새 노드는 자신을 참조
            self.last = n  # last는 새 노드 참조
        else:
            n.next = self.last.next  # 새 노드는 첫 노드 참조
            self.last.next = n  # last가 참조하는 노드와 새 노드 연결
        self.size += 1

    def first(self):  # 원형 연결 리스트의 첫 항목
        if self.is_empty():
            raise EmptyError('Underflow')
        f = self.last.next
        return f.item

    def delete(self):  # 연결 리스트의 첫 노드를 삭제
        if self.is_empty():
            raise EmptyError('Underflow')
        x = self.last.next
        if self.size == 1:  # 연결 리스트에 노드가 1개인 경우
            self.last = None  # empty 리스트 됨
        else:  # 연결 리스트에 노드가 2개 이상인 경우
            self.last.next = x.next  # last가 참조하는 노드가 두번째 노드를 연결
        self.size -= 1
        return x.item

    def print_list(self):
        if self.is_empty():
            print('리스트 비어있음')
        else:
            f = self.last.next
            p = f
            while p.next != f:  # 첫 노드가 다시 방문되면 루프 중단
                print(p.item, ' -> ', end='')
                p = p.next  # 노드들을 차례로 방문
            print(p.item)

class EmptyError(Exception):  # Underflow시 에러 처리
    pass


s = CList()  # 원형 연결 리스트 객체 생성
s.insert('pear')
s.insert('cherry')
s.insert('orange')
s.insert('apple')
s.print_list()

print('s의 길이 =', s.no_items())

print('s의 첫 항목 :', s.first())

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

print('s의 첫 길이 =', s.no_items())

print('s의 첫 항목 :', s.first())

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

s.delete()
print('첫 노드 삭제 후: ', end='')
s.print_list()

위의 개념과 소스코드는 생능출판의 '파이썬과 함께하는 자료구조의 이해'를 보고 이해하여 정리한 것입니다.

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한조건

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

3. 모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

나의 풀이

import heapq

def solution(scoville, K):
    
    heapq.heapify(scoville)
    c = 0
    
    while True:
        if scoville[0] >= K:
            return c
        elif scoville[0] < K and len(scoville) == 1:
            return -1
        else:
            a = heapq.heappop(scoville) + ( heapq.heappop(scoville) * 2 )
            heapq.heappush(scoville, a)
            c += 1

1. heapq에서 최소힙을 이용합니다.

2. 힙의 첫번째 요소(가장 맵지 않은 스코빌 지수 요소)와 두번째요소(두번째로 맵지 않은 스코빌 지수 요소)를 이용해 새로운 음식을 만들어 힙에 넣습니다.

3. 힙의 첫번째 요소가 K보다 큰 경우 횟수를 출력합니다.

4. 힙의 요소가 1개밖에 남지 않고 첫번째 요소가 K보다 작은 경우 -1을 출력합니다.

5. 2번 과정을 반복하다 3번이나 4번을 충족할경우 해당 값을 리턴하고 종료합니다.

프로그래머스 '더 맵게' : https://programmers.co.kr/learn/courses/30/lessons/42626

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한조건

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.
  
  

입출력 예

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

나의 풀이

def solution(citations):
    for i in range(len(citations),-1,-1):
        c=[j for j in citations if i<= j]
        if i <= len(c):
            return i

1. i보다 큰 논문의 수를 세서 개수가 i보다 많거나 같으면 i를 리턴합니다. 

다른 사람의 풀이

def solution(citations):
        
        citations.sort(reverse=True)
        answer = max(map(min, enumerate(citations, start=1)))
        return answer

프로그래머스 'H-Index' : programmers.co.kr/learn/courses/30/lessons/42747

문제 설명

수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.

송신 탑(높이)수신 탑(높이)

맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.

제한조건

• heights는 길이 2 이상 100 이하인 정수 배열입니다.
• 모든 탑의 높이는 1 이상 100 이하입니다.
• 신호를 수신하는 탑이 없으면 0으로 표시합니다.

입출력 예

입출력 예 설명

입출력 예 #1
앞서 설명한 예와 같습니다.

입출력 예 #2

[1,2,3] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다.
[4,5,6] 번째 탑이 쏜 신호는 3번째 탑이 수신합니다.
[7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

입출력 예 #3

[1,2,4,5] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다.
[3] 번째 탑이 쏜 신호는 2번째 탑이 수신합니다.
[6] 번째 탑이 쏜 신호는 5번째 탑이 수신합니다.
[7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

나의 풀이

def solution(heights):
    answer = [0] * len(heights)
    for i in range(1,len(heights)):
        for j in range(i-1,-1,-1):
            if heights[i] < heights[j]:
                answer[i] = j + 1
                break
    return answer

1. i는 쏘는 신호, j는 받는 신호
2. j가 더 클 경우 answer의 값을 바꾸고 다음으로 넘어갑니다.

프로그래머스 '탑' : https://programmers.co.kr/learn/courses/30/lessons/42588