파이썬

[Algorithm/Python] 크루스칼 알고리즘이란? || 최소 신장 트리

들어가며본 포스팅에서는 신장 트리에 대해 그리고 최소 신장 트리 알고리즘인 크루스칼 알고리즘에 대해 소개합니다. 📌 신장 트리란?신장 트리(Spanning Tree)란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 말합니다.예를 들어 위와 같은 그래프가 존재한다고 할 때, 아래의 경우는 신장 트리인지를 확인해보겠습니다. 이 그래프는 노드 1을 포함하고 있지 않기 때문에 신장 트리에 해당하지 않습니다. 이 그래프는 모든 노드를 포함하고 있지만, 사이클이 존재하므로 신장 트리에 해당하지 않습니다. 이 그래프는 모든 노드를 포함하고 있으며, 사이클이 존재하지 않으므로 신장 트리에 해당합니다. 신장 트리의 노드 개수와 간선의 관계를 보면, 노드의 개수가 5개일 때, 간선..

[Algorithm/Python] 서로소 집합(Disjoint Sets) 알고리즘이란?

들어가며본 포스팅에서는 서로소 집합과 구현 방식에 대해 소개합니다.📌 서로소 집합이란?서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미합니다. 예를 들어 {1, 2}와 {3, 4}는 서로소 관계이지만, {1, 2}와 {2, 3}은 서로소 관계가 아닙니다. 서로소 집합 자료구조는 union과 find라는 2개의 연산이 이루어집니다. union(합집합)이란, 하나의 집합으로 합치는 연산을 의미하며, find(찾기) 연산은 특정 원소가 어느 집합에 속하였는지를 찾아내는 연산입니다. 1️⃣ union(합집합) 연산을 통해, 서로 연결된 두 개의 노드를 확인합니다. - 1 ) 노드 A와 노드 B의 루트 노드인 A'와 B'를 찾습니다. - 2 ) 루트 노드 A'를 루트 노드 B'의 부모 노..

[Programmers/Python] H-Index || 정렬(Sort)

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 H-Index 풀이 42747더보기문제 설명) H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이..

[Programmers/Python] 운영체제

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 PCCP 모의고사 1회 4번 운영체제 121686 더보기 문제 설명 개발자 준모는 운영체제를 만들었습니다. 준모가 만든 운영체제는 프로그램의 우선순위와 호출된 시각에 따라 실행 순서를 결정합니다. 모든 프로그램에는 1부터 10까지의 점수가 매겨져 있으며, 이 점수가 낮을수록 우선순위가 높은 프로그램입니다. 각 프로그램들은 실행 시간이 정해져 있으며 프로그램이 호출되면 대기상태에 있다가 자신의 순서가 되면 실행 시간 동안 실행된 뒤 종료됩니다. 준모가 만든 운영체제는 호출된 프로그램들 중 우선순위..

[Programmers/Python] 가장 큰 수 || 정렬

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 가장 큰 수 42746더보기문제 설명0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.제한 사항..

[Programmers/Python] 폰켓몬, 전화번호 목록 || Hash

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 폰켓몬 1845더보기문제 설명 )당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 ..

[Algorithm/Python] 파이썬 itertools에서 combinations, permutations를 사용하지 않고, 조합과 순열 구현

파이썬에서는 순열과 조합을 간단하게 바로 구해볼 수 있다. 그러나, itertools가 기억이 나지 않는 경우를 대비하여 순열과 조합을 직접 구현해보도록 하자. 📌 itertools 패키지의 combinations, permutations 활용 먼저 itertools를 통해 조합과 순열을 구하는 방법이다. ✅ [ CODE ] # 조합 from itertools import combinations arr = [0, 1, 2, 3] print(list(combinations(arr, 2))) # [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] ✅ [ CODE ] from itertools import permutations arr = [0, 1, 2] print(lis..

[Programmers/Python] 올바른 괄호 || Stack & Queue

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 올바른 괄호 12909 더보기 문제 설명 ) 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요. 제..

[Programmers/Java] 42576_완주하지 못한 선수

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 자바 42576 완주하지 못한 선수 더보기 문제 설명 ) 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 ) 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는..

[Programmers/Python] 42576_완주하지 못한 선수

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 42576 완주하지 못한 선수 더보기 문제 설명 ) 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 ) 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이..