본문 바로가기

알고리즘/백준 (Pyhthon)

 (79)
[알고리즘] 백준 9663 N-Queen / python, 백트랙킹 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ✔ 풀이과정 같은 열과 대각선에 안겹치게 퀸을 놓는 게임을 구현한다. 먼저, 같은 열을 체크한다. ck배열은 크기가 N이고, 퀸을 놓은 위치의 열을 표시한다. ck_col[2] = 1 대각선을 체크한다. 대각선의 총 개수는 7개 이므로 ck배열의 크기는 2 * N - 1 이다. 퀸을 놓은 대각선의 규칙을 찾아보면 위치가 행=1, 열=2 일 때 3이므로 ck_dig[행+열] = 1로 바꾼다. 반대쪽 대각선을 체크한..
[알고리즘] 백준 1248 맞춰봐 / python, 백트랙킹 https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 문제 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 www.acmicpc.net ✔ 풀이과정 첫째 줄에 수열의 크기 N이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문자는 두 번째 줄에 해당한다. 예제에서 첫번째줄 : -+0+ / 두번째줄 : +++ / 세번째줄 : -- / 네번째줄:+ 이다. A = [-2, 5, -3, 1]일 때, 부호의 뜻은 첫번째줄 : A[0], A[0]+A[1], A[0]+A[1]+A[2], A[0]+A[1]..
[알고리즘] 백준 1339 단어수학 / python https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net ✔ 풀이과정 원래는 순열을 이용하는것같은데.. 파이썬은 딕셔너리를 사용해야지 시간초과가 안나나보다😢 딕셔너리에 각 숫자의 자리값을 저장해놓고 내림차순으로 정렬한다음, 제일 큰 수인 9부터 곱해준다. 이 예제로 설명하자면 dictionary = { G:100, C:1010, F:1, A:10000, D:100, E:10, B:1 } 이렇게 자리값을 10의 n승으로 저장한다. sort_list ..
[알고리즘] 백준 2529 부등호 / python https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력� www.acmicpc.net #순열이 오름차순일때 사용하는 함수 def next_permu(a): i = len(a)-1 while i > 0 and a[i-1] >= a[i]: i -= 1 if i
[알고리즘] 백준 14889 스타트와 링크 / python https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net def next_permutation(a): n = len(a) - 1 i = n while i > 0 and a[i-1] >= a[i]: i -= 1 if i == 0: return False j = n while a[i-1] >= a[j]: j -= 1 a[i-1], a[j] = a[j], a[i-1] j = n while i < j: a[i], a[j] = a[j], a[i] i += 1 j -= 1 return..
[알고리즘] 백준 10974 모든 순열 / python, 순열 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net def next_permutation(a): n = len(a) - 1 i = n while i > 0 and a[i-1] >= a[i]: i -= 1 if i == 0: return False j = n while a[i-1] >= a[j]: j -= 1 a[i-1], a[j] = a[j], a[i-1] j = n while i < j: a[i], a[j] = a[j], a[i] i += 1 j -= 1 return True a = [i+1 for i in range(int(input..
[알고리즘] 백준 1748 수 이어 쓰기 / python https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net N = input() result = 0 for i in range(len(N)-1): result += 9 * (10**i) * (i+1) else: result += (int(N) - 10**(len(N)-1) + 1) * len(N) print(result)
[알고리즘] 백준 1107 리모컨 / python, 브루트포스 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net N = int(input()) M = int(input()) if M != 0: B = list(input().split()) else: B = [] R = [str(i) for i in range(10) if str(i) not in B] result = abs(N - 100) for i in range(1000000): tf = True for s in str(i): if ..

티스토리툴바