[프로그래머스] 카펫 / 완전 탐색(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

[프로그래머스] 가장 먼 노드 / 최단 경로, 다익스트라

💣 문제 이해 한 출발 정점에서 다른 모든 정점으로의 최단 경로 이동 비용을 계산하는 문제였다. 각 노드로 이동하는 최소 비용을 계산하여 그중 최대를 구한 후, 동일한 비용을 지불하는 경로의 수를 카운트 했다. 이 문제는 다익스트라 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; const int MAX = 20001; const int INF = 1e9; int dist[MAX] = {0, }; int solution(int n, vector edge) { int max_cost = 0; int result = 0; priority_queuepq; // 비용, 노드번호 vectornodes[n+1]; // 각..

→2020.11.21