🗂️ 문제링크: 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(..
🗂️ 문제링크: https://www.acmicpc.net/problem/7562 💡 접근법나이트가 이동할 수 있는 범위를 dx와 dy로 생성한다.이후 맵의 크기에 맞게 False로 maps를 초기화하고, deque를 통해 큐를 생성한다. 초기 시작 위치값인 a와 b를 입력받고, maps[a][b]=0으로 초기화한다.while()문을 통해 큐의 맨 왼쪽 값을 pop하면서 나이트가 이동할 수 있는 범위를 모두 탐색한다. 이때 맵을 벗어나지 않으면서 방문한 적 없는 위치일 경우 큐에 현재 위치를 추가하고 maps에 현재 값을 업데이트한다. 이때 업데이트되는 값은 처음부터 지금까지 이동한 횟수를 나타낸다. 만약 종료 위치에 도달했을 경우 큐를 비워 while문을 빠져나온다.최종적으로 이동하려는 위치에 해당..
🗂️ 문제링크: https://www.acmicpc.net/problem/1966 💡 접근법제일 왼쪽의 값을 쉽게 꺼내기 위해 deque를 사용한다. 문서가 몇 번째로 인쇄되는지 횟수를 세기 위해 인덱스를 저장해야 한다. 이를 위해 queue에 튜플 형식으로 (인덱스, 중요도)를 저장한다.while()문을 통해 큐에서 왼쪽에 위치한 값을 하나씩 꺼내고, 만약 그 다음 값들 중 현재 값보다 중요도가 높은 문서가 있다면 다시 큐에 현재 값을 삽입한다. 이때 인쇄가 될 경우 카운트 횟수를 증가시켜야 한다. 따라서 큐에서 현재 값을 꺼낼 때 카운트를 1 증가시키고, 만약 현재 값보다 중요도가 큰 문서를 발견하여 현재 값을 다시 큐에 삽입하게 되면 카운트를 1 감소시킨다. target에 궁금한 문서를 저장해 ..
