IT-garden

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한조건

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예

입출력 예 설명

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

나의 풀이

import heapq

def solution(jobs):
    jobs=sorted(jobs, key = lambda x: (x[0],x[1]))
    heap=[] # 힙
    
    t = jobs[0][1] + jobs[0][0] # 전체 시간
    m = t - jobs[0][0] # 요청에서 종료까지
    i = 1
    
    while True:
        if i == len(jobs):
            break
            
        if jobs[i][0] < t: # 작업 중에 요청이 들어오는 것
            heapq.heappush(heap,[jobs[i][1],jobs[i][0]])
            i += 1
        else: # 작업이 끝나고 요청이 들어오는 것
            try: # 실행할 작업이 있는지 확인
                start,h=heapq.heappop(heap) 
                t += start # 전체 시간에 더하기
                m += t - h # 요청에서 종료까지 구해 더하기
            except: # 작업을 수행하고 있지 않은 경우
                t = jobs[i][0] + jobs[i][1] # 시간 새로 설정
                m += jobs[i][1] # 작업 소요시간 더하기 
                i += 1
                
    while True: # heap에 남아있는 것들을 처리하기 위한 무한 반복
        try:
            start,h=heapq.heappop(heap)
            t += start  # 전체 시간에 더하기
            m += t - h # 요청에서 종료까지 구해 더하기
        except:
            break
            
    return m//len(jobs) # 평균 시간

1. heapq을 이용하여 문제를 풀었습니다.
2. 예시를 통해 해당 시점으로부터 처리할 수 있는 작업들 중 가장 작업 소요시간이 작은 작업부터 해야 평균을 가장 줄일 수 있다는 것을 알 수 있습니다.
3. jobs를 오름차순으로 정렬하고 하나의 작업을 수행해 걸린 전체 시간(t)과 요청에서 종료까지 걸린 시간 m을 구합니다.
4-1. 무한 루프를 통해 작업이 진행 중에 새로운 작업이 들어오면 heapq에 넣습니다.
4-2. 그렇지 않을 경우 heapq에 값이 있다면 최소힙을 제거하고 t와 m을 계산합니다. heapq에 값이 없다면 t를 새로 설정하고 t와 m을 계산합니다.
5. 무한 루프가 끝나고 아직 heapq에 값이 있다면 heapq의 값들을 계산하고 요청부터 종료까지 걸린 시간의 평균을 리턴합니다.

프로그래머스 '디스크 컨트롤러' : https://programmers.co.kr/learn/courses/30/lessons/42627

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한조건

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

나의 풀이

def solution(n, computers):
    def dfs(s):
        ch[s]=1
        for i in a[s]:
            if ch[i] == 0:
                dfs(i)

    a=[[] for i in range(n)]
    for i in range(n):
        for j in range(i,n):
            if computers[i][j] == 1:
                a[i].append(j)
                a[j].append(i)
                
    ch=[0]*n
    c=0
    for i in range(n):
        if ch[i] == 0:
            c += 1
            dfs(i)  
    return c

1. computers의 배열을 토대로 각 컴퓨터가 어디에 연결되어 있는지 저장합니다.
2. dfs를 통해 모든 점을 방문하고 네트워크의 개수를 세서 리턴합니다.

프로그래머스 '네트워크' : https://programmers.co.kr/learn/courses/30/lessons/43162

문제 설명

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.

그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.
[1, 1, 2, 3, 5, 8, .]
지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.

타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.

제한조건

• N은 1 이상 80 이하인 자연수이다.
  
  

입출력 예

나의 풀이

def solution(N):
    d=[0]*(N+1)
    d[1]=4
    d[2]=6
    for i in range(3,N+1):
        d[i] = d[i-1] + d[i-2]
    return d[N]

[1, 1, 2, 3, 5, 8 ...]일 때 타일의 개수가 주어지면 각 경우의 둘레를 구했습니다.

n = 1 이면 둘레는 1 * 4 = 4
n = 2 이면 둘레는 (1 * 2) + (2 * 2) = 6
n = 3 이면 둘레는 (3 * 2) + (2 * 2) = 10
n = 4 이면 둘레는 (5 * 2) + (3 * 2) = 16

이를 통해 n이 3이상인 경우 점화식 d[i] = d[i-1] + d[i-2]를 만들었습니다.

프로그래머스 '타일 장식물' : https://programmers.co.kr/learn/courses/30/lessons/43104

크루스칼(Kruskal) 알고리즘은 간선들을 가중치가 증가하는 순서로 정렬하고 가중치가 가장 작은 간선이 사이클을 만들지 않으면 트리 간선으로 선택합니다. 다음 가중치에서도 사이클을 만들지 않으면 트리 간선으로 선택하고 이 과정을 반복해서 정점-1개의 간선을 선택하는 알고리즘입니다.

크루스칼 알고리즘은 최소신장트리(무방향 가중치 그래프에서 간선의 가중치 합이 최소인 것)를 찾는 알고리즘입니다.

크루스칼 알고리즘은 항상 욕심내서 최솟값을 선택하여 가중치의 합이 최소인 것을 찾기 때문에 그리디 알고리즘이라고 할 수 있습니다.

크루스칼 알고리즘에서 간선이 사이클을 만드는지는 union연산과 find연산을 사용합니다. 이는 Union-Find 알고리즘이라고도 부르고 서로소 집합 알고리즘이라고도 합니다. 이 알고리즘은 여러 노드가 존재할 때 두 개의 노드를 선택해 루트를 확인하고 현재 서로 같은 그래프에 속하는지 판별합니다.

상호 배타적 집합들은 1차원 리스트로 표현하며 루트의 리스트 원소에는 루트 자신이 저장되고 루트가 아닌 노드의 원소에는 부모 노드가 저장됩니다. union은 두 개의 집합을 하나의 집합으로 합치는 연산입니다. find는 find연산을 수행하면서 루트까지 올라가는 경로 상의 각 노드의 부모 노드를 루트로 갱신합니다. 이를 경로 압축이라 하는데 이를 실행하면서 수행 시간을 단축시켜 줄 수 있습니다.

find(1)이 수행되면서 1, 3, 7, 10을 거쳤는데 각 노드의 부모노드를 루트로 갱신했습니다.

다음은 크루스칼 알고리즘으로 최소신장트리를 찾는 과정입니다.

크루스칼 알고리즘에서 최소신장트리를 찾기 위해서는 먼저 그래프의 가중치를 기준으로 오름차순으로 정렬합니다.

그리고 가중치에 따른 간선들이 싸이클을 형성하는지 하나씩 확인합니다.

정점 4와 5를 이어주는 첫번째 간선을 선택합니다.

정점 5와 6을 이어주는 두번째 간선을 선택합니다.

정점 3와 5를 이어주는 세 번째 간선을 선택합니다.

정점 1와 3을 이어주는 네 번째 간선을 선택합니다.

정점 4와 6을 선택할 경우 정점 4, 5, 6이 사이클을 형성하기 때문에 선택하지 않습니다.

정점 2와 4을 이어주는 여섯 번째 간선을 선택합니다.

이를 통해 모든 정점이 연결되어 최소신장트리를 이룹니다.

간서의 가중치의 값은 1 + 2 + 3 + 5 + 9 = 20입니다.

크루스칼 알고리즘의 파이썬 코드입니다.

graph=[(1,2,13),(1,3,5),(2,4,9),(3,4,15),(3,5,3),(4,5,1),(4,6,7),(5,6,2)]
graph.sort(key = lambda x: x[2]) # 가중치로 간선 정렬 (정점1, 정점2, 가중치)

mst=[]
n=6 # 정점 개수
p=[0] # 상호배타적 집합

for i in range(1,n+1):
    p.append(i) # 각 정점 자신이 집합의 대표

def find(u):
    if u != p[u]:
        p[u] = find(p[u]) # 경로압축
    return p[u]

def union(u, v):
    root1 = find(u)
    root2 = find(v)
    p[root2] = root1 # 임의로 root2가 root1의 부모

tree_edges = 0 # 간선 개수
mst_cost = 0 # 가중치 합

while True:
    if tree_edges == n-1:
        break
    u, v, wt =graph.pop(0)
    if find(u) != find(v): # u와 v가 서로 다른 집합에 속해 있으면
        union(u, v)
        mst.append((u, v)) 
        mst_cost += wt
        tree_edges += 1

# 출력>>최소신장트리:  [(4, 5), (5, 6), (3, 5), (1, 3), (2, 4)]
print('최소신장트리: ',mst)

# 출력>>최소신장트리 가중치: 20
print('최소신장트리 가중치:', mst_cost)

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한조건

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

입출력 예 설명

입출력 예 #1
다음과 같이 5가지 방법이 있다.

나의 풀이

def solution(n):
    d=[0]*(n+1)
    d[1]=1
    d[2]=2
    for i in range(3,n+1):
        d[i] = (d[i-1] + d[i-2]) % 1000000007
    return d[n]

프로그래머스 '2 x n 타일링' : https://programmers.co.kr/learn/courses/30/lessons/12900

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한조건

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

나의 풀이

def solution(N, number):
    possible_set = [0,[N]] 
    if N == number: 
        return 1
    for i in range(2, 9): 
        case_set = [] 
        case_set.append(int(str(N)*i))
        for i_half in range(1, i//2+1):
            for x in possible_set[i_half]:
                for y in possible_set[i-i_half]: 
                    case_set.append(x+y)
                    case_set.append(x-y)
                    case_set.append(y-x)
                    case_set.append(x*y)
                    if y !=0:
                        case_set.append(x/y)
                    if x !=0:
                        case_set.append(y/x)
            if number in case_set:
                return i
            possible_set.append(case_set) 
    return -1

다이나믹 문제에서 문제를 어떤식으로 풀어야 할지 몰라 많이 시간을 사용했던 문제입니다.

프로그래머스 'N으로 표현' : https://programmers.co.kr/learn/courses/30/lessons/42895