개발새발문제

문제 설명크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제N 이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오 규칙- Queen은 가로 세로 대각선으로 이동할 수 있다  입력1 ≤ N   입력 예제8  출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.  출력 예제92    문제 풀이체스말을 놓을 수 있는지 확인 가로세로- dfs를 사용하여 행은 n(i)로 +1씩 더해주면서 확인하고, 열은 v1 배열을 사용하여 j 값을 1로 체크해준다 우상 대각선- 우상 대각선에는 규칙이 있다- i+j 값이 모두 같다(위의 초록색 라인은 합이 모두 4)- i+j 값은 2*N-1 개 좌상 대각선- 좌상 대각선에도 규칙이 있다- i-j 값이 모두 같다(위의..

우선순위큐일반적인 큐(Queue)는 선입 선출의 구조(FIFO, First In First Out)를 가지고 있다.하지만, 우선순위큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 의미한다.   우선순위 큐는,1. 모든 항목에 우선순위가 있다.2. 높은 우선순위를 가진 요소는 낮은 우선순위를 가진 요소보다 먼저 제거된다.3. 두 요소의 우선순위가 같으면 큐의 순서에 따라 제거된다.   우선순위큐는 최소 두 가지 연산을 가지고 있다.하나의 원소를 우선순위를 지정하여 추가하는 함수 push우선순위가 가장 높은 원소를 큐에서 제거하고 반환하는 함수 pop  우선순위큐는 힙(heap)이라는 자료 구조를 이용해 구현한다힙(heap)이란, 완전 이진트리로 부모 노드..

문제설명재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라. => 즉 a**b를 10으로 나눈  나머지를 구하는 문제 입력1. 테스트케이스의 개수 T2. a,b51 63 76 27 1009 635..

문제 설명이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)  입력값노드의 개수 N노드 왼쪽자식노드 오른쪽자식노드노드가 없는 경우 '.'루트노드는 항상 A  출력값전위 순회중위 순회후위 순회  풀이 1# 108384KB, 88ms(PyPy3)N = int(input())# 자식 노드 저장l = [0] * (N+1) #..

문제 설명- LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제- ex) ACAYKP와 CAPCAK의 LCS는 ACAK입력값1. 문자열12. 문자열2- 알파벳 대문자로만 이루어져 있으며 최대 1000글자 - 예제ACAYKPCAPCAK출력값- 두 문자열의 LCS 길이 - 예제 답 : 4   문제 풀이첫번째 시도 같은 패턴의 길이 중 가장 긴 길이를 출력하라는 줄 알고 잘못 풀었다..!# 단순히 패턴이 겹치는 것 중 긴 패턴을 찾으라는 줄 알고 잘못 품..!text = input()pattern = input()# 최장 길이 countmax_cnt = 0cnt = 0N = len(text)M..

문제설명fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.fibonacci(0)은 0을 출력하고, 0을 리턴한다.fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다. 1은 2번 출력되고, 0은 1번 출..

문제 설명- 가로 M, 세로 N, 높이 H의 토마토 상자- 보관 후 하루가 지나면 익은 토마토의 위, 아래, 왼쪽, 오른쪽, 앞 뒤 여섯 방향의 토마토는 익는다- 보관된 토마토들이 모두 익는데 소요되는 최소 일수입력값1. M, N, H ( 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 )2. N개의 줄까지 하ㅏ의 상자에 담긴 토마토의 정보- 1은 익은 토마토 0은 안익은 토마토 -1은 빈 공간- 토마토가 하나 이상 익은 경우만 입력으로 주어진다출력값- 토마토가 모두 익는데 걸리는 최소 일수- 저장될 때부터 모두 익어있으면 0 출력- 토마토가 모두 익지 못하는 상황이면 -1 종합 결과   첫번째 시도import copydef mature(h,r,c) : global time, t..

문제 설명N개의 과일이 꽂혀 있는 과일 탕후루과일은 1번부터 9번까지 번호가 있음한 꼬치에 과일을 두 종류 이하로 사용해야함앞에서 a개 뒤에서 b개를 빼서 N-(a+b)의 최댓값은?입력값N (1탕후루에 꽂힌 N개의 과일 번호출력값과일의 개수가 가장 많은 탕후루의 과일 개수  처음 생각한 풀이 코드# 반례발견! 오답# 반례 : 1 1 3 7 8 9 9 9import syssys.stdin = open('백준/test.txt')# 앞에서 제거def front(lst) : lst.pop(0) return lst# 뒤에서 제거def back(lst) : lst.pop() return lstN = int(input())tang = list(map(int,input().split()))# 탕후..

문제 설명필요하다고 생각하는 N개의 물건각 물건은 무게 W와 가치 V최대 K만큼의 무게를 들 수 있다제한시간 2초입력값N K (1N개의 줄에 거쳐 W V (1- 예제4 76 134 83 65 12 출력값배낭에 넣을 수 있는 물건들의 가치합의 최댓값- 예제 답 : 14  일반적으로 dfs로 푸는 방법을 생각할 수 있으나, 제한시간이 2초이고 N이 100개까지 있으므로 시간초과가 나기 쉽다 def dfs(n,sum_w, sum_v) : global max_v # 종료조건 if sum_w > K : if sum_v > max_v : max_v = sum_v return if n == N : if sum_v > max_v : ..

문제설명- 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램- add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.- remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.- check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)- toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)- all: S를 {1, 2, ..., 20} 으로 바꾼다.- empty: S를 공집합으로 바꾼다.입력값1. 수행해야 하는 연산의 수 M2. M개줄에 걸쳐 수행해야하는 연산이 한 줄에 하나씩 주어진다출력값check 연산이 주어질 때..

문제 설명- 자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 프로그램- A,B,C는 2,147,483,647 이하의 자연수  보기엔 단순해보이지만, 시간 제한이 타이트하고 자연수의 크기가 커서 시간초과가 나기 딱 쉬운 그런 문제 1. ** 연산자 사용import sysinput = sys.stdin.readlineA,B,C = map(int,input().split())ans = A**B%Cprint(ans) ** 연산자- x ** y 형태로 사용- 가장 짧고 간단한 방법으로 거듭제곱을 수행할 수 있음- ** 연산자는 내장 연산자이기 때문에 별도의 import 없이 사용 가능 특징** 의 반환값은 파라미터의 type에 따라 결정됨속도 측면에서 ** 연산자가 일반적으로 더 빠르다. 결과역시 시간초과..

1대1 가위바위보 Problem가위 1, 바위 2, 보 3이긴사람 출력  TRY1A,B =map(int, input().split())if A-B == 1 :    print("A")elif A-B == -1 :    print("B")elif A-B == 2 :    print("B")elif A-B == -2 :    print("A")  #값의 차이를 이용해 이기는 경우를 각각 지정함#elif문이 3개나 들어가 비효율적임 #실행시간 : 115ms  TRY2A,B =map(int, input().split())dif = A-Bif dif == 1 or dif == -2 :    print("A")elif dif == -1 or dif == 2 :    print("B")  #A와 B 값의 차이를 di..