코딩하는 eroke

1. 중복순열

1~n의 숫자 중 m개를 중복순열로 선택하기

n개의 노드를 가진 트리를 m레벨 만큼 내려가며 1에서 n사이의 숫자를 중복하여 선택한다

import sys
input=sys.stdin.readline #input 속도 개선/ 문자열 읽을 시 input().rstrip()으로 개행문자 제거필수
#중복순열
def dfs(lev): 
    global cnt
    if lev==m:
        print(res)
        cnt+=1

    else:
        for i in range(1,n+1): #1~n까지 m번 돌면서 하나씩 선택
            res[lev]=i
            dfs(lev+1)


if __name__=="__main__":
    n,m = map(int,input().split()) #n개 중 m개 중복순열 > n개의 노드 트리 m개 레벨 생성
    res=[0]*m
    cnt=0
    dfs(0)
    print(cnt) #중복순열의 개수

2. 순열

순열은 중복순열과 로직이 거의 똑같다.

단, dfs를 태울때 중복으로 선택하지 않도록 체크해주면 된다.

import sys
input=sys.stdin.readline #input 속도 개선/ 문자열 읽을 시 input().rstrip()으로 개행문자 제거필수
#순열
def dfs(lev):
    global cnt
    if lev==m:
        print(res)
        cnt+=1

    else:
        for i in range(1,n+1): #1~n까지 m번 돌면서 하나씩 선택
            if(ch[i]==0):   #선택하지 않은것만
                res[lev]=i  #선택
                ch[i]=1     #체크
                dfs(lev+1)
                ch[i]=0


if __name__=="__main__":
    n,m = map(int,input().split()) #n개의 노드 트리 m개 레벨 생성
    res=[0]*m
    ch=[0]*(n+1) #중복 제외처리 체크배열
    cnt=0
    dfs(0)
    print(cnt) #순열의 개수

3. 조합

조합은 1~n의 숫자들 중 m개를 선택한 부분집합끼리도 중복이 없어야 한다. [2,4]=[4,2]

n개의 숫자중 하나씩 택할때마다 다음 노드는 무조건 앞에서 선택한 것보다 큰 수를 선택하도록 한다. (중복방지)

import sys
input=sys.stdin.readline #input 속도 개선/ 문자열 읽을 시 input().rstrip()으로 개행문자 제거필수
#조합
def dfs(lev,node):
    global cnt
    if lev==m:
        print(res)
        cnt+=1

    else:
        for i in range(node,n+1): #node~n까지 m번 돌면서 하나씩 선택
            res[lev]=i
            dfs(lev+1, i+1) #트리 가지에 +1 (중요)

if __name__=="__main__":
    n,m = map(int,input().split()) #n개의 노드 트리 m개 레벨 생성
    res=[0]*m
    cnt=0
    dfs(0,1)
    print(cnt) #조합의 개수

참고

1. 부분집합

1부터 N까지의 부분집합을 구할때 DFS로 부분집합을 구현할 수 있다.

집합 원소는 포함할 수, 포함하지 않을 수로 체크하는 배열을 두어서 구현한다.

DFS가 N+1까지 도달하면 포함하기로 한 수를 차례로 출력한다.

#부분집합
def dfs(v):
    if v==n+1: #도착점
        for i in range(1,n+1):
            if ch[i]==1: print(i, end=' ')
        print()

    else:
        ch[v]=1 #사용하겠다
        dfs(v+1)
        ch[v]=0 #사용안함
        dfs(v+1)


if __name__=="__main__":
    n=int(input())
    ch=[0]*(n+1)
    dfs(1)

2. 합이 같은 부분집합 (응용)

입력받은 배열의 합과 부분집합의 합의 차이를 이용한다. (total-sum)

사용할 원소는 해당 원소를 더해준다.

사용하지 않을 원소는 기존 sum 값을 유지하고 트리 레벨만 증가시킨다.

import sys

def dfs(lev,sum): #tree level
    if sum>total//2: return #cut off (합이 같은 부분집합이므로 절반 이상 합산은 제거)

    if lev==n: #dfs탈출
        if sum==(total-sum):
            print("합이같은 부분집합 존재 : ",sum)
            sys.exit(0)

    else:
        dfs(lev+1, sum+arr[lev]) #사용
        dfs(lev+1, sum)          #사용x (기존 sum 그대로)

if __name__=="__main__":
    n=int(input())
    arr=list(map(int,input().split()))
    total=sum(arr)
    dfs(0,0)

    print("합이 같은 부분집합 없음") #dfs 함수에서 종료처리 안됐을 시

[1,3,5,7] [6,10] 16으로 합이 같은 부분집합이 존재한다.

참고

리스트 생성

a = []  #기본

a = [0]*N #크기 N의 1차원 리스트를 0으로 초기화 생성

b = [[0]*N for _ in range(N)] #N*N 2차원 리스트를 0으로 초기화 생성

리스트의 입출력

연속 입력 시 input().split() 을 사용한다. 

input()은 기본적으로 문자열 형식으로 입력받기 때문에 다른 자료형으로 입력받으려면 map을 사용하면 된다.

#변수입출력
N = input() #기본적으로 문자열로 받음, 정수입력 = int(input())
a, b = map(int, input().split()) #int로 연속입력

#리스트입출력
arr = list(input().split()) #공백으로 구분, 연속입력
arr2 = list(map(int, input().split())) #int로 입력 

#리스트 원소 붙여서 출력
arr=''.join(arr)
print(arr)

#리스트 원소 사이의 문자 지정 가능
arr='.'.join(arr)
print(arr)


#2차원리스트입력
for i in range(n):
    arr3.append(list(map(int, input().split())))

arr4=[list(map(int, input().split())) for _ in range(n)]

a=''.join(a)

기본적으로 사용하는 메소드들

import random as r

b= list(range(1,11)) #1~10

r.shuffle(b) #b 무작위로 섞음 

b.insert(인덱스, 값) #해당 인덱스에 값 추가

b.append(값) #리스트 끝에 해당 값 추가

b.pop() #끝값 제거

b.remove(값) #첫번째 값 삭제
del b[인덱스] #해당 인덱스 값 삭제

b.index(값) #해당값의 인덱스 출력

len(b) #리스트 b의 길이

리스트 슬라이스 기능

a[:n] #0~(n-1)인덱스까지 슬라이스

enumerate 

리스트의 인덱스, 값에 각각 접근이 가능하다.

for x in enumerate(b):
	print(x) # len(b) 만큼 리스트 b의 (인덱스, 값)이 tuple형으로 순서대로 출력됨
	print(x[0], x[1]) #괄호, 콤마 없이 인덱스 값 만 출력됨
    
for index, val in enumerate(b):
	print(index, val) # line 3과 출력 같음

all, any

if all(50>x for x in a):
	print("모두 50 이상") 
    
if any(50>x for x in a):
	print("하나라도 50 이상")

python list 내장함수들에 대해 기본적으로 정리해보았고 계속해서 추가할 예정이다,,

sorted()

1. sorted()는 리스트, 문자, 숫자 모두 정렬이 가능하다 list 형으로 반환한다. (용도에 맞게 join 하기)

   ※ sort()는 리스트 자료형만!

2. key 옵션으로 정렬 기준을 지정할 수 있다. 

a = ['aaa', 'aa', 'b', 'cccc']
sorted(a, key=len) # ['b', 'aa', 'aaa', 'cccc']

b = ['cde', 'ctc', 'abc']
# b의 문자열 중 첫문자를 우선, 다음은 마지막 문자 기준 정렬
sorted(a, key=lambda s: (s[0], s[-1])) # ['abc', 'ctc', 'cde'] 

#람다대신 함수지정도 가능
def fn(s):
  return s[0], s[-1]

print(sorted(a, key=fn))

#딕셔너리 key로 정렬
d1 = sorted(d.items())

#딕셔너리 val로 정렬
d2 = sorted(d.items(), key=lambda x: x[1])

파이썬 딕셔너리 사용 시 유용한 컨테이너 자료형들의 용도와 사용법을 정리해보았다.

1. defaultdict

딕셔너리는 존재하지 않는 인덱스/키를 조회, 삭제 연산 시 각각 IndexError, KeyError가 발생한다.

그래서 다음처럼 에러가 발생하는 경우를 예외처리 하는 방법도 있다.

    a = {}  # 빈 딕셔너리
    
#1 try-except
    try:
        print(a['key'])  # 없는 키 조회 시
        del a['key']  # 없는 키 삭제 시
    except KeyError:
        print('KeyError 발생')

#2 if문
    if 'key' in a:
        print('Key 존재')
    else:
        print('존재하지 않는 Key')

defaultdict 객체는 존재하지 않는 키에 대한 연산을 할때 디폴트 값을 기준으로 딕셔너리 키:값을 생성해준다.

int, list 등 다양한 형태로 딕셔너리를 만들 수 있다.

list 딕셔너리는 키에 문자열도, 리스트도 삽입할 수 있다. 값을 넣어 줄 때는 리스트처럼 append를 사용하면 된다.

    a = collections.defaultdict(int) 
    a['key'] += 10
    print(a) #defaultdict(<class 'int'>, {'key': 10})
    
    b = collections.defaultdict(list) 
    b[0].append([1,2,3])
    b[0].append('to')
    print(b) #defaultdict(<class 'list'>, {0: [[1, 2, 3], 'to']})

2. Counter

Counter는 아이템에 대한 개수를 계산해 딕셔너리로 리턴한다. (개사기)

most_common(n) 로 Counter 객체의 n번째까지 빈도가 높은 요소를 출력할 수도 있다.  

    a = [2,4,1,1,1,1,5,5,5,3,6]
    b = collections.Counter(a)
    print(b) #Counter({1: 4, 5: 3, 2: 1, 4: 1, 3: 1, 6: 1})
    print(b.most_common(2)) #[(1, 4), (5, 3)]

+ 딕셔너리는 해시테이블을 이용한 자료형으로 입력 순서가 유지되지 않아 입력순서를 유지하려면 OrderedDict 이라는 객체를 사용해야했으나 파이썬 3.7부터는 딕셔너리도 내부적으로 인덱스를 이용해 입력 순서가 유지되도록 개선됐다.

Reference

책) 파이썬 알고리즘 인터뷰 (박상길) 

해시 문제를 풀다가 딕셔너리에 값을 추가하는 법에 대해 찾아보았다.

collections 라이브러리의 defaultdict 이라는 함수를 사용해서 값 추가가 가능하다. 

from collections import defaultdict
clothes=[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]
size=len(clothes)
dic=defaultdict(list)

for i in range(size):
    dic[clothes[i][1]].append(clothes[i][0])

print(dic)
print(dic.values())
print(dic.keys())
print()
dic['headgear'].remove('yellowhat')
print(dic)

위 실행결과를 보면 리스트 처럼 딕셔너리에 append(), remove() 함수를 사용할 수 있다.