Home

[프로그래머스] 가장 큰 정사각형 찾기

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12905 2. 풀이 dp를 이용하여 문제를 해결해야 합니다. dp_map에 현재 인덱스에서 가능한 최대 정사각형의 크기를 기록해놓습니다. 각 칸을 모두 돌면서 왼쪽, 위, 왼쪽 대각선 위를 살펴보고 해당 값에서 가장 작은 값 + 1로 갱신합니다. 이는 직접 그려보면서 이해하면 더 쉬운데, k 크기의 정사각형을 현재 위치에서 만들기 위해서는 위의 3개의 위치에서 k-1 이상의 값을 가져야 하기 때문입니다. … … ...

Read more

[프로그래머스] 최솟값 만들기

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12941 2. 풀이 2.1. dfs 를 사용한 시간 초과 풀이 특별한 방법이 떠오르지 않아서 dfs를 사용한 완전탐색을 이용하였으나 시간 초과되었습니다. 트리의 높이가 1000 라서 시간을 극복할 수 없습니다. answer = 98765432100 N = 0 def dfs(depth, A, B, value): global is_visited, answer if value >= answer: return if depth == N: answ...

Read more

[프로그래머스] 다리를 지나는 트럭 풀이

1. 문제 https://www.welcomekakao.com/learn/courses/30/lessons/42583 2. 풀이 시뮬레이션으로 문제를 해결하면 됩니다 다리 사이즈, 대기 트럭 만큼 deque 생성을 해줍니다. 다리를 지나고 있는 트럭이 존재하지 않을 때 까지 while 문을 수행합니다. 대기열에 트럭이 있고, 다리를 지나고 있는 트럭이 없는 경우에 해당 숫자는 0으로 채워집니다. 시간을 1씩 증가시키면서, 다음 들어올 트럭이 다리에 있는 트럭의 무게의 합과 더하여 무게를 초과하지 않으면 다리에 있는 차에 넣고 아닌 경우에는 다리에 들어오지 ...

Read more

[프로그래머스] 카펫 풀이

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42842 2. 풀이 전체 직사각형과 노란 직사각형의 가능한 세로 크기를 모두 구한다. 하나씩 꺼내보면서 가로와 세로에 각각 -2 된 값보다 작거나 같은 경우(내부에 속하려면 전체 격자 크기의 가로, 세로 크기 -2보다 작거나 같아야 하기 때문)를 구해서 return import math def make_grid_num(rec_grid_num, start_idx): # 가능한 직사각형의 세로 크기를 모두 구한다. sizes = [] half = (int)(math.sqrt(rec_...

Read more

[프로그래머스] 위장 풀이

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42578 2. 풀이 해시를 사용하면 손쉽게 풀 수 있는 문제입니다. 딕셔너리에 옷 종류를 key로, 옷 이름은 집합 value에 넣어줍니다. 모든 값을 넣고 옷 종류마다 +1 을 해준 값을 정답해 곱해줍니다. (+1은 옷을 안 입는 경우입니다.) -1 한 값을 정답으로 해줍니다(모두 벗은 경우) def solution(clothes): answer = 1 spy_dic = {} for wear, kind in clothes: # 딕셔너리에 옷 종류를 key로 옷 이...

Read more

[프로그래머스] 큰 수 만들기 풀이

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42883 2. 풀이 2.1. 시간 초과 풀이 만들어야 하는 자리 수는 number의 길이 - 빼야할 숫자 k 입니다. 숫자를 결정할 때 가장 높은 자리 숫자부터 정해야 합니다. 높은 자리 숫자는 현재 string 에서 최소한 빼야할 숫자 k - 1개 만큼이 뒤에 포함되어 있어야 합니다. 예를 들어, ‘2223454’ 에서 4개의 숫자를 빼야 되면 자리 수는 3자리이고, 첫 숫자는 뒤에 최소한 4 - 1 = 3개 만큼의 숫자 ‘454’ 앞에 있어야 하기 때문에 ‘222...

Read more

[프로그래머스] 피보나치 수 풀이

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12945 2. 풀이 배열을 하나씩 증가시키면서 이전 수 2개를 더해주고 return 해주는 간단한 문제입니다. def solution(n): F = [0, 1] for i in range(2, n+1): F.append((F[i-1] + F[i-2]) % 1234567) return F[n]

Read more

[프로그래머스] 전화번호 목록 풀이

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42577 2. 풀이 2.1. 딕셔너리(해쉬)를 이용한 풀이 prefix_dic이라는 dictionary 에 모든 단어를 집어 넣습니다. for문을 돌면서 문자 길이 -1 까지 체크를 하면서 dictionary에 해당 문자열이 존재하는지 확인합니다. 문자열의 길이가 20이 최대이기 때문에 속도에 문제가 없는 소스코드입니다. def solution(phone_book): answer = True prefix_dic = {} for x in phone_book: ...

Read more

What is mkdir -p option on linux?

When we use mkdir -p option, system automatically creates an intermediate directory that does not exist. If you use -p, you don’t need to make intermediate directory. Intermediate directories are created automatically. This is very useful. # below command is not success because there is no middle directory(f1/f2) $ mkdir f1/f2/f3 mkdir: f1/f2:...

Read more

[프로그래머스] 더 맵게

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42626 2. 풀이 2.1. PriorityQueue를 이용한 시간초과 풀이 PriorityQueue 를 사용하여 문제를 해결한 풀이입니다. 문제 해결 방법은 아래와 같습니다. PriorityQueue 에 남은 원소가 2개 이상일 경우에 계속해서 로직을 수행합니다. 가장 적은 2개를 뽑아서 2개 다 0이 아닌지 확인하고, 다음 값을 PriorityQueue에 집어 넣습니다. while 문이 끝나고 나서 P...

Read more