[프로그래머스] 카펫 / 완전 탐색(Brute-force Search)

💭 문제 이해 갈색 타일의 개수와 노란색 타일의 개수가 입력으로 주어질 때, 전체 카펫의 가로 길이와 세로 길이를 구하는 문제이다. 수식으로 정리해본다면, 1. 가로를 테두리를 포함해서 \(x+2\) 로 표현하고, 세로는 테두리를 포함하여 \(y+2\) 로 표현한다. 2. 위 수식을 기준으로 전체 칸 수는 \((x+2)(y+2) = brown + yellow\) 로 표현할 수 있다. 3. 노란 부분은 \(xy = yellow\) 로 표현할 수 있다. 4. 전체 칸 수를 나타내는 수식을 전개하면 \(xy+2x+2y+4=brown+xy\) 가 되고, 이를 정리하면 \(x+y = \frac{brown-4}{2}\) 라는 관계가 성립된다. 즉, \(y = \frac{brown-4}{2}-x\) 관계를 만족하며 ..

→2021.03.18

[프로그래머스] 소수 찾기 / 완전 탐색(Brute-force Search)

💭 문제 이해 한 자리의 숫자들이 나열된 문자열을 조합해서 만들 수 있는 소수의 갯수를 구하는 문제이다. 파이썬의 기본 모듈인 itertools.permutations를 이용하여 모든 경우를 구하고, 소수 판별은 숫자 범위가 0~9로 적으므로 2~n-1까지 나눠보면서 직접 찾아냈다. 구현 언어: Python from itertools import permutations # 소수 판별 함수 def is_prime_number(num: int) -> bool: if num < 2: return False for i in range(2, num): if num % i == 0: return False return True def solution(numbers): answer = set() # 중복되지 않는 모..

→2021.03.17

[프로그래머스] 다리를 지나는 트럭 / 큐(Queue)

💭 문제 이해 트럭이 순서대로 대기하고 있고, 다리가 견딜 수 있는 무게 내에서 최대한 빠르게 모든 트럭이 통과하는 시간을 구하는 문제이다. 트럭들이 대기하다가 순서대로 지나가고, 다리 또한 한 방향으로 지나가기 때문에 Queue가 떠올랐다. 트럭이 지나가는 다리를 bridge라는 이름으로 queue(deque 사용)를 선언하고 대기 중인 트럭들을 waiting이라는 이름으로 queue를 선언했다. 대략적인 코드 구조는 다음과 같다. 0. 0초부터 1초 씩 증가하며 시간을 기록한다. 1. bridge가 비어있지 않다면 지금 시점에 지나가야하는 트럭은 dequeue 시킨다. (다리를 빠져나간다.) 2. bridge와 waiting에 남은 트럭이 없다면 현재 시간을 리턴함으로 반복문을 종료시킨다. (모든 차..

→2021.03.12

[프로그래머스] 가장 큰 수 / 정렬

💭 문제 이해 정수를 붙였을 때 가장 큰 수가 되도록 만들어주어야 한다. 모든 조합을 구해서 최대값을 팩토리얼 연산으로 구한다면, 여기서 유의할 점은 최대 10만 개의 입력이 들어올 수 있다는 점이다. 그렇다면 먼저 조건에 맞게 정렬을 해주고 Join 하는 방법도 있다. 서로 다른 자리의 숫자를 합쳤을 때 최대가 되도록 하기 위해서, 문자열 대소비교의 특징을 사용했다. 문자열은 대소비교를 할 때, 첫 자리가 큰 수를 찾아내고 숫자가 같다면 길이가 긴 것을 큰 것으로 인정한다. 숫자는 최대 1000 까지 가능하므로 각 숫자를 문자열로 바꾸어주고 3배로 연장하여 대소비교를 수행하면 조건에 맞게 정렬할 수 있게 된다. 구현 언어: Python def solution(numbers): # 문자열은 첫 글자부터 ..

→2021.03.11

[프로그래머스] 도둑질 / 동적 계획법(Dynamic-Programming)

💭 문제 이해 두 수를 인접하지 않게 선택하여 최대 합을 구하는 문제이다. 마을이 원형구조이므로 1, 2, 3, 4번 집이 있을 때, 1번은 2번, 4번과 인접해있다. 따라서 1번을 선택할 때의 경우(2, 4번은 선택불가)와 1번을 선택하지 않을 경우(1번만 사용불가)를 나누어서 두 결과값 중 최대를 반환하면 된다. 구현 언어: Python def solution(money): # 3 1 4 7 2 5 case1 = [i for i in money] case2 = [i for i in money] # 첫 번째를 선택하는 경우 case1[1], case1[-1] = case1[0], 0 # 첫 번째를 선택하지 않는 경우 case2[0] = 0 for i in range(2, len(money)): case..

→2021.03.11

[프로그래머스] 등굣길 / 동적 계획법(Dynamic-Programming)

💭 문제 이해 격자를 오른쪽과 아래쪽으로 이동하며 최단 경로의 수를 측정하는 문제이다. DP로 풀 수 있고, 물이 있는 부분을 어떻게 체크하느냐가 포인트인 문제이다. 구현 언어: Python def solution(m, n, puddles): maps = [[0]*(m+1) for _ in range(n+1)] dp = [[0]*(m+1) for _ in range(n+1)] # 물 체크 for pud in puddles: maps[pud[1]][pud[0]] = -1 dp[1][0] = 1 # 시작지점은 1 for i in range(1, n+1): for j in range(1, m+1): if maps[i][j] == -1: dp[i][j] = 0 else: dp[i][j] = (dp[i-1][j]..

→2021.03.11

[BOJ] 백준 1535 안녕 / 동적 계획법(Dynamic-Programming)

💭 문제 이해 세준이 체력이 최대 100이므로 숫자를 증가시키면서 해당 체력내에 얻을 수 있는 최대 기쁨을 갱신한다. 구현 언어: Python import sys r = sys.stdin.readline n = int(r()) hp_loss = list(map(int, r().split())) pleasure = list(map(int, r().split())) dp = [[0]*101 for _ in range(n+1)] for i in range(1, n+1): for j in range(100): if j < hp_loss[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-hp_loss[i-1]] + pleasure[i-1..

→2021.03.11

[BOJ] 백준 2512 예산 / 이분탐색

💭 문제 이해 국가예산이 주어지고, N개의 지방에서 예산 요청이 주어질 때 정해진 예산 내에서 최대 얼마까지 배정할 수 있는 지 계산하는 문제이다. 내용은 다르지만 큰 틀은 이전에 풀었던 이분탐색 문제들과 다를 바가 없다. 최소 예산인 1부터 최대 예산인 max(지방의 예산요청들) 사이에서 이분탐색을 하며 그 값을 찾아내면 된다. 구현 언어: Python import sys r = sys.stdin.readline def binary_search(requests: list, budget: int) -> int: result = 0 left = 1 right = max(requests) while left = mid else req for req in requests) if total_sum int: re..

→2021.02.11

[BOJ] 백준 1764 듣보잡 / 이분탐색

💭 문제 이해 제목이....ㅋ 암튼 전형적인 방법으로 풀면 이분탐색이지만, 파이썬의 장점을 잘 살리면 이분탐색보다 실행속도도 더 빠르고 간단하게 풀어낼 수 있다. 풀이 방법은 다음과 같다. 1. 이분탐색 2. Set 자료구조와 in 연산자 3. Set의 교집합을 구할 수 있는 & 연산자 4. Set과 intersection 메소드를 이용한 교집합 연산 실행속도는 4 > 3 >= 2 > 1 순으로 빠르다. 구현 언어: Python 1. 이분탐색 import sys r = sys.stdin.readline def binary_search(d_list: list, b_list: list) -> list: result = [] d_list.sort() for b in b_list: left = 0 right =..

→2021.02.11

[BOJ] 백준 10816 숫자 카드 2 / 이분탐색

💭 문제 이해 이전에 풀었던 숫자 카드 문제와 거의 비슷하다. 주어진 숫자 입력들이 상근이가 가진 숫자 카드에 있는지 여부를 체크하는 문제였다면, 이 문제는 상근이가 그 숫자들을 몇 개 가지고 있는 지도 체크해야 한다는 점이다. Python의 Counter를 이용해서 상근이의 숫자 카드를 Key 값으로 카드번호, Value 를 카드 개수로 하는 딕셔너리를 생성했다. 그리고 입력으로 들어온 숫자가 Counter 객체에 존재한다면 Value를 출력하고, 없다면 0을 출력하게 구현했다. 구현 언어: Python import sys from collections import Counter r = sys.stdin.readline answer = [] n, my_card = int(r()), Counter(map..

→2021.02.09