Kim Jisong

I am an amazing person.

Backjoon Algorithm 1-1: Math1

Introduction

Basic

나머지

pass

최대공약수와 최소공배수

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

  • 최대공약수: 0이 아닌 두 개 이상의 정수의 공통되는 약수
    • 유클리드 호제법 사용: 2개의 자연수 a, b(a>b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
a = 24
b = 18

r = a%b
while r != 0:
  big = b
  small = r
  r = big%small
print(small)
>> 6
  • 최소공배수: 2개 이상의 수의 공배수 중 가장 최소인 값을 소인수분해하여 각 수 중 어느 한 곳에라도 있는 약수를 찾아 곱해준 값
    • a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈것과 같다.
a = 24
b = 18

r = a%b
while r != 0:
  big = b
  small = r
  r = big%small
print(int(a*b/small))
>> 72
import sys
input = sys.stdin.readline

num1, num2 = map(int,input().split())

def GCD(b, s):
    big = b
    small = s
    r = big%small
    while r!=0:
        big = small
        small = r
        r = big%small
    return small

if (num1>num2):
    big = num1
    small = num2
else:
    big = num2
    small = num1

gcd = GCD(big,small)
print(gcd)
print(int(big*small/gcd))

최소공배수

소수 찾기

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

import sys
input = sys.stdin.readline

N = int(input())
numbers = list(map(int,input().split()))

lists = []

for n in range(2, 1001):
    for i in range(2, n):
        if n % i == 0:
            break
    else:
        lists.append(n)

cnt = 0
for num in numbers:
    if num in lists:
        cnt += 1
print(cnt)

소수 구하기

골드바흐의 추측

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

첫번째 시도

import sys
input = sys.stdin.readline

# 입력
numbers = []
N = int(input())
while N!=0:
    numbers.append(N)
    N = int(input())

# 소수 리스트 생성
lists = []
for n in range(3,max(numbers)):
    for i in range(3,n):
        if n%i == 0:
            break
    else:
        lists.append(n)

# 계산
result = {}
for num in numbers:
    # num 값에 맞는 소수 리스트 가져오기
    dummy_list = []
    if num != max(numbers):
        cnt = 0
        for i in range(len(lists)):
            if lists[i]>num:
                cnt=i
                break
        dummy_list = lists[:cnt]
    else:
        dummy_list = lists[:]
    
    # num 값에 맞는 소수 리스트 출력
    result[num] = [-1,-1]
    findFlag = False
    for big in range(len(dummy_list)-1,-1,-1):
        for small in range(0,len(dummy_list)):
            if num == dummy_list[big]+dummy_list[small]:
                result[num] = [dummy_list[small],dummy_list[big]]
                findFlag = True
                break
            elif num < dummy_list[big]+dummy_list[small]:
                break
        if findFlag == True:
            break

# 출력
for num in numbers:
    if result[num][0]!=-1 and result[num][1]!=-1:
        print("{0} = {1} + {2}".format(num,result[num][0],result[num][1]))
    else:
        print("Goldbach's conjecture is wrong.")

에라토스테네스의 체

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

  • 2부터 N까지 모든 정수를 적는다.
  • 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
  • P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
  • 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
import math

# 소수 판별 함수(에라토스테네스의 체)
def is_prime_number(n):
    # 2부터 n까지의 모든 수에 대하여 소수 판별
    array = [True for i in range(n+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)

    # 에라토스테네스의 체
    for i in range(2, int(math.sqrt(n)) + 1): #2부터 n의 제곱근까지의 모든 수를 확인하며
        if array[i] == True: # i가 소수인 경우(남은 수인 경우)
            # i를 제외한 i의 모든 배수를 지우기
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1

    return [ i for i in range(2, n+1) if array[i] ]

팩토리얼

pass

팩토리얼 0의 개수

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

import sys
input = sys.stdin.readline

# 값 초기화
N = int(input())

if N == 0:
    print(0)
else:
    pactorial = 1
    for i in range(1,N+1):
        pactorial*=i
    cnt = 0
    s = str(pactorial)
    for i in range(len(s)-1,-1,-1):
        if s[i] != '0':
            break
        cnt += 1
    print(cnt)

조합 0의 개수

Practice

GCD 합

숨바꼭질 6

2진수 8진수

8진수 2진수

-2진수

골드바흐 파티션

Plus

진법 변환 2

진법 변환

Base Conversion

소인수 분해

2022

Stack

1 minute read

Introduction

Stack

less than 1 minute read

Introduction

Download-only-one-directory

less than 1 minute read

Git 명령어를 사용한 하위 디렉토리 다운로드 Clone 할 로컬 저장소 생성

Sort

3 minute read

Introduction

Tree

less than 1 minute read

Introduction

Mutex library on C++

less than 1 minute read

#include <iostream> #include <thread> #include <chrono> #include <mutex> #include <atomic> #include <string.h>

TODO

less than 1 minute read

how to costom github blog using jekyll

Welcome to Jekyll!

less than 1 minute read

You’ll find this post in your _posts directory. Go ahead and edit it and re-build the site to see your changes. You can rebuild the site in many different wa...

Back to top ↑