Class 2 (Hashing ~ 부녀회장이 될테야)

solved.ac

• 이번 글에서는 문자열, 간단한 수학 문제들을 비롯하여 간단한 DP 문제까지 해결해보도록 하겠습니다.

 

15829번 : Hashing

15829번: Hashing

• Hash 함수를 구현해보는 문제입니다. Hash 함수란, 간단히 말해 문자열을 특정 정수인 '해시 값'으로 바꿔주는 역할을 수행한다고 생각하시면 되겠습니다.
• 문제에서는 문자열에 영문 소문자만을 포함시킨다고 명시되어 있습니다. 각 문자는 '아스키 코드'라는 정수 값을 가지고 있어 이 값을 이용해 문자열을 정수로 변환할 수가 있습니다.
• 예를 들어 'a'는 아스키 코드 값이 97, 'b'는 98인 것부터 마지막 영문 소문자인 'z'가 122까지로 구성되어 있습니다. 이제 이 값을 가져올 수만 있으면 되는데, 파이썬에서는 'ord()' 함수를 이용하여 쉽게 해결할 수 있습니다.
• 'ord('a')'의 경우 바로 97의 값을 얻어낼 수 있으며 문제에서는 'a'를 1로 처리한다고 했기 때문에 ord('a') - 96의 연산을 각 문자에 적용해주시면 되겠습니다.
• 나머지 부분은 문제를 따라가며 천천히 구현해주시면 됩니다. 아래는 예시 답변 코드입니다.

def compute_hash(string):
    hash_value = 0
    for i, char in enumerate(string):
        num = ord(char) - 96
        hash_value += num * (31 ** i)
    return hash_value % 1234567891

if __name__ == '__main__':
    char_len = int(input())
    string = input()
    print(compute_hash(string))

• 중간에 처음 맛보실 수도(?) 있는 enumerate() 함수가 끼어들어가 있습니다. 이 enumerate() 함수는 입력이 들어오면 인덱스와 해당 요소를 함께 반환해주는 친구입니다.
• 예를 들어, [1, 2, 3, 4, 5]라는 배열이 입력으로 들어가고 for문으로 enumerate([1, 2, 3, 4, 5]) 를 돌리게 되면 (0, 1), (1, 2), ..., (4, 5)와 같이 인덱스와 요소를 한꺼번에 얻을 수 있는 형태로 반환됩니다.
• 위 함수는 유용하게 쓰이는 일이 많으니 기억해두시면 좋겠습니다. 👍🏻

 

1259번 : 팰린드롬수

1259번: 팰린드롬수

• 문제에서도 알 수 있듯이 팰린드롬이란 특정 단어를 뒤에서부터 읽어도 똑같이 읽을 수 있는 단어입니다. (토마토, 기러기, 스위스 등)
• 수에서도 동일하게 적용하여 주어진 수가 팰린드롬수인지를 판단하는 문제입니다.
• 문자열을 사용하여 쉽게 해결할 수도 있겠지만, 저는 몫과 나머지를 활용해 수 자체를 거꾸로 뒤집는 방법을 택하였습니다. 이 뒤집힌 수가 원본 숫자와 동일하다면 'yes'를 아니면 'no'를 출력하도록 구현하였습니다.

def is_palindrome(num):
    original, reversed_num = num, 0
    while num > 0:
        reversed_num = reversed_num * 10 + num % 10
        num //= 10
    return original == reversed_num

if __name__ == '__main__':
    while True:
        num = int(input())
        if num == 0:
            break
        print('yes' if is_palindrome(num) else 'no')

 

1546번 : 평균

1546번: 평균

• 주어진 점수들을 문제에서 제시된 방법으로 변환한 새로운 점수들의 평균을 구하는 간단한 문제입니다.

def compute_new_scores(scores, max_score):
    return [(score / max_score * 100) for score in scores]

def calculate_average(scores):
    return sum(scores) / len(scores)

if __name__ == '__main__':
    N = int(input())
    scores = list(map(int, input().split()))
    
    max_score = max(scores)
    new_scores = compute_new_scores(scores, max_score)
    print(calculate_average(new_scores))

 

2609번 : 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수

• 최대공약수와 최소공배수를 구하는 문제입니다.
• 머리로는 우리가 배웠던 그 기초적인 수학 지식을 이용하여 풀 수 있을 것만 같지만, 사실상 코드로 구현하기에는 어려움이 있을 수 있습니다.
• 먼저 최대공약수는 주로 유클리드 호제법을 사용하여 구할 수 있습니다. 이와 관련해서는 전에 작성한 포스팅을 참고하시면 되겠습니다.

꼭 알아야하는 코딩 테스트 유형: 1) #Math

• 또한 최소공배수도 마찬가지로 두 수 a, b가 주어질 때, a * b // (a, b의 최대공약수) 의 관계가 성립합니다. 따라서 최대공약수만 구해진다면 최소공배수도 덤으로 구할 수 있게 됩니다.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

if __name__ == '__main__':
    a, b = map(int, input().split())
    print(gcd(a, b))
    print(lcm(a, b))

• 그러나 파이썬에서는 math 모듈을 통해 여러 수학적인 함수들을 제공해줍니다. 이 중에서 최대공약수와 최소공배수를 구할 수 있는 gcd()와 lcm() 함수도 존재합니다. 간혹 수학 문제에서 쓰일 때가 있으니 기억해두시면 되겠습니다! 👍🏻

import math

def calculate_gcd_and_lcm(a, b):
    gcd = math.gcd(a, b)
    lcm = math.lcm(a, b)
    return gcd, lcm

if __name__ == '__main__':
  a, b = map(int, input().split())
  gcd, lcm = calculate_gcd_and_lcm(a, b)

  print(gcd)
  print(lcm)

 

2775번 : 부녀회장이 될테야

2775번: 부녀회장이 될테야

• DP의 시작이라고도 볼 수 있는 문제입니다. 'Dynamic Programming'이란 간단히 말해 작은 문제를 해결한 뒤 그 결과를 따로 저장하고, 추후에 이와 관련된 큰 문제가 발생하면 전에 저장했던 결과 값을 불러와서 큰 문제를 해결하는 데 사용하는 방식이라고 보시면 됩니다.
• 이 문제에서는 반복문을 순회하며 해당 층에 살고 있는 거주자들의 수를 하나씩 차근차근 더해주는 방식을 사용할 수 있습니다.
• 앞으로 다양한 DP 문제들을 다룰 예정이기 때문에 아래 포스팅도 참고하시면 도움이 될 것입니다.

꼭 알아야하는 코딩 테스트 유형: 3) #Dynamic_Programming

import sys; input=sys.stdin.readline

def calculate_residents(k, n):
    number_of_residents = [i for i in range(1, n+1)]
    for _ in range(k):
        for j in range(1, n):
            number_of_residents[j] += number_of_residents[j-1]
    return number_of_residents[-1]

if __name__ == '__main__':
    for _ in range(int(input())):
        k = int(input())
        n = int(input())
        print(calculate_residents(k, n))