TIL of Algorithm

25314 - 코딩은 체육과목 입니다

문제

오늘은 혜아의 면접 날이다. 면접 준비를 열심히 해서 앞선 질문들을 잘 대답한 혜아는 이제 마지막으로 칠판에 직접 코딩하는 문제를 받았다. 혜아가 받은 문제는 두 수를 더하는 문제였다. C++ 책을 열심히 읽었던 혜아는 간단히 두 수를 더하는 코드를 칠판에 적었다. 코드를 본 면접관은 다음 질문을 했다. “만약, 입출력이 �$N$바이트 크기의 정수라면 프로그램을 어떻게 구현해야 할까요?”

혜아는 책에 있는 정수 자료형과 관련된 내용을 기억해 냈다. 책에는 long int는 4$4$바이트 정수까지 저장할 수 있는 정수 자료형이고 long long int는 8$8$바이트 정수까지 저장할 수 있는 정수 자료형이라고 적혀 있었다. 혜아는 이런 생각이 들었다. “int 앞에 long을 하나씩 더 붙일 때마다 4$4$바이트씩 저장할 수 있는 공간이 늘어나는 걸까? 분명 long long long int는 12$12$바이트, long long long long int는 16$16$바이트까지 저장할 수 있는 정수 자료형일 거야!” 그렇게 혜아는 당황하는 면접관의 얼굴을 뒤로한 채 칠판에 정수 자료형을 써 내려가기 시작했다.

혜아가 N바이트 정수까지 저장할 수 있다고 생각해서 칠판에 쓴 정수 자료형의 이름은 무엇일까?

입력

첫 번째 줄에는 문제의 정수 N이 주어진다(4 <= N <= 1000; N은 4의 배수)

예제 입력 & 예제 출력

# 입력 
4
# 출력 
long int

노트

출력에서 long 과 long, long과 int 사이엔 공백이 하나씩 들어간다.

작성 코드

# https://www.acmicpc.net/problem/25314

# 1차버전
n = int(input())
for _ in range(n//4):
    print("long ", end="")
print("int")

# 2차 개선 버전
print(int(input())//4 * 'long ' + 'int')

후기

주말에나 추가 정리할 예정이지만 파이썬은 정말 신기한 것 같다.
연산자도 그렇고, 무엇보다 파이썬은 확실히 시스템적으로 상당히 복잡한 절차와 과정을 거쳐서 그런가, 변수에 값을 넣냐 않 넣냐 만으로도 4ms 이상 차이나는 것을 볼 수 있었다.
특히나 C나 C++ 의 semantic 한 언어들과 달리, 사라질 값에 가까운 형태의 값 선언도 어쩌면 내부에선 실제로 데이터가 들어오는 것을 이미 객체로 만들어서 받는게 아닌가 라는 생각이 들었다.
실제로 [파이썬 튜터](Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java) 를 통해 구동되는 모습을 봤더니, 위의 형태는 global한 형태의 변수 선언 및 이동 저장의 과정이 있었으나, 하단의 것은 그런 과정 자체가 없었다.

15552 - 빠른 A+B

문제

본격적으로 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를 한 줄에 하나씩 순서대로 출력한다.

예제 입력 & 예제 출력

작성 코드

# https://www.acmicpc.net/problem/15552
import sys

# 1차 고민 버전 
for _ in range(int(input())):
     a, b = map(int, sys.stdin.readline().split())
     print(a + b)

# 2차 고민 개선버전 
for _ in range(int(input())):
    print(sum(map(int, sys.stdin.readline().split())))

# 우수한 작성 사례 
n,*a=map(int,open(0).read().split())
print(' '.join(str(a[i]+a[i+1])for i in range(0,2*n,2)))

후기

오… 이번 문제는 다른 분들의 맞춘 코드들이 하나같이 내공이 느껴지는 코드였다. 거기다 지속적으로 느끼지만 코드에서 출력을 위해 반복문을 극단적으로 죽이려고 노력하는 경우도 있겠구나 라는 생각을 했다.
그걸 출력이 가능한 다른 형태로 바꿔 산술로 계산하는 것은 상당한 효과가 있다는 것을 알 수 있었다.
더불어 람다 함수의 사용 등을 포함하여, 파이썬의 자료구조나 독특한 사용 가능한 것들에 대한 공부가 확실히 해야할 것같다.

11021 - A+B - 7

문제

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10)

출력

각 테스트 케이스마다 “Case #x: “를 출력한 다음, A+B를 출력한다. 테스트 케이스 번호는 1부터 시작한다.

예제 입력 & 예제 출력

# 예제 입력
5
1 1
2 3
3 4
9 8
5 2

# 예제 출력 
Case #1: 2
Case #2: 5
Case #3: 7
Case #4: 17
Case #5: 7

작성코드

# https://www.acmicpc.net/problem/11021
import sys

for i in range(0, int(sys.stdin.readline().rstrip())):
    print("Case #" + str(i + 1) + ": " +
          str(sum(map(int, sys.stdin.readline().split()))))

후기

해당 문제는 살짝 난해했다. 무엇보다 출력시의 주의사항을 확인할 수 있었다.
우선 print 내부에서 ’+’ 연산은 동일한 형일 때 가능하다. 하지만 문자열과 정수형은 동일하지 않았다. 따라서 형변환이 필수이다.

TIL of Algorithm