🗂️ 문제링크: https://www.acmicpc.net/problem/11051 💡 접근법이항 계수란 그냥 조합이다. 즉, (5, 2)란 5C2를 구하는 것이다.이항계수의 성질을 이용하여 동적계획법으로 문제를 풀었으며, 이항계수의 성질은 다음과 같다. nCk = nCn-knCk = n-1Ck + n-1Ck-1파스칼의 삼각형을 본다면 더 쉽게 이해가 가능할 것이다. 위 두 성질을 기반으로 세운 DP 점화식은 다음과 같다.dp[i][k] = dp[i-1][k] + dp[i-1][k-1] (i≥1, k≥1) 추가적으로 코드에서는 1번 성질을 이용해서 for문의 반복횟수를 줄일 수 있다.예시로, 5C2 == 5C3이므로 5//2까지만 순회한다면 5에 대한 모든 조합의 경우를 구할 수 있다.5C0 ==..
🗂️ 문제 링크: https://www.acmicpc.net/problem/9237 💡 접근법최대한 빠르게 모든 묘목을 심고 다 자라게하기 위해서는 자라는 데 오래 걸리는 묘목부터 심어야 한다.따라서 묘목이 자라는 기간을 내림차순으로 정렬한다. 묘목 하나를 심는 데 1일이 소요된다. 이 말은 묘목은 하루에 하나만 심을 수 있다는 말로 해석된다.따라서 묘목을 구입한 1일부터 바로 묘목을 심도록 하자.또한 묘목을 심은 날짜에 묘목이 자라는 데 걸리는 기간을 더한다면 해당 묘목이 모두 자라는 날짜를 구할 수 있다. 예시를 들어 살펴보자.1일에 첫 번째 묘목을 심는다. 이때 첫 번째 묘목이 자라는 데 4일이 걸린다면, 해당 묘목은 5일까지 모두 자란다.2일에 두 번째 묘목을 심는다. 이때 두 번째 묘목이 ..
기여한 프로젝트https://github.com/projectdiscovery/nuclei-templates GitHub - projectdiscovery/nuclei-templates: Community curated list of templates for the nuclei engine to find security vulnerabiCommunity curated list of templates for the nuclei engine to find security vulnerabilities. - projectdiscovery/nuclei-templatesgithub.comNuclei란 애플리케이션, 운영체제, 인프라, 클라우드 플랫폼 및 네트워크를 조사하여 취약점 식별 및 완화를 지원하도록 설계된 ..
🗂️ 문제링크: https://www.acmicpc.net/problem/4948 💡 접근법n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 문제이다.이때 여러 케이스에 대해 소수를 판별할 때, 동일한 수에 대한 소수 판별 로직이 반복 수행될 수 있다. 이 과정을 없애고자 is_prime_num 리스트를 생성하여 한 번 소수 판별을 수행한 수에 대해서는 True or False로 값을 저장해두어 로직이 재수행되지 않도록 한다. 😎 내 코드import sysdef is_prime(x): if x == 1: return False for i in range(2, int(x**0.5)+1): if x % i == 0: return False..
🗂️ 문제링크: https://www.acmicpc.net/problem/1929 💡 접근법소수는 1과 자기 자신을 제외한 약수가 존재하지 않아야 한다.소수를 판별하기 위해서는 2부터 √x까지만 나눠보면 된다. x = a * b라고 했을 때 a와 b 중 하나는 반드시 √x 이하이기 때문이다. 예를 들어 x = 36 이라고 할 때약수 쌍: (1, 36), (2, 18), (3, 12), (4, 9), (6, 6), (9, 4), (12, 3), (18, 2), (36, 1)즉, 보면 알 수 있듯이, (4, 9) 이후부터는 대칭적으로 반복된다. 😎 내 코드import sysdef gcd(x): if x == 1: return False elif x == 2 or x == 3: ..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법lose_list[i] → i번 선수에게 진 선수들의 리스트와 win_list[i] → i번 선수에게 이긴 선수들의 리스트를 각각 구한다.즉, 단방향 그래프 형식으로 이긴 선수들의 그래프와 진 선수들의 그래프 관계를 나타냈다. i번 선수에게 이긴 선수들과 i번 선수에게 진 선수들을 모두 구한다.만약 순위를 매길 수 있다면, lose_list[i]의 수 + win_list[i]의 수는 n-1일 것이다. 이를 구하기 ..
🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 접근법모든 노드의 가중치가 동일했기 때문에 BFS를 사용하여 최단 거리를 구했다.1번 노드에서 모든 노드까지의 최단 거리를 구하고, 그 중 가장 긴 거리를 구한 뒤, 거리 배열에서 가징 긴 거리의 개수를 구했다. 😎 내 코드from collections import dequedef BFS(v, graph, visited): distances = [0 for _ in range(len(visited))] ..
🗂️ 문제링크: https://www.acmicpc.net/problem/1874 💡 접근법제시하는 입력값의 수열을 만들기 위해 1~N까지 차례로 숫자가 입력될 때 스택에서 어떤 순서로 push와 pop을 해야할 지를 결정해야 하는 문제이다. 풀이는 다음과 같다. 1부터 N까지 숫자를 차례대로 입력한다.스택의 top이 현재 비교하는 수열보다 작다면 현재 숫자를 스택에 push한다.스택의 top이 현재 비교하는 수열과 같다면 스택에서 pop하고, 반복 수행한다.위 과정을 while 문을 통해 반복 수행하는 이유는, pop한 뒤 수열의 top과 다음 수열이 같을 수 있기 때문이다.모든 숫자를 입력한 뒤 만약 스택이 비어있다면 만들 수 있는 수열이 되고, 스택이 비어있지 않다면 만들 수 없는 수열에 해당한..
