본문 바로가기

전체 글

 (42)
20. 백준 1904 (실버3) : 01타일 _ python풀이 / DP 문제지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다.그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수..
19. 백준 11401 (골드1) : 이항계수3 _ python풀이 / 수학,페르마의소정리 문제자연수 N\(N\)과 정수 K\(K\)가 주어졌을 때 이항 계수 (NK)\(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.입력첫째 줄에 N\(N\)과 K\(K\)가 주어진다. (1 ≤ N\(N\) ≤ 4,000,000, 0 ≤ K\(K\) ≤ N\(N\))출력 (NK)\(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 출력한다.예제 입력 1 복사5 2예제 출력 1 복사10  *문제 해석이항계수 문제다. nCk를 1,000,000,007로 나눈 나머지를 출력하면 된다. nCk = n! / (n-k)! k! 이를 재귀 팩토리얼을 통해 풀려고 하면 스택오버플로우로 인해 계산하지 못하게 된다. 시간복잡도가 O(n^2)인데 n의 범위가 ..
18. 백준 5639 (골드4) : 이진검색트리 _ python풀이 / 이진트리 문제이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.이진 검색 트리를 전위 순회한 결과가 주어졌을 때..
17. 백준 10158 (실버3) : 개미 _ python풀이 / 애드 혹 문제가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매 시간마다 (6,4), (5,3), (4,..
16. 백준 9663 (골드4) : N-Queen _ python풀이 / 브루트포스 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (1 ≤ N 출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.예제 입력 1 복사8예제 출력 1 복사92 어떤 문제인지는 앞으로 제목에 적어둘 예정이다. *문제 해석 백트래킹하면 나오는 기본 문제인 N-Queen 문제다. 퀸이 서로를 공격할 수 없는 경우는 다음과 같다.1. 행과 열마다 한개의 퀸만 존재한다.2. 같은 대각선상에 퀸이 존재하지 않는다. '1'을 풀기 위해서는 각 행들을 하나의 리스트로 하고 리스트 별로 인덱스가 겹치지 않게 퀸을 배치하는 식으로 하면 될 것이다. ..
[Python] 순열과 조합 ( permutation, combination ) 순열 (permutation) 서로 다른 n개중 r개를 골라 순서를 정해 나열하는 가짓수를 의미한다. nPr 로 표기한다. 순서를 고려하기 때문에 만약 [A, B, C] 리스트가 있다면 [(A,B), (A,C), (B, C), (B, A), (C, A), (C, B)]가 나오게 된다. 요소가 동일 하더라도 순서가 다르면 다른 것으로 친다. *순서를 고려하며 중복은 허용하지 않는다. nPr = n! / (n-r)! python의 모듈 itertools를 통해 사용 가능하다. from itertools import permutationsarr = ['a','b','c']for i in permutatinos(arr,2): print(i) 단순 import permutations일 경우 사용시 itertool..

티스토리툴바