전체 글

🗂️ 문제링크: https://www.acmicpc.net/problem/1149 💡 접근법모든 집에 대해 비용을 적은 것부터 많은 것으로 정렬한 뒤, 비용이 적은 집에 대해서 우선적으로 처리하는 방식이다.즉, 현재 순간에서 가장 비용이 적은 것을 선택한다. 이때 문제에서 제시한 바와 같이, 이전 집과는 같은 색을 칠하지 않는 조건을 처리한다. 😎 내 코드import sysfrom collections import dequeN = int(sys.stdin.readline())house_cost = []RGB = ["R", "G", "B"]for i in range(N): costs = list(map(int, sys.stdin.readline().split())) for c, r in z..

🗂️ 문제링크: 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 += ..

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법progresses 리스트 자체를 큐로 사용한다. 이때 while 문을 통해 진도(progress)에 작업 속도(speed)를 계속해서 더해간다.만약 첫 번째 요소의 진도율이 100% 이상일 경우, 이는 배포가 가능한 작업이 된다. 따라서 첫 번째 요소 이후에도 배포가 가능한 작업이 있는지 카운팅하고, 해당 요소들은 큐에서 삭제한다. 이때 큐에서 삭제하는 작업의 효율성을 위해 deque()를 사용한다.💡 deque..

🗂️ 문제링크: https://www.acmicpc.net/problem/1699 💡 접근법제곱 수는 1, 4, 9, 16 … 등이 있다.항의 최소 개수를 구하기 위해서는 제곱 수를 이용해야 한다. 한 가지 예시로 12의 경우, dp[12] = min(dp[1] + dp[11], dp[4] + d[8], dp[9] + dp[3])이다.즉, 제곱 수를 기준으로 모든 경우의 수를 계산해서 최소가 되는 값을 저장해야 한다. 😎 내 코드import sysimport mathN = int(sys.stdin.readline())dp = [100000] * (N+1)dp[0] = 0dp[1] = 1for i in range(1, N+1): for j in range(1, int(math.sqrt(i))+1..

🗂️ 문제링크: https://www.acmicpc.net/problem/11727 💡 접근법N=1일 때, 2x1 직사각형을 채우는 방법의 수는 2x1 크기의 타일 하나로 채우는 방법 1가지이다.N=2일 때, 2x2 직사각형을 채우는 방법의 수는 2x1 크기의 타일 2개를 이어붙이는 방법, 1x2 크기의 타일 2개를 이어붙이는 방법, 2x2 크기의 타일 하나로 채우는 방법, 총 3가지이다. N=3일 때, 2x3 직사각형을 채우는 방법은 다음과 같다.2x2 직사각형에 2x1 직사각형을 이어붙인다.2x1 직사각형에 1x2 크기의 타일 2개를 이어붙이거나, 2x2 크기의 타일 1개를 이어붙인다.이때, 2x1 크기의 타일 2개를 이어붙이는 경우의 수는 1번에 포함되기 때문에 카운트하지 않는다.이를 점화식으로..

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 접근법처음에는 min heap과 max heap을 각각 생성하고 이를 통해 최댓값, 최솟값을 찾아주려고 했다. 하지만 이렇게 하면 일일히 min heap에서 삭제된 값을 max heap에서도 찾아 삭제해야 한다는 단점이 있다. 따라서 하나의 힙을 생성하여 문제를 해결한다. 최소 힙에서 최댓값을 구하는 방법은 다음과 같다.힙 자료구조 또한 리스트 기반이기 때문에 max(heap..

🗂️ 문제링크: https://www.acmicpc.net/problem/2468 💡 접근법BFS 알고리즘을 통해 기준 높이보다 지역의 높이가 높아 물에 잠기지 않는 영역의 개수를 구한다. 이를 구하기 위해선 BFS 알고리즘을 통해 인접한 지역(상하좌우)을 탐색할 때 방문하지 않았던 위치(not visited[nx][ny])이면서 기준 높이보다 해당 지역의 높이가 높아야 한다(maps[nx][ny] > h). 지도에서 최대 지역의 높이를 찾아 최대 높이만큼 반복하여 안전한 영역의 최대 개수를 구한다. 😎 내 코드import sysfrom collections import dequeN = int(sys.stdin.readline())maps = []max_height = 0for _ in range(..