sjmin

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net import itertools while True: k, *S = map(int, input().split()) S.sort() if k == 0: break for result in itertools.combinations(S, 6): print(' '.join(map(str, result))) print()

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net import itertools vowels = ['a', 'e', 'i', 'o', 'u'] # 5개의 모음 정의 L, C = map(int, input().split()) # 가능한 암호를 사전식으로 출력해야 하므로 입력 이후에 정렬 수행 array = input().split() array.sort() # 길이가 L인 모든 암호 조합을 확인 for password in itertools.combin..

1. 순열(Permutation) 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것 import itertools data = [1, 2] for x in itertools.permutations(data, 2): print(list(x)) # [1, 2] # [2, 1] 2. 조합(Combination) 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것 import itertools data = [1, 2, 3] for x in itertools.combinations(data, 2): print(list(x), end=' ') # [1, 2] [1, 3] [2, 3] https://developersj.tistory.com/106 백준 1759번 : 암호 만들기 https://w..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net import sys N, M = map(int, input().split()) data = list(map(int, sys.stdin.readline().split())) sum_value = 0 prefix_sum = [0] for k in data: sum_value += k prefix_sum.append(sum_value) for prefix in range(M): ..

1. 구간 합 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값 각 쿼리에 대해 구간 합을 빠르게 계산하기 위해서는 N개의 수의 위치 각각에 대하여 접두사 합(Prefix Sum)을 미리 구해 놓으면 된다. (접두사 합 : 리스트 맨 앞부터 특정 위치까지의 합을 구해놓은 것을 의미) 예를 들어 5개의 데이터 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정해보자. 여기서 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40으로 90이 될 것이다. 구간 합 계산 문제는 여러 개의 쿼리(Query)로 구성되는 문제 형태로 출제되는 경우가 많다. M개의 쿼리가 존재한다고 가정해보면, 각 쿼리는 Right, Left로 구성되며, 이는 [Left, Right]의 구간을 ..

1. 투 포인터 리스트에 순차적으로 접근해야 할 때 2개의 점 위치를 기록하면서 처리하는 알고리즘 예를 들어, 한 반에 40명의 학생이 있을 때, 모든 학생을 번호 순서대로 일렬로 세운 뒤, 학생들을 순차적으로 지목해야 할 경우를 생각해보자. 2, 3, 4, 5, 6, 7번 학생을 지목할 때, 번호로 한명씩 부르기보다는 '2번부터 7번까지의 학생'이라고 부를 수 있다. 이처럼 순차적으로 접근해야 할 때는 '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 특정한 합을 가지는 부분 연속 수열 찾기 문제를 풀어보자. 양의 정수로만 구성된 리스트가 주어졌을 때, 그 부분 연속 수열 중에서 '특정한 합'을 갖는 수열의 개수를 출력하는 문제이다. 특정한 부분합을 M이라고 할때 풀이 순서는..

1. 소수(Prime Number) 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수 ex) 2, 7... # 소수 판별 함수 def is_prime_number(x): for i in range(2, x): # 2부터 (x - 1)까지의 모든 수를 확인하며 if x % i == 0: # x가 해당 수로 나누어 떨어진다면 return False # 소수가 아님 return True # 소수임 print(is_prime_number(4)) print(is_prime_number(7)) # False # True 위 코드의 시간복잡도는 O(X)이며, 비효율적이다. 예를들어, 1,000,000이라는 수가 소수인지 확인해야 할 때는 1,000,000을 2부터 999,999..

cf) 표준 라이브러리 : 특정한 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리 라이브러리 종류 내장 함수 print(), input() 과 같은 기본 입출력 기능부터 sorted() 와 같은 정렬 기능을 포함하고 있는 기본 내장 라이브러리 itertools 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리, 순열과 조합 라이브러리 제공 heapq 힙(Heap) 기능을 제공하는 라이브러리, 우선순위 큐 기능을 구현하기 위해 사용 bisect 이진 탐색(Binary Search) 기능을 제공하는 라이브러리 collections 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함하고 있는 라이브러리 math 필수적인 수학적 기능을 제공하..

1. 복잡도 알고리즘의 성능을 나타내는 척도 시간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미, 알고리즘을 위해 필요한 연산 횟수를 계산할 수 있다. 알고리즘 문제를 풀 때, 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다. cf) 빅오(Big-O) 표기법 : 시간 복잡도를 표현하는 방법, 가장 빠르게 증가하는 항만을 고려하는 표기법 a = 5 b = 7 print(a + b) # a와 b에 값을 대입하는 대입 연산과 출력 함수를 무시하고 보면, 연산 횟수는 1 # 단순 더하기 연산 한번이 수행되므로(상수 연산) 시간 복잡도는 O(1) array = [3, 5, 1, 2, 4] # 5개의 데이터(N = 5) for i in array: for j in array: ..

1. 시작하기 전 클래스를 사용하는 것은 작정하고 속성과 기능을 가진 객체를 만들겠다는 뜻이다. 그래서 파이썬은 그에 따른 부가적인 기능을 제공한다. 예를 들어 어떤 클래스를 기반으로 속성과 기능을 물려받아 새로운 클래스를 만드는 상속, 이러한 상속 관계에 따라서 객체가 어떤 클래스를 기반으로 만들었는지 확인해주는 isinstance() 함수, 파이썬 기본적으로 제공하는 str() 함수 혹은 연산자를 사용해서 클래스의 특정 함수를 호출할 수 있게 해주는 기능이 대표적이다. 2. 어떤 클래스의 인스턴스인지 확인하기: isinstance() 객체(인스턴스)가 어떤 클래스로부터 만들어졌는지 확인할 수 있도록 isinstance() 함수를 제공한다. # 기본 형태 isinstance(인스턴스, 클래스) # 맞으..