분류 전체보기

[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..

[알고리즘] 최소 스패닝 트리 알고리즘 | 크루스칼/프림 알고리즘

~목차~ 스패닝 트리란? 크루스칼 알고리즘 프림 알고리즘 (최소) 스패닝 트리란? 최소 스패닝 트리 알고리즘을 설명하기 이전에 스패닝 트리(Spanning Tree)란 무엇인가 알아보도록 하겠습니다. 스패닝 트리는 어떤 그래프에서 모든 노드를 연결하며 사이클이 없는 부분 그래프를 의미합니다 그림으로 이해해보겠습니다 왼쪽과 같은 초기 그래프가 있을 때 오른쪽 그래프는 스패닝 트리입니다. 그럼 아래 그래프는 스패팅 트리 일까요? 아닙니다. 오른쪽 그래프는 사이클이 발생했고, 오른쪽 그래프는 모든 노드를 연결하지 않고 있습니다. 그렇다면 아래 그래프는 신장(스패닝) 트리일까요? 그렇습니다. 신장 트리 중 최소 신장 트리입니다. 최소 신장(스패닝) 트리는 신장 트리 중 가장 적은 비용을 갖는 그래프입니다. 모든..

[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..

[Python] 백준 21924 도시 건설 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/21924 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 문제 해결 포인트 - 크루스칼 알고리즘 작성 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) parent = [i for i in range(N..