본문 바로가기

프로그래밍 언어/python23

9663: N-Queen 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (1 ≤ N 출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.예제 입력 1 복사8예제 출력 1 복사92 첫 시도)def isSafe(board, x,y): N = len(board) #행의 최대 개수, 열의 최대 개수 # 이전 행y-1,y-2...의 x열에 1이 있나? # 왼쪽 대각선 (y-1,x-1) (y-2,x-2)...에 1이 있나? # 오른쪽 대각선 (y-1 ,X+1) for i in range(y): if(board[i][x]==.. 2025. 5. 28.
11050: 이항계수1 문제자연수 N\(N\)과 정수 K\(K\)가 주어졌을 때 이항 계수 (NK)\(\binom{N}{K}\)를 구하는 프로그램을 작성하시오.입력첫째 줄에 N\(N\)과 K\(K\)가 주어진다. (1 ≤ N\(N\) ≤ 10, 0 ≤ K\(K\) ≤ N\(N\))출력 (NK)\(\binom{N}{K}\)를 출력한다.예제 입력 1 복사5 2예제 출력 1 복사10 1) Divide and Conquer로 풀기n, k = map(int, input().split())def bino_coef(n,k): if(k==0 or k==n): return 1 return bino_coef(n-1,k-1)+ bino_coef(n-1,k)print(bino_coef(n,k)) 2) memoizationn.. 2025. 5. 7.
2747: 피보나치 수 문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.출력첫째 줄에 n번째 피보나치 수를 출력한다.예제 입력 1 복사10예제 출력 1 복사55 1) 재귀 -> 시간초과n = int(input().strip())def f.. 2025. 5. 7.
24051: 삽입정렬1 문제오늘도 서준이는 삽입 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 삽입 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.크기가 N인 배열에 대한 삽입 정렬 의사 코드는 다음과 같다.insertion_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다. for i 입력첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 저장 횟수 K(1 ≤ K ≤ N2)가 주어진다.다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)출력K 번째 저장 되는 수를 출력한다. 저장 .. 2025. 4. 12.
2740: 행렬의 곱셈 문제N*M크기의 행렬 A와 M*K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오.입력첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다.출력첫째 줄부터 N개의 줄에 행렬 A와 B를 곱한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.예제 입력 1 복사3 21 23 45 62 3-1 -2 00 0 3 예제 출력 1 복사-1 -2 6-3 -6 12-5 -10 18N, M = map(int, inp.. 2025. 4. 11.
11004: k번째 수 - 퀵정렬 Hoare 분할에서는 왼쪽에서 피벗보다 큰 값과 오른쪽에서 피벗보다 작은 값을 찾아 서로 교환합니다. 왼쪽도 잘못된 값이고 오른쪽도 잘못된 값일때 둘을 교환하는 것입니다.def partition(A, left, right): low = left + 1 high = right pivot = A[left] while low = left and A[high] > pivot: high -= 1 if low  Hoare partition algorithm의 목표는 [pivot 이하 값들] pivot [pivot 초과 값들] 이렇게 만드는 것입니다. pivot을 변경하며 반복하면 (퀵)정렬이 되는 것이지요.따라서 low는 pivot보다 큰 값을 찾으려고 오른쪽.. 2025. 4. 9.

티스토리툴바