전체 글128 [백준 9663번] N-Queen in python 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력 1 8 예제 출력 1 92 이 문제는 기존의 프로그래머스에서도 다뤘던 문제여서 금방 풀 줄 알았다... 그런데 기억이 안나...ㅜ DFS와 재귀를 이용하여 푸는 문제. def check(lst,row): for i in range(row): if lst[i]==lst[row] or i-lst[i]==row-lst[row] or i+lst[i]==row+lst[row]: return Fa.. 2021. 11. 2. [백준 2108번] (Counter)통계학(평균, 중앙값, 최빈값, 범위) in python 문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. 출력 첫째 줄에는 산술평균을 출력한다. 소수점 이하 .. 2021. 11. 1. [백준 10989번] 수 정렬하기 3 in python 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 10 5 2 3 1 4 2 3 5 1 7 예제 출력 1 1 1 2 2 3 3 4 5 5 7 이번 문제는 시간 초과가 아니라 메모리에 대한 문제였다. 보통 정렬을 할때는 시간 복잡도를 줄이는데 이번엔 메모리 할당에 대한 문제가 나와 신선했다. 병합정렬을 쓰거나, 기존에 파이썬에 내장되어 있는 정렬함수를 써도 메모리 초과 문제를 해결할 수 없었다. 여러 블로그를.. 2021. 11. 1. 병합 정렬 in python 고급 정렬 중 병합정렬에 대해 공부해보자. 병합정렬은 모든 리스트의 요소를 한개의 배열로 쪼개고 하나씩 위로 올리면서 정렬을 하는 방식이다. 그래서 리스트의 모든 요소가 한개의 배열로 쪼개질 때, log(n)이고 각 요소를 정렬할 때 n의 복잡도가 들면서 최종적으로 O(nlog(N))의 복잡도가 든다. log(n)은 만약 8개의 요소가 있으면 각각을 한개로 쪼개는데 3번 분류된다. 2^3. 2의 몇승으로 늘어나기 때문에 log를 붙인다. 이걸 코드로 짜면 #병합정렬 def merge_sort(array): if len(array) 2021. 11. 1. [백준 1018번] 체스판 다시 칠하기 in python 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8.. 2021. 10. 29. [백준 11729번] 하노이 탑 이동 순서 in python 문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 입력 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다. 출력 첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈.. 2021. 10. 29. 이전 1 ··· 11 12 13 14 15 16 17 ··· 22 다음
