poorman

https://www.acmicpc.net/problem/10871

문제

정수 N개로 이루어진 수열 A와 정수 X가 주어진다. 이때, A에서 X보다 작은 수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000)

둘째 줄에 수열 A를 이루는 정수 N개가 주어진다. 주어지는 정수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

X보다 작은 수를 입력받은 순서대로 공백으로 구분해 출력한다. X보다 작은 수는 적어도 하나 존재한다.

해결 방안

1. filter 함수를 이용하여 X보다 작은 수만 필터링한다.

소스 코드

import sys
input = sys.stdin.readline

N,X = map(int, input().split())
A = map(int, input().split())
s = map(str, list(filter(lambda x: x < X, A)))
print(' '.join(s))

https://www.acmicpc.net/problem/15552

문제

본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다.

C++을 사용하고 있고 cin/cout을 사용하고자 한다면, cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자. 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.

Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다.

Python을 사용하고 있다면, input 대신 sys.stdin.readline을 사용할 수 있다. 단, 이때는 맨 끝의 개행문자까지 같이 입력받기 때문에 문자열을 저장하고 싶을 경우 .rstrip()을 추가로 해 주는 것이 좋다.

또한 입력과 출력 스트림은 별개이므로, 테스트케이스를 전부 입력받아서 저장한 뒤 전부 출력할 필요는 없다. 테스트케이스를 하나 받은 뒤 하나 출력해도 된다.

자세한 설명 및 다른 언어의 경우는 이 글에 설명되어 있다.

이 블로그 글에서 BOJ의 기타 여러 가지 팁을 볼 수 있다.

입력

첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다.

출력

각 테스트케이스마다 A+B를 한 줄에 하나씩 순서대로 출력한다.

해결 방안

1. sys.stdin.readline()을 이용하여 input()보다 빠른 입력을 받아 처리한다.

언어별 빠른 입출력 방법 : https://www.acmicpc.net/board/view/22716

BOJ 팁 : https://www.acmicpc.net/blog/view/55

소스 코드

import sys
input = sys.stdin.readline
N = int(input())
for n in range(N):
    x,y = map(int, input().split())
    print(x+y)

https://www.acmicpc.net/problem/1850

문제

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

입력

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 2^63보다 작은 자연수이다.

출력

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

해결방안

1. 같은 숫자로 이루어진 두 수의 최대공약수는 유클리드 호제법을 이용하여 자릿수 연산으로 구할 수 있다.

111/111/11 % 111 = 11
       (8) % (3) = (2)

소스코드

# Greatest Common Divisor
def GCD(x,y):
    x,y = max(x,y), min(x,y)
    while(y > 0):
        z = x % y
        if z == 0:
            return y
        x,y = y,z
    return x

x,y = map(int, input().split())
print('1'*GCD(x,y))

https://www.acmicpc.net/problem/1934

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

해결 방안

1. 유클리드 호제법을 이용하여 최대 공약수를 구한다. 

(https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95)

2. A, B의 최소공약수 = A * B // 최대공약수

소스코드

T = int(input())

# Greatest Common Divisor
def GCD(x,y):
    x,y = max(x,y), min(x,y)
    while(y > 0):
        z = x % y
        if z == 0:
            return y
        x,y = y,z
    return x

# Least Common Multiple
def LCM(x,y):
    return x * y // GCD(x,y)

for t in range(T):
    x,y = map(int, input().split())
    print(LCM(x,y))

https://www.acmicpc.net/problem/2839

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

해결 방안

1. 봉지의 수를 최소화 하기 위해서는 최대한 5킬로그램 봉지를 많이 사용하면 된다.

2. N을 5로 나눈 최대치에서 1씩 줄여가면서 남은 N값이 3으로 나누어 떨어지는 순간에 봉지 개수를 리턴한다.

3. 5와 3으로 나누어 떨어지지 않는 경우에 -1을 리턴한다.

소스 코드

N = int(input())

def count_bag(x):
    bag1 = 5
    bag2 = 3
    max_bag1 = x//5
    for i in range(max_bag1+1):
        cnt1 = max_bag1 - i
        rest_x = x-(cnt1*bag1)
        if rest_x % bag2 != 0:
            continue
        cnt2 = rest_x // bag2
        return cnt1 + cnt2
    return -1

print(count_bag(N))

https://www.acmicpc.net/problem/10826

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

해결 방안 - 1

1. 재귀 함수를 이용한다. f(n+2) = f(n+1) + f(n)

2-1. 함수 f(n)는 n이 0일때 0, 1일때 1을 리턴한다.

2-2. n이 2이상의 경우에 f(n-2) + f(n-1)을 리턴한다.

소스코드 - 1

n = int(input())

def fibonacci(x):
    if x == 0:    return 0
    if x == 1:    return 1
    return fibonacci(x-1) + fibonacci(x-2)
    
print("%d" % fibonacci(n))

*재귀 함수를 사용하는 경우에 x가 커질수록 메모리 사용량과 연산 시간이 증가하여 시간 초과로 실패한다.

해결 방안 - 2

1. Dynamic Programming 알고리즘으로 n-1, n-2번째의 수만 메모리에 갱신하여 연산해 나간다.

2. 파이썬의 특징을 활용하여 x, y = y, x+y 연산으로 x에는 n-1번째 값을, y에는 n-1번째와 n-2번째의 합을 취한다.

소스코드 - 2

n = int(input())

def fibonacci(k):
    x, y = 0, 1
    for i in range(k):
        x, y = y, x+y
    return x 

print("%d" % fibonacci(n))

[Time Complexity] Python - Find Value in List vs Set vs Dict

[시간 복잡도] 파이썬 - List vs Set vs Dict 에서 Value 찾기

결론

1. Set, Dict 에서 value를 찾을 경우에 시간 복잡도 O(1)로 가장 빠름

2. 다만 List to Set/Dict conversation이 필요한 경우에 일정 값 이하의 n에서는 List를 사용

[Time Complexity] Python - Deque vs List performance comparison (append, appendleft, pop, popleft)

[시간 복잡도] 파이썬 - Deque vs List 퍼포먼스 비교 (append, appendleft, pop, popleft)

결론

1. append와 pop의 경우에는 List와 Deque 둘 다 Time Complexity가 O(n)으로 별차이가 없음

2. appendleft와 popleft의 경우에 Deque가 훨씬 빠름

[Time Complexity] Python - Numpy vs List of zeros declaration

[시간 복잡도] 파이썬 - Numpy vs List의 제로 배열 선언 비교

결론

1. 제로 리스트 선언은 numpy.zeros가 가장 빠름

2. 다만 numpy to list 시간 복잡도가 O(n)이므로 리스트로 변환이 필요시에 [0] * n 가 가장 빠름

출처 : http://pythonstudy.xyz/python/article/401-%EC%A0%95%EA%B7%9C-%ED%91%9C%ED%98%84%EC%8B%9D-Regex

참조 : http://www.nextree.co.kr/p4327/