https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net * 유클리드 호제법이란? - 즉, a,b의 최대공약수는 b,r의 최대공약수와 같다는 것이다. n,m = map(int,input().split()) def Eucliden(a, b): while(b != 0): r = a % b a = b b = r return a print(Eucliden(n,m)) print(n*m // (Eucliden(n,m))) - 따라서 b가 0이 아닌 동안 b를 a에 넣고 a를 b로 나눈 나머지를 b에 넣는 과정을 반복했다. - 9번째..
https://www.acmicpc.net/problem/5430 5430번: AC 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. www.acmicpc.net import sys,collections input = sys.stdin.readline t = int(input()) for _ in ra..
https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 www.acmicpc.net import sys input = sys.stdin.readline t = int(input()) for i in range(t): q..
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 이중연결리스트 문제를 풀고 삘받아 원형연결리스트문제까지 도전해보았다. 이것도 역시 단순 수식으로 짧게 푸는 방법도 있지만, 원형 연결리스트로 풀어보았다. import sys input = sys.stdin.readline class CList: class Node: def __init__(self,item,link): self.item = item self.next = link def __init__(self): self.last = None self.size = 0 def insert(..
https://www.acmicpc.net/problem/1406 1406번: 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 www.acmicpc.net 처음에 단순히 전에 풀었던 스택/큐/덱 문제처럼 접근해서 리스트로 풀었더니 시간 초과가 나왔다. list.insert가 O(n)이고 list..
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다. www.acmicpc.net 분류에 이분 탐색이라 되어 있어서 열심히 이분 탐색을 공부해서 풀었다. import sys input = sys.stdin.readline n = int(input()) L = list(map(int, input().split())) m = int(input()) mL = list(map(..
백준 1929번 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) www.acmicpc.net * prime함수 : n을 매개변수로 넘겨받아 1부터 n-1까지 n%i = 0이면 a에 1을 더해줘서 최종적으로 a가 1이면 (모든 수는 1로 나누어지므로 모든 수의 a는 최소1이다) 소수 -> True 반환 * a,b를 입력받아 list1에 소수인 것들만 append해줬다. * a와 b가 100만까지 들어오다보니 이 방법으로는 시간초과가 발생하였다. * 따라서 새로운 방법인 '에라토스테네스의 체'를 사용해보았다. import math def get_primes(a,b..
모르는 사이에 조금씩 조금씩..
