[프로그래머스] 다리를 지나는 트럭 / 큐(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

[NLP] BoW(Bag of words)

Bag of Words 단어 및 문서를 숫자형태로 나타내는 가장 간단한 기법으로서 TextMining 분야에서 딥러닝 기술이 적용되기 이전에 많이 활용되던 방식이라고 한다. Step 1. Constructing the vocabulary containing unique words Example sentences: "John really really loves this movie", "Jane really likes this song" 이 문장에서 really와 this는 중복되기에 한 번만 포함하면 된다. Vocabulary: {"John", "really", "loves", "this", "movie", "Jane", "likes", "song"} Step 2. Encoding unique words ..

→2021.02.17

[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

[BOJ] 백준 1654 랜선 자르기 / 이분탐색

💭 문제 이해 영식이가 가지고 있는 K개의 랜선을 N개 이상의 동일한 길이의 선들로 만들기 위해 자를 길이를 찾아야하는 문제이다. 랜선의 길이는 최대 231-1로 완전탐색을 하게 되면 시간초과가 발생하게 된다. 이분탐색을 통해서 무리 없이 해결할 수 있는 문제이다. 구현 언어: Python import sys from collections import Counter r = sys.stdin.readline def binary_search(target_cnt: int, lines: list) -> int: result = 0 left = 1 right = max(lines) while left

→2021.02.09