문제 설명선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요. 제한 조건 스..
분류 전체보기
시간 제한 메모리 제한 2 초 128 MB 문제 (링크) https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 나의 풀이 import sys import math n = int(sys.stdin.readline()) # n이하의 수 중 소수를 찾아줄 배열 (에라토스테네스의 체) prime_checker = [True for _ in range(n+1)] # 소수가 아닌 0과 1에 대해 별도의 False처리 prime_checker[0:2] = False for i in range(2, int(math.sqrt(n)) + 1): if prime_checker[i]: j ..
시간 제한 메모리 제한 0.5 초 128 MB 문제 (링크) https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 나의 풀이 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) end = 0 intervalSum = arr[0] ans = float('inf') for start in range(..
문제 (링크) https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 나의 풀이 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) intervalSum = arr[0] # m과 비교할 start ~ end까지 더한 값들 cnt = 0 # start ~ end == m 일..
투 포인터 알고리즘은 주로 수열의 연속된 값들의 합을 다룰 때 사용되는 알고리즘이다. 여기서 두 개의 포인터란 말 그대로 시작점과 끝 점을 포인터로 잡아 해당 포인터들이 움직이면서 동작을 수행해준다. 백문이불여일견. 이미지로 한 번 살펴보자 동작 방식 우리가 배열에서 연속된 값의 합이 5가 될 때의 경우를 찾고 싶다고 가정해보자. 물론 반복문을 두 번 중첩시켜 모든 배열의 값들에 대해 완전탐색을 진행할수도 있지만, 그러한 방식은 O(n^2) 만큼의 시간이 소요된다. 배열이 커지면 커질수록 연산시간은 기하급수적으로 증가할 것이다. 따라서 사용되는 방식이 이 글에 포스팅하는 투 포인터 방식이다. 앞서 설명한 것과 마찬가지로, 투 포인터 방식에선 start와 end라는 두 개의 포인터를 정의해준다. 처음엔 두..
예전에 지금보다 더 코린이일 때, 카카오 코딩테스트 기출문제를 호기심에 풀어보다가 첫 문제부터 막힌 기억이 생생하다. 정답률이 무려 80%가 넘는 쉬운 문제였는데, 우리가 흔히 사용하는 10진수의 숫자를 2진수 형태로 바꿔주면 바로 풀 수 있는 간단한 문제였다. 물론 내가 부족하다는 게 가장 주된 이유이지만, 함수를 모른다는 이유로 문제를 풀지 못하면 꽤 억울하다. 그 때의 억울함을 추억하며 이 내용을 정리해보자. 파이썬의 공식 문서에 등록되어 있는 bin()의 사용법은 다음과 같다. 어려운 내용이 아니다. 정수형 숫자를 파라미터로 bin(x)에 넘겨주게 되면, 해당 숫자에 맞는 2진수 숫자를 리턴해준다. print(bin(10)) 10을 2진수로 바꿔주면 다음과 같은 결과가 출력된다. 재미있는 점은 이..
문제 (링크) https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 나의 풀이 첫 번째 풀이 import sys import math data = [] while True: n = int(sys.stdin.readline()) # 입력값이 0이 아닐때까지 입력값을 data배열에 저장 if n == 0: break else: data.append(n) def is_prime_count(x, y): # x이상 y이하의 수 중 소수인 것의 개수 리..
문제 (링크) https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 나의 풀이 import math m, n = map(int, input().split()) arr = [True for _ in range(n+1)] for i in range(2, int(math.sqrt(n)) + 1): if arr[i] == True: j = 2 while i * j 1: if arr[i] == True: print(i) 접근 방법 및 코드 설명 낮에 공부했었던 에라토스테네스의 체를 사용하는..
