여름의 서재

V개 이내의 노드를 E개의 간선으로 연결한 방향성 그래프에 대한 정보가 주어질 때, 특정한 두 개의 노드에 경로가 존재하는지 확인하는 프로그램을 만드시오. 두 개의 노드에 대해 경로가 있으면 1, 없으면 0을 출력한다. 예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경로를 찾는 경우, 경로가 존재하므로 1을 출력한다. 노드번호는 1번부터 존재하며, V개의 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다. [입력] 첫 줄에 테스트 케이스 개수 T가 주어진다. 1≤T≤50 다음 줄부터 테스트 케이스의 첫 줄에 V와 E가 주어진다. 5≤V≤50, 4≤E≤1000 테스트케이스의 둘째 줄부터 E개의 줄에 걸쳐, 출발 도착 노드로 간선 정보가 주어진다. E개의 줄 이후에는 경로의 존재를 확인할 출발..

📕 문제 평소에 잔머리가 발달하고 게으른 철수는 비밀번호를 기억하는 것이 너무 귀찮았습니다. 적어서 가지고 다니고 싶지만 누가 볼까봐 걱정입니다. 한가지 생각을 해냅니다. 0~9로 이루어진 번호 문자열에서 같은 번호로 붙어있는 쌍들을 소거하고 남은 번호를 비밀번호로 만드는 것입니다. 번호 쌍이 소거되고 소거된 번호 쌍의 좌우 번호가 같은 번호이면 또 소거 할 수 있습니다. 예를 들어 아래의 번호 열을 철수의 방법으로 소거하고 알아낸 비밀 번호입니다. [입력] 10개의 테스트 케이스가 10줄에 걸쳐, 한 줄에 테스트 케이스 하나씩 제공된다. 각 테스트 케이스는 우선 문자열이 포함하는 문자의 총 수가 주어지고, 공백을 둔 다음 번호 문자열이 공백 없이 제공된다. 문자열은 0~9로 구성되며 문자열의 길이 N은..

📕 문제 그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다. 길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다. 다음과 같이 길이 주어질 때, A도시에서 B도시로 가는 길이 존재하는지 알아내는 프로그램을 작성하여라. - A와 B는 숫자 0과 99으로 고정된다. - 모든 길은 순서쌍으로 나타내어진다. 위 예시에서 2번에서 출발 할 수 있는 길의 표현은 (2, 5), (2, 9)로 나타낼 수 있다. - 가는 길의 개수와 상관없이 한가지 길이라도 존재한다면 길이 존재하는 것이다. - 단 화살표 방향을 거슬러 돌아갈 수는 없다. from collections import defaultdict def dfs(S): ..

📕 문제 어린이 알고리즘 교실의 선생님은 경우의 수 놀이를 위해, 그림처럼 가로x세로 길이가 10x20, 20x20인 직사각형 종이를 잔뜩 준비했다. 그리고 교실 바닥에 20xN 크기의 직사각형을 테이프로 표시하고, 이 안에 준비한 종이를 빈틈없이 붙이는 방법을 찾아보려고 한다. N이 30인 경우 다음 그림처럼 종이를 붙일 수 있다. 10의 배수인 N이 주어졌을 때, 종이를 붙이는 모든 경우를 찾으려면 테이프로 만든 표시한 영역을 몇 개나 만들어야 되는지 계산하는 프로그램을 만드시오. 직사각형 종이가 모자라는 경우는 없다. # DP 알고리즘 이용 def paper(n): lst = [1, 3] for i in range(2, n): lst.append(lst[i-1] + lst[i-2]*2) return..

📕 문제 크기가 N인 파스칼의 삼각형을 만들어야 한다. 파스칼의 삼각형이란 아래와 같은 규칙을 따른다. 1. 첫 번째 줄은 항상 숫자 1이다. 2. 두 번째 줄부터 각 숫자들은 자신의 왼쪽과 오른쪽 위의 숫자의 합으로 구성된다. N이 4일 경우, N을 입력 받아 크기 N인 파스칼의 삼각형을 출력하는 프로그램을 작성하시오. # 동적계획법 이용 # 메모이제이션 이용 def pascal_triangle(n): pascal = [[1]] for i in range(1, n): lst = [1] m = 0 while m+1 < len(pascal[i-1]): lst.append(pascal[i-1][m]+pascal[i-1][m+1]) m += 1 lst.append(1) pascal.append(lst) ret..

📕 문제 주어진 100x100 평면 글자판에서 가로, 세로를 모두 보아 가장 긴 회문의 길이를 구하는 문제 def long_palindrome(N, M, matrix): for i in range(N): for j in range(0, N-M+1): if matrix[i][j] == matrix[i][j+M-1]: for k in range(1, M): if matrix[i][j+k] != matrix[i][j+M-1-k]: break else: return True for i in range(N): for j in range(0, N-M+1): if matrix[j][i] == matrix[j+M-1][i]: for k in range(1, M): if matrix[j+k][i] != matrix[j+..

📕 문제 어떤 문자열 A를 타이핑하려고 한다. 그냥 한 글자씩 타이핑 한다면 A의 길이만큼 키를 눌러야 할 것이다. 여기에 속도를 조금 더 높이기 위해 어떤 문자열 B가 저장되어 있어서 키를 한번 누른 것으로 B전체를 타이핑 할 수 있다. 이미 타이핑 한 문자를 지우는 것은 불가능하다. 예를 들어 A=”asakusa”, B=”sa”일 때, 다음 그림과 같이 B를 두 번 사용하면 5번 만에 A를 타이핑 할 수 있다. A와 B가 주어질 때 A 전체를 타이핑 하기 위해 키를 눌러야 하는 횟수의 최솟값을 구하여라. # 보이어 무어 알고리즘 이용 def find(pattern, char): # 얼마나 움직일지 결정하는 함수 for i in range(len(pattern) - 2, -1, -1): # 마지막글자와..

📕 문제 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다. T = int(input()) for tc in range(T): steels = input() steels_list = [] cnt = 0 i = 0 while i < len(steels): if steels[i] == '(': if steels[i+1] != ')': steels_list.append(i) i += 1 else: cnt += len(steels_list) i += 2 else: cnt += 1 steels_list.pop() i += 1 print('#{0} {1}'.format(tc+1, cnt))