📁문제 풀이

[Python] 백준 2579 계단 오르기 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 해결 포인트 - 최대 300개 계단의 점수를 기록할 배열 미리 선언 - 계단 별 점수 기록 배열과 dp 기록을 저장할 배열 2개 필요 - 계단 1 : 본인 점수 계단 2 : 계단 1 + 본인 점수 계단 3 : max(계단 1 + 본인 , 계단 2 + 본인) - 점화식 : max( 본인 이전 계단 밟고 본인 , 본인 이전 계단 밟지 않고 본인) ai = ma..

[Python] 백준 1966 프린터 큐

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 해결 포인트 - 자료구조 큐 - 순서를 나타내는 두개의 변수를 잘 구분하여 인지하여야한다. * 남은 우선순위 중 최대값이므로 출력하는 순서 * 초기 큐의 각 문서 순서 - 큐에 (중요도, 위치) 값을 삽입한다. 위치값을 삽입하는 이유는 M과 비교하여 찾는 문서인지 확인하기 위함 - 초기 큐를 내림차순으로 정렬한다. 매번 큐의 최대값을 구하는 것보다..

[Python] 백준 16953 A -> B | 그리디 알고리즘 | BFS

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 해결 포인트 - 그리디 알고리즘, BFS - 입력 값에 대해서 두개의 연산을 연쇄적으로 수행함으로 모든 경우의 수 확인 - 원하는 값이 발견되면 출력 후 즉시 종료( 가장 먼저 발견되는 연산 횟수가 가장 작은 연산이므로) : 그리디 - 연산 값이 타켓 값보다 크다면 해당 서브 트리에 대해서 더이상 탐색하지 않도록 한다. 작성 코드 from collections import deque a, b = map(int, input().split()) que = deque() #..

[Python] 백준 1003 피보나치 함수 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 해결 포인트 - DP - 입력값(1~40) 에 따라 0과 1이 불린 횟수를 점화식을 이용하여 구할 수 있다 - 입력값 0은 0이 1회/1이 0회 불린다. 입력값 1은 0이 0회/1이 1회 불린다. - 입력값이 2라면 f(2) = f(1) + f(0) 이므로 1이 한 번, 0이 한 번 불린다. - 입력값이 3이라면 f(3) = f(2) + f(1) 이므로 f(2) 실행시 1한 번, 0 한 번 불린 것과 1이 한 번 불린 것을 더하면 1이 2번..

[Python] 백준 9095 1, 2, 3 더하기 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 해결 포인트 - DP(다이나믹 프로그래밍)의 전형적인 문제이다 - DP는 한번 진행한 계산에 대해서 저장 해두고 또 발생시 계산 값만 사용한다. - 해당 코드에서 numbers 배열은 계산 결과 값을 저장해두는 역할을 한다. - 1, 2, 3을 이용하여 1, 2, 3을 만드는 방법을 생각해보자 1 = 1 1을 만드는 방법은 1개(numbers[1] = 1) 2 = 1 + 1 2 = 2 2를 만드는 방법은 2개(numbers[2] = 2) 3 ..

[Python] 백준 1715 카드 정렬하기 | 그리디 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 해결 포인트 - 작은 카드 뭉치들 부터 순서대로 처리해야 하므로 그리디 알고리즘입니다! - 카드 뭉치가 1개라면 비교할 뭉치가 없으므로 0 반환 - 카드 뭉치가 3개 이상이라면 최소값 2개를 뽑아 순서대로 연산(우선순위 큐) - 큐 안에 뭉치가 2개 남았다면 더이상 최소 값 2개를 찾지 않고 연산 값을 더하여 출력 & 반복문 종료..

[Python] 프로그래머스 실패율 | 정렬 | 2019 KAKAO BLIND RECRUITMENT

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 각 스테이지 별 실패율 계산 -> 내림차순 정렬(실패율이 큰 값이 앞에 와야하므로) - 실패율이 같다면 스테이지 번호 -> 오름차순 정렬 - 정렬 결과에서 스테이지 번호만 리스트로 출력 작성 코드 def solution(N, stages): players = len(stages) # 사용자 수 answer = [] for sta..

[Python] 프로그래머스 선 연결하기 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 크루스칼 알고리즘을 이용하여 최소 스패닝 트리 찾는다. - 간선 비용 기준으로 오름차순 정렬하여 순서대로 사이클이 발생하지 않으면 연결해 나간다 크루스칼 알고리즘 정리 글 2023.05.29 - [🧪Computer Science/알고리즘] - [알고리즘] 최소 스패닝 트리 알고리즘 | 크루스칼/프림 알고리즘 작성 코드 def s..

[Python] 백준 1774 우주신과의 교감 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1774 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 - dots : 각 점(정점, 노드) 별 x, y 좌표 저장 - edges : 간선의 비용 기준으로 오름차순 - parent : 정점 별 속한 집합 정보 - 각 정점 정보를 순서대로 dots..