🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42583# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법트럭을 큐(다리)에 차례로 진입시키는데, 이때 시간(second)을 기준으로 한다.시간을 기준으로 총 두 가지의 작업을 수행하며, total_weight 변수를 통해 큐(다리)의 전체 무게를 체크한다.큐에서 0번째 트럭이 다리를 건넜는지 확인한다.만약 다리를 건넜다면, 큐에서 해당 트럭을 삭제한다. (total_weight에서 해당 트럭의 무게도 뺀다)경과 시간 = 현재 시간 - 진입 시간을 확인하여 트럭이 다리..
Algorithm/Programmers
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법lose_list[i] → i번 선수에게 진 선수들의 리스트와 win_list[i] → i번 선수에게 이긴 선수들의 리스트를 각각 구한다.즉, 단방향 그래프 형식으로 이긴 선수들의 그래프와 진 선수들의 그래프 관계를 나타냈다. i번 선수에게 이긴 선수들과 i번 선수에게 진 선수들을 모두 구한다.만약 순위를 매길 수 있다면, lose_list[i]의 수 + win_list[i]의 수는 n-1일 것이다. 이를 구하기 ..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법모든 노드의 가중치가 동일했기 때문에 BFS를 사용하여 최단 거리를 구했다.1번 노드에서 모든 노드까지의 최단 거리를 구하고, 그 중 가장 긴 거리를 구한 뒤, 거리 배열에서 가징 긴 거리의 개수를 구했다. 😎 내 코드from collections import dequedef BFS(v, graph, visited): distances = [0 for _ in range(len(visited))] ..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법DP의 top-down 방식으로 풀었다.triangle을 모두 탐색하면서 값을 업데이트 해나갔다. 현재 위치까지 도달하는 모든 경로 중 최댓값을 저장해야 한다. 따라서 위의 칸의 대각선 두 값 중 더 큰 값을 선택하여 더한다. 만약 대각선에 값이 존재하지 않는다면, 이는 삼각형의 범위를 벗어난 것이므로 이를 따로 처리해야 한다. 점화식은 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (i>=1, ..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42898# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🚀 시행착오def solution(m, n, puddles): # m: 열, n: 행 answer = 0 dict = {} # key: 경로, value: 경로 개수 visited = [[False] * (m+1) for _ in range(n+1)] dx = [0, 1] # 아래쪽, 오른쪽 dy = [1, 0] def DFS(y, x, cnt): visi..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746# 💡 접근법주어진 숫자 리스트를 이어붙여 만들 수 있는 모든 경우의 수를 탐색하면 시간 초과가 발생한다. 따라서 문자열 정렬을 활용해 가장 큰 수를 만들어야 한다. 문자열 정렬의 특성- 문자열 정렬은 숫자의 크기나 자릿수와 상관없이 문자 순서대로 사전식 정렬된다.- 문자열의 길이가 다를 때, 더 짧은 문자열은 사전식 정렬에서 먼저 온다. ex) "1"과 "10"을 비교하면, "1"이 "10"의 부분 문자열이므로 "1"이 "10"보다 앞에 정렬된다. 올바른 정렬을 수행하기 위해 자릿수를 맞춰서 비교해야 한다.문자열 정렬은 사전식 정렬로 수행되므로, 이는 [1, 10] ..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42584 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법언제 주식가격이 떨어졌는지 알기 위해서는 타겟 하나에 대해 이후의 주식 가격을 매번 비교해야 한다. 즉, 가격이 떨어지지 않는 기간(초 단위)을 각각 계산한다. 하지만 이러한 접근법으로 구현할 경우 시간 복잡도는 O(N²)이다. 😎 내 코드def solution(prices): answer = [] for i, p in enumerate(prices): seconds = 0 ..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 👀 배운 코드1. DFS 기반 코드재귀 방식으로 모든 경우의 수에 대한 계산을 수행한다.def solution(numbers, target): global answer answer = 0 def DFS(i, sum): global answer if i == len(numbers): if sum == target: answer += ..
