pjaehyun의 개발일지

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42895

문제 설명

문제풀이 코드

def solution(N, number):
    answer = -1
    if N == number:
        return 1
    
    dp = [[] for _ in range(9)]
    
    # 최솟값이 8보다 클 수 없기때문에 1개부터 8개까지 N으로 만들 수 있는 모든 수를 구한다.
    for i in range(1, 9):
    	# 숫자 이어 붙이기
        dp[i].append(int(str(N) * i))
        for j in range(1, i):
            for num1 in dp[j]:
                for num2 in dp[i - j]:
               	    # 사칙연산
                    dp[i].append(num1 + num2)
                    dp[i].append(num1 * num2)
                    dp[i].append(num1 - num2)
                    if num2 != 0:
                        dp[i].append(num1 // num2)
        if number in dp[i]:
            answer = i
            break
    return answer

동적 계획법으로 문제 풀이

1. N = 5일 때, 5를 만들기 위해서는 5가 1개 있으면 되기 때문에  dp[1] = [5]가 된다. 

2. 5가 2개 있으면 만들 수 있는 수는 [0, 1, 10, 25, 55]이다. 

3. 5가 3개 있으면 만들 수 있는 수는[0, 2, ... 555]가 있다.

4. 이를 통해 알 수 있는 것은 dp[3] = dp[1] ㅇ dp[2], dp[2] ㅇ dp[1]이 된다. (ㅇ 는 사칙연산을 표현)

5. dp[4] = dp[1] ㅇ dp[3], dp[2] ㅇ dp[2], dp[3] ㅇ dp[1]이 되게 된다.

6. 이를 통해 점화식을 도출하면, dp[i] = dp[j] ㅇ dp[i-j] 가 된다.

7. 이제 반복문을 돌면서 1개부터 9개 까지 N으로 만들 수 있는 모든 수들을 구하여 찾고있는 수가 dp에 들어있을 때 i값을 반환하면 된다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42898

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

입출력 예

m	n	puddles	return
4	3	[[2, 2]]	4

 

입출력 예 설명

문제풀이 코드

def solution(m, n, puddles):
    dp = [[0] * (m+1) for _ in range(n+1)]
    dp[1][1] = 1
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if [j, i] in puddles:
                continue
            dp[i][j] += (dp[i-1][j] + dp[i][j-1]) % 1000000007
    return dp[n][m]

문제의 최단경로를 보고 bfs로 접근했다가 실패...

오른쪽과 아래로만 내려갈 수 있으면 이동할 수 있는 모든 경로가 최단거리기 때문에 동적계획법으로 풀이 변경

위 그림을 보고 점화식을 유추할 수 있다 

현재 위치가 dp[x][y]일 때, 점화식은

dp[x][y] = dp[x-1][y] + dp[x][y-1]가 된다.

1. dp배열을 루프돌면서 모든 위치에 값을 구해준다. 단, 길이 물에 잠겼을 때는 continue를 통해 dp[i][j]를 초기화하지 않는다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42627

문제 설명

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

예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

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

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

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

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

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

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

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

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

 

제한 사항

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

문제풀이 코드

import heapq

def solution(jobs):
    start, end = -1, 0
    result = 0
    
    hq = []
    i = 0
    while i < len(jobs):
        for job in jobs:
        	# 요청시간이 start와 end 사이에 있는 작업을 힙에 삽입
            if start < job[0] <= end:
            	# 삽입할 때는 (작업시간, 요청시간)으로 삽입한다. 
                # 작업시간이 짧은 순으로 힙에서 뽑아야하기 때문
                heapq.heappush(hq, (job[1], job[0]))
        if hq:
            current = heapq.heappop(hq)
            start = end
            end += current[0]
            
            # 현재 작업이 요청에서 작업까지 걸린 시간을 result에 더해준다.
            result += end - current[1]
            i += 1
        else:
            end += 1
    return result // len(jobs)

힙을 사용한 문제 풀이

1. 현재 대기하고있는 작업들 중 작업시간이 가장 짧은 순서로 작업을 실행시켜야 한다.

2. 작업들 중 실행시킬 수 있는 작업들을 힙에 삽입한다.

3. 삽입할 땐, 작업시간으로 힙에서 빼올 수 있도록 (작업시간, 요청시간)으로 바꿔서 넣는다

4. 현재 실행시킬 수 있는 작업이 다 삽입되면 힙에서 작업시간이 가장 작은 작업을 pop한다

5. start, end, result를 차례대로 변경한 후 반복문을 진행한다.

6. 반복문이 종료되면 요청에서 작업까지 걸린 시간의 평균을 반환한다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43164

문제 설명

문제풀이 코드

from collections import defaultdict

def solution(tickets):
    tickets_dict = defaultdict(list)
    result = []
    
    # 공항에서 출발하여 도착할 수 있는 모든 도착지를 딕셔너리 형태로 관리
    for start, end in tickets:
        tickets_dict[start].append(end)
    
    # 방문 순서는 알파벳 순으로 하기때문에 정렬해준다
    for key in tickets_dict.keys():
        tickets_dict[key].sort()
        
    def dfs(start):
        while tickets_dict[start]:
            end = tickets_dict[start].pop(0)
            dfs(end)
        
        # 출발지에서 더이상 갈곳이 없을 때 결과에 넣어준다.
        # 방문 순서가 역순으로 쌓임
        if not tickets_dict[start]:
            result.append(start)
    
    dfs("ICN")
    return result[::-1]

1. 출발지에서 갈 수 있는 모든 도착지를 딕셔너리 형태로 만든다.

2. 출발지에서 갈 수 있는 모든 도착지를 정렬한다. (방문은 알파벳순으로 해야된다.)

3. 출발지에서 갈 수 있는 모든 도착지를 순서대로 재귀호출한다.

4. 출발지에서 더 이상 갈 수 있는곳이 없다면 결과에 추가해준다.

5. 출발은 "ICN"에서 하니까 dfs("ICN")으로 호출한다.

6. 도착지가 없는 곳 부터 결과에 들어오기 때문에 result를 뒤집어서 반환한다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

문제풀이 코드

첫번째 풀이(완전탐색)

from itertools import permutations
def solution(k, dungeons):
    dungeons = list(permutations(dungeons))
    result = [0] * len(dungeons)
    for i in range(len(dungeons)):
        fatigue = k
        for j in range(len(dungeons[i])):
            if dungeons[i][j][0] <= fatigue:
                result[i] += 1
                fatigue -= dungeons[i][j][1]
    return max(result)

1. dungeons를 탐색할 수 있는 모든 방법을 구한다

2. 모든 방법들을 탐색하여 각 방법별로 탐색 가능한 던전의 수를 구하여 결과 배열에 넣어준다

3. 결과에 담긴 값 중 가장 큰 값을 반환한다

두번째 풀이(백트래킹)

answer = 0
visited = []

def dfs(k, count, dungeons):
    global answer
    
    if count > answer:
        answer = count
    
    for i in range(len(dungeons)):
        if k >= dungeons[i][0] and not visited[i]:
            visited[i] = True
            dfs(k - dungeons[i][1], count + 1, dungeons)
            visited[i] = False

def solution(k, dungeons):
    global visited
    visited = [False] * len(dungeons)
    dfs(k, 0, dungeons)
    return answer

1. 백트래킹 기법으로 재귀함수가 끝나면 visited[i]를 False로 바꾸어주면서 모든 경우를 탐색하여 가장 큰 값을 반환하도록 한다

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12900

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

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

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

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

제한사항

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

입출력 예

문제풀이 코드

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

dp를 이용한 풀이

1. 위 규칙을 보고 점화식을 세우면 (n-2)의 경우의 수 + (n-1)의 경우의 수 = n의 경우의 수로 볼 수 있다

2. 점화식을 구현해 문제를 해결할 수 있다

* 위 규칙은 피보나치 수열과 비슷

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17680

캐시

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력형식

• 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

입출력 예제

문제풀이 코드

def solution(cacheSize, cities):
    arr = []
    answer = 0
    for c in cities:
        if c.lower() not in arr:
            answer += 5
            arr.append(c.lower())
            if len(arr) > cacheSize:
                arr.pop(0)
        else:
            answer += 1
            arr.pop(arr.index(c.lower()))
            arr.append(c.lower())
    return answer

1. 알파벳은 대소문자 구분없이 모두 소문자로 취급한다

2. 도시가 배열에 들어가있지 않은경우 cache miss로 answer + 5를 해주고 도시를 배열에 추가

3. 배열의 크기는 cacheSize보다 커질 수 없으므로 커지면 첫번째 들어온 원소를 빼준다

4. 도시가 배열에 들어가있는 경우 cache hit로 answer + 1을 해준다

5. 배열에 들어가있는 도시를 pop하고 마지막에 추가해준다.

6. 반복문이 종료되면 answer는 총 실행시간이 된다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12914

문제풀이 코드

def solution(n):
    if n == 1:
        return 1
    dp = [0 for x in range(n+1)]
    dp[1], dp[2] = 1, 2
    for i in range(3, len(dp)):
        dp[i] = (dp[i-1] + dp[i-2]) % 1234567
    return dp[n]

1. dp 문제

2. 피보나치 수열을 사용하여 문제 풀이 가능