https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 문제설명2진 트리 모양 초원에서 각 노드를 돌아다니며 양 모으기각 노드는 양과 늑대로 구성모은 양의 수보다 늑대의 수가 같거나 더 많아지면 모든 양 잡아먹힘중간에 양이 늑대에게 잡아먹히지 않으면서 다시 루트 노드로 돌아올 때, 최대 몇마리의 양을 모을 수 있는지 ? 2. 문제해결edges에서 하나의 edge는 부모-자식 노드의 연결을 의미한다.현재 노드에서 연결된 노드들을 방문할 수 있을 뿐만 아니라 이전 부모노드에 연결된 자식노드에도 방..

https://leetcode.com/problems/coin-change/description/ 1. 문제설명coins에 들어있는 coin을 이용해서 amount 만들 때, 필요한 최소 개수만들 수 없으면 -1를 반환하고 각 coin의 개수는 무한개로 가정 2. 문제해결최소 개수를 구하는 거니까 BFS 이용단, 그냥 BFS로 구현하면 메모리 초과 에러 발생가지를 뻗기 전에 cur_v와 coin을 더한 값을 방문했는지 visit을 통해 확인class Solution: def coinChange(self, coins: List[int], amount: int) -> int: from collections import deque def bfs(): q = d..

https://leetcode.com/problems/is-graph-bipartite/ 1. 문제설명주어진 그래프가 Bipartite인지 아닌지 반환 2. 문제이해하나의 노드가 A라면 엣지로 연결된 노드들이 모두 B이어야 한다.만약 하나의 노드가 B로 저장되어 있고, 이와 연결된 노드도 B로 저장되어 있으면 Bipartite 불가 3-1. 문제해결 (BFS)만약 next_v가 방문처리 되어 있지 않을 경우 connect 확인 connect에 저장되어 있지 않을 경우 : 반대로 저장 (A-B)connect에 저장되어 있을 경우 : 반대로 되어 있는지 확인 (똑같으면 False 반환) 그래프의 노드들이 모두 하나로 연결되어 있지 않고, 여러개의 그래프가 나올 수도 있으니까 전체적인 visit을 만들어서 방..

https://leetcode.com/problems/longest-valid-parentheses/description/ 1. 문제설명“(”와 “)”로 구성된 문자열이 주어질 때, 유효한 괄호 문자열의 가장 긴 길이를 반환 2. 문제해결괄호 짝 맞추기 문제는 stack, 길이를 구하는 문제는 index가 많이 활용되므로 이를 이용해서 해결 시도(인덱스 길이 계산 후 pop) : ‘()(())’에서 길이가 각각 2, 4로 따로 구해져 연속된 부분 반영이 안된다.(pop 후 인덱스 길이 계산) : pop을 먼저 해 준 다음 stack[-1] 부분의 인덱스와 현재 인덱스의 차를 구해주면 연속되는 길이가 자연스럽게 구해진다.단, stack이 비어 있으면 안되니까 맨 처음에 짝이 절대 안맞는 [-1, ‘)’]을..

https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 문제설명두 개의 큐가 주어질 때, 각 큐의 합이 같도록 만들기 위한 최소 이동 횟수 구하기한 번의 pop과 한 번의 insert를 합쳐서 1회 수행 2. 문제해결def solution(queue1, queue2): from collections import deque queue1 = deque(queue1) queue2 = deque(queue2) cur1 = sum(queue1) cur2 = sum(queu..

https://leetcode.com/problems/trapping-rain-water/description/ 1. 문제설명각 높이를 나타내는 지도가 주어졌을 때, 얼만큼 물이 담길 수 있는지 계산 2. 문제해결[stack 이용]class Solution: def trap(self, height: List[int]) -> int: stack = [] water = height.copy() for i, h in enumerate(height): if stack and stack[-1][1] 현재 높이랑 마지막에 저장된 높이랑 비교하는 과정이 필요하므로 stack 이용stack이 들어 있고 현재 높이가 stack의 맨 끝 높이보다 크거나 같으면..

https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 문제설명단품 메뉴들을 조합해서 코스요리 형태로 재구성하기메뉴 주문시 가장 많이 함께 주문한 단품메뉴들을 선택단, 최소 2가지 이상의 단품메뉴로 구성 / 최소 2명 이상의 손님으로부터 주문된 것 단품메뉴 조합에 대해서만 후보에 포함  2. 코드구현def solution(orders, course): # 'XA'와 'AX'가 다르게 카운트 되는 것 방지 for i in range(len(orders)): orders[..

https://leetcode.com/problems/sudoku-solver/description/  class Solution: def solveSudoku(self, board: List[List[str]]) -> None: row_sets = [set() for _ in range(9)] col_sets = [set() for _ in range(9)] box_sets = [set() for _ in range(9)] for r in range(9): for c in range(9): if board[r][c] != '.': num = board[r][c] ..

에라토스테네스의 체 알고리즘특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 할 때 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘에라토스테네스의 체 알고리즘의 구체적인 동작 과정1) 2부터 N까지의 모든 자연수를 나열한다.2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.3) 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않음 !)4) 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.  에라토스테네서의 체 알고리즘 동작 예시1) 2부터 N까지의 모든 자연수를 나열한다. 2) 아직 처리하지 않은 가장 작은 수 2를 제외한 2의 배수는 모두 제거한다  3) 아직 처리하지 않은 가장 작은 수 3을 제외한 3의 배수는 모두 제거한다.  ..

import matha,b = map(int, input().split())math.gcd(a,b)math.lcm(a,b)