파이썬

문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 정답 소스코드 (Python) import sys sentence=sys.stdin.readline().rstrip() bomb=sys.stdin.readline().rstrip() bomb_len=len(bomb) stack=[] for i in range(len(sentence)): stack.append(sentence[i]) if ''.join(stack[-bomb_len:])==bomb: for j in range(bomb_len):..

문제 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 정답 소스코드 (Python) import heapq v,e=map(int,input().split()) graph=[[]for _ in range(v+1)] dis=[1e9]*(v+1) for i in range(e): v1,v2,e=map(int,input().split()) graph[v1].append([v2,e]) graph[v2].append([v1,e]) def dijkstra(start): q=[] heapq.heappush(q,(0,start)) d..

문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 정답 소스코드 (Python) n,d=map(int,input().split()) shortcut=[] for i in range(n):shortcut.append(list(map(int,input().split()))) shortcut.sort() dp=[i for i in range(d+1)] k=0 for i in range(d+1): dp[i]=min(dp[i-1]+1,dp[i]) while k

문제 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 정답 소스코드 (Python) n=int(input()) arr=[] for _ in range(n):arr.append(int(input())) dp=[1]*(n+1) lenth=0 for i in range(n): for j in range(i): if arr[i]>arr[j]: if dp[i]

문제 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 정답 소스코드 (Python) from itertools import permutations n=int(input()) baseball=list(permutations([1,2,3,4,5,6,7,8,9],3)) num,s_len,b_len="",0,0 for _ in range(n): num,s_len,b_len=input().split() s_len,b_len=int(s_len),int(b_len) delete=[] for i in range(len(ba..

문제 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 정답 소스코드 (Python) N=int(input()) def permutation(n,r,temp=[]): if r==0: return print(*temp) else: for i in range(1,n+1): if i not in temp: temp.append(i) permutation(n,r-1,temp) temp.remove(i) permutation(N,N) 풀이 (Python) 간단한 기본 문제로서 순열을 구현할 수 있으면 쉽게 풀 수 있는 문제이다. 직접 순열을 구현해봄으로써 재귀구조와 브루트포스에 공부가 되는 문제이기도 하다. 파..

완전탐색 ( Complete Search) 이란? 완전탐색을 알기 전에 상위 개념인 탐색에 대해 알아야 하는 탐색(Search) 알고리즘은 많은 데이터 중 목적에 맞는 데이터를 찾기 위한 방법이다. 탐색 알고리즘에는 여러 가지 탐색 방법이 존재하는데 완전 탐색은 그중 대표적인 알고리즘 중 하나이다. 완전탐색(Complete Search) 은 말그대로 "모든 경우의 수를 검사" 하는 방식으로 브루트포스( Bruth-Force) 알고리즘으로 불리기도 한다. "brute"는 "무식한", "force"는 "힘"을 의미하는데 무식한 힘 즉 무식하게 전체 모든 경우의 수를 검사하는 알고리즘을 의미한다. 완전탐색(Complete Search)은 전체 모든 경우의 수를 검사하기 때문에 매우 큰 메모리를 사용하며, 시간..

문제 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 정답 소스코드 (Python) arr=[] result=[] find_result=False sum=0 for i in range(9): tmp=int(input()) arr.append(tmp) sum+=tmp for i in range(9): for j in range(i+1,9): tmp_sum=sum-arr[i]-arr[j] if tmp_sum==100: result.extend([arr[i],arr[j]]) find_result=True break if f..

문제 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 정답 소스코드 (Python) from collections import deque n,k=map(int,input().split()) limit=100001 cnt=[0]*limit visited=[False]*limit def bfs(x,end): queue=deque() queue.append(x) while queue: x=queue.popleft() if x==end:return cnt[x] if -110 (+1..

문제 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 정답 소스코드 (Python) from collections import deque n,m=map(int,input().split()) field=[] visited=[[False for j in range(m)]for i in range(n)] arr=[[-1 for j in range(m)]for i in range(n)] for i in range(n): tmp=list(map(int,input().split..