(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 1112 진법 변환 파이썬(Python)
진법을 변환하는 정수론 문제.
기본적으로, 이진법 변환은 고등학생도 할 수 있는 문제고, 그걸 B진법으로 확장하는 것도 딱히 어려운 일은 아니다.
이 문제의 어려운 부분은 음수 진법을 계산하는 부분인데, 얼핏 보았을 때는 비직관적이라 약간의 고민이 필요하다.
사실 그것도 예제들을 천천히 살펴보면 쉽게 떠올릴 수 있다.
\(12345_{(-10)}\)은 \(8265_{(10)}\)인데, 자릿수를 하나씩 살펴보면 규칙성을 찾을 수 있다.
우선, \(b^2i = (-b)^2i\)이므로, 홀수 자릿수(0부터 셌을 때)를 유심히 봐야 함을 직관적으로 생각할 수 있다.
이를테면 1번째 자릿수를 보면 각각 6, 4이고, 3번째 자릿수를 보면 2, 8인데, 즉 해당 자릿수를 10에서 뺀 값을 취하고 있는 것이다.
일반화하자면, 진법을 변환한 후 홀수 번째 자릿수에서 B의 보수(정확히는 abs(b)의 보수)를 취해주면 홀수 번째 자릿수를 알아낼 수 있다는 뜻이다.
그렇다면 짝수 번째 자릿수는 어떤가? 홀수 번째 자릿수에서 B의 보수를 취했다는 말은, 같은 수를 나타낼 때, \(+B^{i} \times N_{i}\) 대신 \(-B^{i} \times (B - N_{i})\)를 사용했다는 것이고, 이 둘간의 차는 \(B^{i}N_{i} + B^{i}(B - N_{i}) = B^{i+1}\)이다.
즉, \(i\)번째 자리에서 그 자릿수가 홀수 번째라 보수를 취했다면 그 다음 자릿수(\(i+1\))의 수에 1을 더해주면 되는 것이다.
이를 위 예시에 적용해보면 5는 그대로 5고, 6은 보수를 취해 4가 되고, 2는 1을 더해 3이 되고, 8은 보수를 취해 2가 되고, 마지막에 0(\(8625 = 08625\)이므로)은 1을 더해 1이 된다.
즉, 풀이가 잘 맞아떨어짐을 알 수 있다.
이제, 이대로 구현만 하면 되는데, 이를 간단하게 구현하기 위해서는 음수의 몫과 나머지 계산을 잘 활용하면 된다.
마지막으로, 음수를 양수 진법으로 변환하는 과정(\(N < 0 \land B > 0\))은 양수를 양수 진법으로 변환하고 거기에 -를 붙인 것과 동일하므로 예외처리를 해주면 된다.
#!python
# n을 b진법으로 변환하는 함수
def solve(n, b):
q, r = divmod(n, b)
if not q:
return abs(r)
return 10 * solve(q, b) + abs(r)
n, b = map(int, input().split())
# t는 결과의 부호
# 음수를 양수진법으로 변환하는 경우에만 음수
t = 1
# 계산 편의상 음수 진법은 n을 음수로 반전시킨다
# 첫 자리는 이전 자릿수의 자리올림이 없기 때문
# 또한 음수를 양수진법으로 변환하는 경우를 예외처리
if b < 0:
n = -n
elif n < 0:
n = -n
t = -1
print(t * solve(n, b))
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...