[Baekjoon 문제풀이] 1463 - 1로 만들기 (Python 3)

서론 본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다. 대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다. 문제 Baekjoon 1463번 - 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 해법 Top-Down 방식의 재귀호출로 이 문제를 해결하려고 하면 시간초과로 막히게 될 것이다(사실 필자가 그랬다.) 사실 뭔가 재귀를 써야한다 싶으면 사실 Top-Down으로 풀어도 되는 문제는 없다... 그래서 아무튼 이번 문제는 Memoization을 통한 Bottom-Up DP를 사용해야 해결할 ..

• format_list_bulleted SW/Baekjoon
• · 2022. 1. 10.
• textsms

[Baekjoon 문제풀이] 1934 - 최소공배수 (Python 3)

서론 본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다. 대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다. 문제 Baekjoon 1934번 - 최소공배수 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 해법 이번 문제는 주어진 A, B에 대하여 두 수의 최소공배수를 구하는 문제다. 이번 문제는 "유클리드 호제법"을 이용하면 쉽게 해결할 수 있다. 우선 유클리드 호제법을 ..

• format_list_bulleted SW/Baekjoon
• · 2022. 1. 6.
• textsms

[Baekjoon 문제풀이] 4948 - 베르트랑 공준 (Python 3)

서론 본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다. 대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다. 문제 Baekjoon 4948번 - 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 해법 이번 문제는 주어진 정수 N에 대하여, N보다 크고 2N보다 작거나 같은 소수의 개수를 출력하는 문제다. 이번 문제도 에라토스테네스의 체를 사용하면 쉽게 해결할 수 있는데, ..

• format_list_bulleted SW/Baekjoon
• · 2022. 1. 6.
• textsms

[Baekjoon 문제풀이] 1011 - Fly me to the Alpha Centauri (Python 3)

서론 본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다. 대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다. 문제 Baekjoon 1011번 - Fly me to the Alpha Centauri: https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 해법 이번 문제는 주어진 X지점에서 Y지점까지 이동하기 위해 공간이동장치를 최소 몇번 작동시켜야 하는지..

• format_list_bulleted SW/Baekjoon
• · 2022. 1. 6.
• textsms

[Baekjoon 문제풀이] 11653 - 소인수분해 (Python 3)

서론 본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다. 대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다. 문제 Baekjoon 11653번 - 소인수분해: https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 해법 이번 문제는 어떤 임의의 정수 N이 주어질때 이 N을 소인수분해하는 과정을 출력하는 문제이다. 소인수분해 작업은 대상이 작은 수라면 큰 문제가 되지 않겠지만 수가 커지면 커질 수록 필요한 작업량이 기하급수적으로 증가하게 된다. 특히 이번 문제는 주어진 N의 범위가 1 ≤ N ≤ 10,000,000로 제..

• format_list_bulleted SW/Baekjoon
• · 2022. 1. 4.
• textsms

[Baekjoon 문제풀이] 4153 - 직각삼각형 (Python 3)

서론 본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다. 대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다. 문제 Baekjoon 4153번 - 직각삼각형: https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 해법 이번 문제는 피타고라스의 정리를 이용하면 간단하게 해결할 수 있다. 테스트 케이스의 입력을 받은 후, 받은 수 중 가장 큰 값의 제곱이 나머지 두 수를 각각 제곱한 후 더한 값과 같다면 "right"를..

• format_list_bulleted SW/Baekjoon
• · 2022. 1. 4.
• textsms