문제세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1≤R,C≤20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다. 출력첫째 줄에 말이..

문제루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 예제 입력171 66 33 54 12 44 7 예제 입력2121 21 32 43 53 64 74 85 95 106 116 12 출력첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 출력1461314 예제 출력211233445566 코드풀이1 DFSimport syssys.setrecursionlimit(10**6)N = int(sys.stdin.readline())v = [0] * (N+1..

문제 설명크기가 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 연산이 주어질 때..