코딩테스트/프로그래머스

[프로그래머스] Level 2 - 3xn 타일링 (Python)

https://programmers.co.kr/learn/courses/30/lessons/12902 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr ✅ Solution n이 홀수일 땐 항상 답은 0이다. f(2) = 3, f(4) = 11, f(6) = 41, f(8) = 153 f(n) = f(n-2) * 4 - f(n-4) f(n-2) * 4 보다 f(n-4)가 더 크면 음수가 나오기 때문에 모듈러 분배 법칙을 이용하여 처리한다. ✅ Code def solution(n): if n % 2 == 1: return 0 dp = [3, 11] for i in range(2, n//2 + 1, 1): dp.append(((dp[i-1] * 4 % 1000000007) - dp[i-2]..

[프로그래머스] Level 2 - 구명보트 (Python)

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr ✅ Solution people을 내림차순으로 정렬한다. 가장 큰 요소(people[0]) 을 보트에 추가하고, 제일 작은 요소부터 무게를 넘지 않을 때까지 추가한다. len(people) >=2 일 때 반복 그리고 people에 요소가 남아있다면 보트 하나가 추가로 필요한 것이므로 answer += 1 해준다. ✅ Code from ..

[프로그래머스] Level 2 - 영어 끝말잇기 (Python)

https://programmers.co.kr/learn/courses/30/lessons/12981 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0] programmers.co.kr ✅ Solution words를 돌면서 usedWords에 있거나 앞사람의 마지막 단..

[프로그래머스] Level 2 - 전력망을 둘로 나누기 (Python)

https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr ✅ Solution 전선을 입력받아 tree를 만들어준다. 양뱡향이므로 전선으로 연결된 두 개의 노드에 모두 정보를 추가해준다. 전선 하나를 끊어서 BFS를 돌리고, 각각의 연결된 노드수(송전탑의 수)를 받아온다. 끊을 전선을 BFS에 넘기고 queue에 새로운 노드를 추가할 때, 시작 노드와 추가할 노드가 모두 해당 전선으로 연결된 것이 아니라는 조건을 추가한다..

[프로그래머스] Level 2 - 피로도 (Python)

https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr ✅ Solution 완전 탐색과 그래프를 이용한 방법 두 가지가 있었다. 1. 완전 탐색 permutations로 가능한 조합을 모두 구한 후, answer값을 비교하며 큰 값을 리턴한다. 2. BFS k와 빈 배열로 deque 배열을 만든다. k는 남아있는 피로도, []은 방문한 던전을 의미한다. 던전의 길이만큼 반복문을 돌면서 만약 k가 최소 필요 소..

[프로그래머스] Level 2 - 2개 이하로 다른 비트 (Python)

https://programmers.co.kr/learn/courses/30/lessons/77885 코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr ✅ Solution 숫자가 짝수인 경우, 항상 가장 마지막 비트는 0이다. 따라서 마지막 비트를 0에서 1로 바꿔준 값이 답이기 때문에 숫자+1 값을 answer에 넣어준다. 숫자가 홀수인 경우, 가장 뒤쪽에 있는 0을 1로 바꿔주고 그다음 비트를 0으로 바꿔주면 된다. 예를 들어 7(0111) 은 가장 뒤쪽에 있는 0을 1로 바꿔주고 그다음 비트를 0으로 바꿔준다. 즉, 11(1011)이 답이다. 그리고 9(1001) 은 1001 -> 1011 -> 1010 으로 10이 답이다. ✅ Code def solution(numbers..

[프로그래머스] Level 2 - 다리를 지나는 트럭 (Python)

https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr ✅ Solution [0] * bridge_length로 bridge 배열을 만들어준다. bridge 배열의 길이가 0보다 클 때, 맨 앞의 요소를 bridge배열에서 popleft(), total_weight에서 빼주고 answer에 1을 더해준다. 위 과정은 맨 앞의 요소를 빼주면서 한 칸씩 앞으로 전진시키는 것 대기 트럭이 있고 ..

[프로그래머스] Level 2 - 위장 (Python)

https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr ✅ Solution defaultdict을 이용하여 옷을 종류별로 구분해준다. 종류별로 0개 혹은 1개를 선택할 수 있으므로 각 종류별 길이 + 1을 한 뒤 곱한다. headgear : yellow_hat, green_turban / eyewear: blue_sunglasses -> (2+1) * (1 + 1) = 6 근데, 문제에서 최소 1개의 의상을 입는다고 했으니 모두 0개를 고르는 한개의 경우를 빼주고 리턴한다. ✅ Code from collections import defaultdict def solution(clothes): answer..