시간초과

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

문제 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이 소수라는 ..

알고리즘 공부를 시작하기 앞서 기본적으로 먼저 다뤄야 할 수학 부분에서는 대표유형으로 크게 나누면 약수, 소수, 최대공약수와 최소 공배수 유형으로 나누어 볼 수 있다. 각 유형별로 알아야 할 포인트를 다뤄보도록 하겠다. 약수 약수를 구하는 방법은 어떤 자연수N이 존재하는 경우 N이하의 자연수로 N을 나누었을 때 나머지가 0이면, 해당 N이하의 자연수는 자연수N의 약수이다. 어떤 자연수 N이 37일 때 코드로 작성하면 다음과 같다. n=36 for i in range(1,n+1): if n%i==0:print(i,end=" ") 결과: 1 2 3 4 6 9 12 18 36 하지만 이와 같이 작성하면 시간 복잡도는 O(n)으로 자연수 N이 10^8이 되는 경우 1초의 시간이 걸리게 된다. 더 적은 시간이 걸..

문제 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 (Python) import sys input=sys.stdin.readline # A~Z 는 아스키코드로 65부터 26개이다. y_max,x_max=map(int,input().split()) arr=[] for _ in range(y_max):arr.append(list(map(ord,list(input())))) # ord를 통해 아스키코드로 변환 visited=[False]*26 # 방문 여부 확인 result=0 # d[0]:우 d[1..

문제 28278번: 스택 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net 풀이 (Python) import sys input=sys.stdin.readline n=int(input()) input_arr=[] stack=[] def is_empty(): if len(stack)==0: return True return False for _ in range(n): input_arr=list(map(int,input().split())) if input_arr[0]==1: stack.append(input_arr[1]) elif input_arr[0]==2: ..

문제 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 (Python) from collections import deque n=int(input()) queue=deque() for i in range(1,n+1):queue.append(i) while True: if len(queue)==1: break queue.popleft() queue.append(queue[0]) queue.popleft() print(*queue) 설명 (Python) 설명과 함께 첫 풀이 과정으로 풀이하겠다. 문제에서 제시..

문제 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 (Python) import heapq import sys N=int(input()) num=0 Heapq=[] for i in range(N): num=int(sys.stdin.readline()) if num==0: if len(Heapq)==0:print(0) else: print(-Heapq[0]) heapq.heappop(Heapq) else: heapq.heappush(Heapq,-num) 설명 (Python) 힙(He..

│문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net │풀이 (Python) memo={0:0,1:1,2:2} def tileFill(n): if n in memo: return memo[n] else: memo[n]=tileFill(n-1)+tileFill(n-2) return memo[n] n=int(input()) print(tileFill(n)%10007) │설명 (Python) 2xn 타일링 문제 풀이에 관해 생각의 흐름은 경우의 수이다. 세로로 한개의 타일이 있다고 가정할 때 다음 타일이 올 수 있는 경우의 수는 2개이..

│문제 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net │풀이 T=int(input()) memo ={1:1,2:1,3:1,4:2,5:2} def equilTriangle(n): if n in memo: return memo[n] memo[n]=equilTriangle(n-5)+equilTriangle(n-1) return memo[n] for i in range(T): print(equilTriangle(int(input()))) │설명 왼쪽의 그림을 보고 규칙을 찾기 위해 첫 번째 삼각형을 A1, n번째 삼각형..

│문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net │풀이 (Python) def fibo(n): if n