스칼렛의 코딩라이프

백트래킹 문제 2 백트래킹문제는 항상 실제로 아날로그식으로 풀면 규칙도 다 알겠는데 코드 구현으로 이어지지가 않는게 문제인 것 같다. 스도쿠,, 어릴 때 심심풀이로 엄청 풀었던 것 같은데.. def get_ans(x,y): numlist=[str(i) for i in range(1,10)] row=[sdoku[x][i] for i in range(9)] column=[sdoku[i][y] for i in range(9)] used=list(set(row+column)) for i in used: if i in numlist: numlist.remove(i) if len(numlist)==1: sdoku[x][y]=numlist[0] else: cell=get_square(x//3+1,y//3+1) for..

문제를 보자마자 무슨 뜻인지는 알겠는데 구체적으로 어떻게 구현을 해야 할 지 너무 막막했다. 백트래킹 알고리즘에서 아주 유명한 알고리즘이라 다른 블로그를 참고하여서 이해했다. def nqueen(sol,N): global count if len(sol)==N: count+=1 return 0 candidate=list(range(N)) for i in range(len(sol)): if sol[i] in candidate: candidate.remove(sol[i]) distance=len(sol)-i if sol[i]+distance in candidate: candidate.remove(sol[i]+distance) if sol[i]-distance in candidate: candidate.remo..

비내림차순이라고 하는 이유가 같은 수가 있어서 그런거였구나.. from itertools import combinations_with_replacement N,M=map(int,input().split()) numlist=map(str,range(1,N+1)) setlist=list(combinations_with_replacement(numlist,M)) print('\n'.join(list(map(' '.join,setlist)))) itertools 라이브러리에서 조합과 순열 관련한 함수들을 모조리 다 써보는 문제였군. 이 라이브러리를 몰랐다면,, 아마 답답함에 몸부림 쳤을 듯 싶다. 이번에는 combinations_with_replace(arr,n) 함수를 써서 풀었다. 아주 유익한 라이브러리인 ..

중복을 포함한 조합을 출력하는 문제 역시나 itertools 라이브러리의 product 함수를 활용하면 바로 나온다. from itertools import product N,M=map(int,input().split()) numlist=map(str,range(1,N+1)) setlist=sorted(list(product(numlist,repeat=M))) print('\n'.join(list(map(' '.join,setlist)))) 예전에는 어떻게든 내 힘으로 풀려고 했었는데, (아는것도 없으면서..) 지금은 내가 필요한 function을 가지고 있는 라이브러리를 구글링해서 푸니까 훨씬 좋은 것 같다. (어차피 쓰라고 만들어 놓은 라이브러리니까..)

바로 전 문제는 순열문제였던 것 같은데 이번에는 조합 문제! from itertools import combinations N,M=map(int,input().split()) numlist=map(str,range(1,N+1)) setlist=sorted(list(combinations(numlist,M))) print('\n'.join(list(map(' '.join,setlist)))) 어차피 순서대로 조합이 만들어지는 거긴 하지만 Sort를 했다.

처음엔 굉장히 쉬워보였는데, M값을 왜 받아야 하지.. 라고 생각했는데 역시나 필요했다. 재귀함수를 써 볼까 생각도 했는데 왠지 파이썬에는 이미 구현되어 있는 함수가 있을 것 같아서 열심히 구글링을 했다. from itertools import permutations N,M=map(int,input().split()) numlist=[i for i in range(1,N+1)] setlist=list(permutations(numlist,M)) for i in range(len(setlist)): for j in range(M): print(setlist[i][j],end=' ') print() 재귀함수를 구현 해 볼까 했는데 굉장히 골치가 아파보여서 굳이..? 라는 생각이 들었다. 있는 것을 잘 활용하..