nHr 서로 다른 n개중에서 중복을 허용하되 순서는 없이 r개를 뽑는 경우

itertools 이용

import itertools

arr = [1,2,3,4,5]
r = 2
arrC = itertools.combinations_with_replacement(arr, r)
print(arrC)

nπr 서로 다른 n개중, 중복을 허용하고 순서가 존재하도록 r개를 뽑는 경우

itertools 이용

import itertools

arr = [1,2,3,4,5]
r = 2
list(itertools.product(arr, repeat = r))
print(list)

nCr 서로 다른 n개중 순서와 중복 없이 r개를 뽑는 경우

itertools 사용

import itertools

arr = [1,2,3,4,5]
r = 2

comb = lsit(itertools.combinations(arr, r)
print(comb)

nPr 서로 다른 n개중 r개를 순서는 있고, 중복은 없이 뽑는 경우

itertools사용

import itertools

r = 2
arr = [1,2,3,4,5]
permu = list(itertools.permutations(arr, r))
print(permu)

직접 구현

//

문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. 출력 각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

문제 해결 아이디어 결국 중복을 허용하지 않으며, 순서없이 m개중 n개를 고르는 조합 문제이다.(combinations) 조합의 공식은 nCr = n(n-1)(n-2)...(n-r+1)/r!

import sys

def combi(n,r):
  #n개중 r개를 순서 상관 없이 중복 없이 고름
  a = 1
  b = 1
  for i in range(r):
    a = a*(i+ n-r +1)
  for i in range(1,r+1):
    b = b*i
  return a/b

t = int(sys.stdin.readline().rstrip())
for i in range(t):
  m,n = map(int, sys.stdin.readline().rstrip().split())
  print(int(combi(n,m)))

문제 해결 아이디어 이차원 리스트로 파스칼 삼각형을 만들고 출력하면 된다.

import sys

n,k = map(int, sys.stdin.readline().rstrip().split())

#파스칼 삼각형 만들기
arr = [[1 for _ in range(k+1)] for i in range(n+1)]
for i in range(1, n+1):
  for j in range(1, k+1):
    arr[i][j] = arr[i][j-1] + arr[i-1][j]

print(arr[n-k][k])

문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

입력 첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100) 다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다

출력 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

문제 해결 아이디어 처음에는 소인수 분해를 해서 리스트에 삽입한뒤, 나뉘는것과 나누는것 각각의 리스트중 공통된것을 지우고, 다시 곱셈을 하려했다. 하지만 고민해본 결과 최대 공약수를 구해서 나누어 주기만 하면 쉽게 풀리는 문제였다.

import sys

def rotating(child, parent):
  arrC = []
  arrP = []
  ans = 1
  #약수를 구해준다.
  for i in range(1, child//2 + 1):
    if child%i == 0:
      arrC.append(i)
      arrC.append(child//i)
  for i in range(1, parent//2 +1):
    if parent%i == 0:
      arrP.append(i)
      arrP.append(parent//i)
   #약수중 공통된 수를 찾아주는데, 그 수가 더 커지면 갱신한다. 
  for i in arrP:
    if i in arrC:
      if i> ans:
        ans = i
  print(child//ans, '/', parent//ans, sep = '')
  return 0

n = int(sys.stdin.readline().rstrip())

arr = list(map(int, sys.stdin.readline().rstrip().split()))

for i in range(n-1):
  rotating(arr[0], arr[i+1])

입력 첫째 줄에 수 W H X Y P가 주어진다. P는 선수의 수이다. W와 H는 100보다 작거나 같은 자연수이고, H는 짝수이다. X와 Y는 절댓값이 100보다 작거나 같은 정수이다. P는 최대 50인 자연수이다. 둘째 줄부터 P개의 줄에 각 선수들의 x좌표와 y좌표가 주어진다. 이 좌표는 절댓값이 300보다 작거나 같은 정수이다.

출력 첫째 줄에 링크 안에 있는 선수의 수를 출력한다.

import sys
def dire(x,y,ax,ay):
  return (x-ax)**2+(y-ay)**2



w,h,x,y,p = map(int,sys.stdin.readline().rstrip().split())

hap = 0
r = h/2
for i in range(p):
  ax ,ay = map(int, sys.stdin.readline().rstrip().split())

  if (x <= ax and ax<= (x+w)) and (y <= ay and ay <= (y+h)):
    hap += 1
  elif(dire(x,y+r,ax,ay)<=r**2) or (dire(x+w,y+r, ax,ay)<=r**2):
    hap += 1

print(hap)

문제 해결의 아이디어 사가형과 원으로 나누어 생각하여. 사각형의 좌표 범위 내에 있는경우를 처리하고, 원의 경우 거리와 반지름을 비교하여 처리하였다.

주의점 거리를 처리하며 루트연산을 사용하면, 실수계산 오차에 의해 오답판정을 받을수 있으므로, 루트연산을 사용하지 않고 비교대상인 반지름또한 제곱연산을 하여 계산하였다.

입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력 첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

실패한 코드(메모리 초과) 동일한 수의 갯수를 구하는 문제이기에 '인덱스 = 수'인 리스트를 만드는것이 좋을것이라 판단했지만 실패

import sys

n = int(sys.stdin.readline().rstrip())
arrn = list(map(int, sys.stdin.readline().rstrip().split()))

#크기 만큼 배열 생성. [0] 은 양수, [1]은 음수
if abs(max(arrn)) >= abs(min(arrn)):
  arr = [[0,0] for i in range(2+abs(max(arrn)))]

else: 
  arr = [[0,0] for i in range(2+abs(min(arrn)))]


for i in arrn:
  if i >= 0 :
    arr[i][0] += 1
  else:
    arr[-i][1] += 1

m = int(sys.stdin.readline().rstrip())
arrm = list(map(int, sys.stdin.readline().rstrip().split()))

for i in arrm:
  if i >=0:
    print(arr[i][0],end= ' ')
  else:
    print(arr[-i][1], end = ' ')

성공한 코드 dict를 이용하여 필요한 정보만 저장하여 메모리를 줄였습니다.

import sys

n = int(sys.stdin.readline().rstrip())
arrn = list(map(int, sys.stdin.readline().rstrip().split()))

dic = {}

for i in arrn:
  dic[i] = 0
for i in arrn:
  dic[i] +=1


m = int(sys.stdin.readline().rstrip())
arrm = list(map(int, sys.stdin.readline().rstrip().split()))

for i in arrm:
  try:
    print(dic[i],end = ' ')
  except KeyError:
    print(0, end = ' ')