백준 문제 풀이 (12) 썸네일형 리스트형 [백준] 9663 "N-Queen" -python 알고리즘 대각선에 퀸이 존재하는지 여부를 체크하는 배열 2개와 같은 행에 퀸이 존재하는지 여부를 따지는 배열 1개를 두고 백트래킹을 실행한다. 종료조건은 행을 1번씩 늘리면서 행번호가 입력 N과 같은 경우이다. 소스코드 import sys N = int(sys.stdin.readline()) result = 0 isused1 = [0] * N isused2 = [0] * (N * 2) isused3 = [0] * (N * 2) def func(k): global result if k == N: result += 1 return for i in range(0, N): if isused1[i] or isused2[k+i] or isused3[k-i+N-1]: continue isused1[i] = 1 isu.. [백준] 15651 "N과 M (3)" -python 알고리즘 백트래킹을 통해 모든 중복가능한 조합을 찾아 출력한다. 소스코드 # N과 M (3) import sys n, m = map(int, sys.stdin.readline().split()) arr = [0] * m def func(k): if k == m: for i in arr: print(i, end=" ") print() return for i in range(1, n+1): arr[k] = i func(k+1) func(0) 참고 : https://blog.encrypted.gg/945 [백준] 15560 "N과 M (2)" -python 알고리즘 백트래킹을 통해 구현한다. 소스 코드 # N과 M 2 import sys n, m = map(int, sys.stdin.readline().split()) arr = [0] * m # 수열 저장 isused = [False] * (n + 1) s = set() def func(k): if k == m: s.add(tuple(sorted(arr))) return for i in range(1, n + 1): if not isused[i]: arr[k] = i isused[i] = True func(k+1) isused[i] = False func(0) for i in sorted(list(s)): print(*i) 참고 : https://blog.encrypted.gg/945 [백준] 1339 "단어 수학" -python https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 알고리즘 입력으로 주어진 모든 단어의 알파벳에 대해 자릿수를 구하고 그 합을 구한다. 예를 들어, 단어 ABCDA에서 A의 자릿수는 10001 ( A 관점에서 각 자리수에 A가 있는 부분에 1 아니면 0 ) 모든 알파벳에 대하여 자릿수를 구한 뒤 더해서 저장해 둔다. 모든 단어에서 하나의 알파벳 관점으로 볼 때 최적해를 구하는 그리디 알고리즘이다. # 단어수학 import sys, colle.. 이전 1 2 다음
