Python

문제 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 정답 소스코드 (Python) def dfs(vert,start): visited[vert]=True value=field[vert] if not visited[value]:dfs(value,start) elif visited[value] and value==start:result.append(value) n=int(input()) field=[0] result=[] for i in range(n):field.append(int(input())..

문제 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):..

문제 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) 간단한 기본 문제로서 순열을 구현할 수 있으면 쉽게 풀 수 있는 문제이다. 직접 순열을 구현해봄으로써 재귀구조와 브루트포스에 공부가 되는 문제이기도 하다. 파..

문제 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..

문제 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 정답 소스코드 (Python) from collections import deque count,dx,dy=0,[0,0,1,-1],[1,-1,0,0] def bfs(): queue=deque() queue.append([0,0]) cost[0][0]=field[0][0] while queue: x,y=queue.popleft() for i in range(4): nx,ny=x+dx[i],y+dy[i] if -1

문제 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..

문제 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 정답 소스코드 (Python) def if_decimal(num): if num==1: return for i in range(2,int(num**0.5)+1): if num%i==0: return count.append(num) m,n=map(int,input().split()) count=[] # 몇 개 해당하는지 for i in range(m,n+1): if_decimal(i) # m과 n사이에 숫자 하나씩 확인 print(*count) 풀이 (Python) 어떤 수 n이 소수라는 ..

문제 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 정답 소스코드 (Python) def gcd(x,y): while(y): x,y=y,x%y return x num1,num2=map(int,input().split()) result=gcd(num1,num2) print(result) print(int(num1*num2/result)) 풀이 (Python) 이 문제는 최대공약수를 구하는 방법을 모른다면 힘든 문제이다. 두 수의 각자 약수를 구한 후 비교하여 최대공약수를 구하게 되면, 시간초과가 발생한다. 알고리즘 공부를 하게 되면 처음으로 수학 파트를 공부하게 되는데 이때 ..