손가락놀이터

문제 후기

해당 문제를 보고 닉네임과 uid의 관계를 정립하는 것이 중요하다 생각하여 dictionary를 활용했습니다. 이후는 record의 순서대로 입장과 퇴장을 출력하면 됩니다.

문제 설명

오픈채팅방

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.

신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.

[닉네임]님이 들어왔습니다.

채팅방에서 누군가 나가면 다음 메시지가 출력된다.

[닉네임]님이 나갔습니다.

채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.

• 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.
• 채팅방에서 닉네임을 변경한다.

닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.

예를 들어, 채팅방에 Muzi와 Prodo라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다.

Muzi님이 들어왔습니다.
Prodo님이 들어왔습니다.

채팅방에 있던 사람이 나가면 채팅방에는 다음과 같이 메시지가 남는다.

Muzi님이 들어왔습니다.
Prodo님이 들어왔습니다.
Muzi님이 나갔습니다.

Muzi가 나간후 다시 들어올 때, Prodo 라는 닉네임으로 들어올 경우 기존에 채팅방에 남아있던 Muzi도 Prodo로 다음과 같이 변경된다.

Prodo님이 들어왔습니다.
Prodo님이 들어왔습니다.
Prodo님이 나갔습니다.
Prodo님이 들어왔습니다.

채팅방은 중복 닉네임을 허용하기 때문에, 현재 채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경된다.

Prodo님이 들어왔습니다.
Ryan님이 들어왔습니다.
Prodo님이 나갔습니다.
Prodo님이 들어왔습니다.

채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 record가 매개변수로 주어질 때, 모든 기록이 처리된 후, 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하도록 solution 함수를 완성하라.

제한사항

• record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다.
• 다음은 record에 담긴 문자열에 대한 설명이다.
  • 모든 유저는 [유저 아이디]로 구분한다.
  • [유저 아이디] 사용자가 [닉네임]으로 채팅방에 입장 - Enter [유저 아이디] [닉네임] (ex. Enter uid1234 Muzi)
  • [유저 아이디] 사용자가 채팅방에서 퇴장 - Leave [유저 아이디] (ex. Leave uid1234)
  • [유저 아이디] 사용자가 닉네임을 [닉네임]으로 변경 - Change [유저 아이디] [닉네임] (ex. Change uid1234 Muzi)
  • 첫 단어는 Enter, Leave, Change 중 하나이다.
  • 각 단어는 공백으로 구분되어 있으며, 알파벳 대문자, 소문자, 숫자로만 이루어져있다.
  • 유저 아이디와 닉네임은 알파벳 대문자, 소문자를 구별한다.
  • 유저 아이디와 닉네임의 길이는 1 이상 10 이하이다.
  • 채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못 된 입력은 주어지지 않는다.

입출력 예

입출력 예 설명

입출력 예 #1
문제의 설명과 같다.

def solution(record):

    queue = record.copy()  # record를 queue로 복사
    user = {}       # User uid, 닉네임 저장
    result = []     # 결과값
    chk = []        # 행동과 uid 저장 
    idx = 0         # queue 인텍스 값
    
    # 모든 값 탐색
    while idx < len(queue):
        # 행동, uid, 닉네임을 구분
        value = list(map(str,queue[idx].split()))
        # 입장한 경우
        if value[0] == "Enter":
            # 행동, uid 저장
            chk.append([value[0],value[1]])
            # dict에 uid, 닉네임 저장
            user[value[1]] = value[2]
        # 닉네임 변경한 경우
        elif value[0] == "Change":
            # dict에 닉네임 변경
            user[value[1]] = value[2]
        # 나간 경우
        else:
            # 행동, uid 저장
            chk.append([value[0], value[1]])
        idx += 1
    # 저장한 chk를 통해 차례대로 출력        
    for num in range(len(chk)):
        if chk[num][0] == "Enter":
            result.append(user[chk[num][1]] + "님이 들어왔습니다.")
        else:
            result.append(user[chk[num][1]] + "님이 나갔습니다.")
    return result

문제 후기

해당 문제는 LRU(Least Recently Used) 알고리즘을 참고하여 푸는 방식이다. 

LRU 알고리즘이란 메모리 크기를 가지고 있고 Queue 형태로 캐시 메모리에 들어가는 것이다. 이 때 캐시 메모리 안에 있다면 해당 캐시를 삭제 후 다시 queue에 넣는 방식이다. 자세한 것은 아래의 이미지를 참고한다.

해당 문제를 풀면서 메모리가 갱신되는 것을 잊고 있어서 실수가 발생했다. 다음에도 주의해야할 것 같다.

문제 설명

캐시

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

• 입력된 도시이름 배열을 순서대로 처리할 때, 총 실행시간을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

입출력 예제

from _collections import deque

def solution(cacheSize, cities):
    queue = deque([0] * cacheSize)  # 캐시 생성
    answer = 0     # 정답값
    if cacheSize == 0:  # 캐시가 0이면 전부 chache miss
        return 5 * len(cities)
    for name in cities:     # 캐시 메모리에 돌리기
        name = name.lower() # 전부 소문자로
        if name in queue:   # 만약 도시가 캐시에 있다면
            queue.remove(name)  # 캐시 최신으로 교체
            queue.append(name)
            answer += 1     # cache hit

        else:
            queue.popleft() # 가장 옛날 캐시 삭제
            queue.append(name)  # 캐시에 추가
            answer += 5     # cache miss

    return answer   # 정답 리턴

문제 후기

단순히 a와 b의 숫자를 반으로 줄여가면 된다.

문제를 풀면서 틀렸던 부분은 단순히 두 값의 절대값이 1일 때 끝나도록 했는데 (4, 5)와 같이 대진이 아니더라도 절대값이 1이 발생하는 부분이 있다는 것을 실수했다.

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

제한사항

• N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

입출력 예

입출력 예 설명

입출력 예 #1
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

def solution(n,a,b):
    answer = 1  # 정답값

    while True:     # 리턴할 때 까지 반복
        # 두 값의 차이가 1의 차이가 날때
        # 주의) a와 b가 대진을 해야하는데 2,3 같이 1의 차이가 나도 대결 안하는 경우
        if abs(a - b) == 1 and a // 2 != b // 2:
            return answer   # 정답 리턴
        else:
            if a % 2 == 1:  # 홀수일 때
                a = (a + 1) // 2
            else:
                a = a // 2  # 짝수일 때

            if b % 2 == 1:
                b = (b + 1) // 2    # 홀수일 때
            else:
                b = b // 2      # 짝수일 때
            answer += 1     # 대진횟수

문제 후기

해당 문제는  말한 단어가 이전에 나왔는지 안나왔는지 확인과 이전 단어의 마지막 글자와 현재 단어의 첫번째 글자가 일치하는지 확인하는 것만 생각하면 되는 문제다.

Dictionary를 사용하여 단어가 나왔는지 안나왔는지 해결하였다.

문제 설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

• 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
• 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
• 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
• 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
• (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
• 단어의 길이는 2 이상 50 이하입니다.
• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
• 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

입출력 예

입출력 예 설명

입출력 예 #1
3명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : tank, wheel, mother
• 2번 사람 : kick, land, robot
• 3번 사람 : know, dream, tank

와 같은 순서로 말을 하게 되며, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한 tank와 같으므로 3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다.

입출력 예 #2
5명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : hello, recognize, gather
• 2번 사람 : observe, encourage, refer
• 3번 사람 : effect, ensure, reference
• 4번 사람 : take, establish, estimate
• 5번 사람 : either, hang, executive

와 같은 순서로 말을 하게 되며, 이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. 따라서 [0, 0]을 return하면 됩니다.

입출력 예 #3
2명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : hello, even, now, draw
• 2번 사람 : one, never, world

와 같은 순서로 말을 하게 되며, 1번 사람이 자신의 세 번째 차례에 'r'로 시작하는 단어 대신, n으로 시작하는 now를 말했기 때문에 이때 처음 탈락자가 나오게 됩니다.

def solution(n, words):

    word_dict = {}  # 이전에 나온 단어인지 확인용 dictionary
    idx = 0         # 번호 순서 확인 변수
    count = 1       # 사람이 몇 번째 단어가 틀렸는지 확인 변수
    last_word = words[0][0] # 처음 시작 단어 첫 글자

    while True:

        if idx == len(words):   # 만약 모든 단어를 진행했다면 틀린 사람 없음
            return [0,0]
        if words[idx] not in word_dict and words[idx][0] == last_word:  # 단어가 이전에 안나왔고 앞 단어의 마지막 글자와 일치
            word_dict[words[idx]] = 1   # dictionary에 추가
            last_word = words[idx][-1]  # 마지막 글자 저장
            idx += 1

            if idx % n == 0:    # 만약 n번째 사람이 대답 했다면 단어 + 1
                count += 1
        else:
            if (idx+1) % n:     # 만약 n번째가 아니면 n으로 나눈 나머지 번째 사람
                return [(idx+1) % n, count]
            else:               # n 번째 사람.
                return [n, count]

문제 후기

이전 2020 카카오 여름인턴에서 2번문제로 나왔던 문제입니다. 그 때 당시에도 풀긴 풀었지만 꽤 오랜 시간이 걸렸었는데 다시 풀어보니 이전보다 빨리 풀기는 했습니다. 이전에는 연산자의 경우도 코드로 했지만 경우의 수가 6개만 나와서 전부 입력했습니다.

해당 문제는 수식을 어떻게 하면 잘 구분하는지, 문자열 사용을 잘하면 되는 것 같습니다. 앞에서부터 하는 수식이다보니 Queue를 활용하여 풀었습니다.

문제 설명

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다.
이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다.
해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.
단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.
만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.

예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.

"100-200*300-500+20"

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.
대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• expression은 길이가 3 이상 100 이하인 문자열입니다.
• expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
  • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
• expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
  • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
  • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
• expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
• 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.
• 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

입출력 예

입출력 예에 대한 설명

입출력 예 #1
* > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.
100-200*300-500+20
= 100-(200*300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420
따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420 입니다.

입출력 예 #2
- > * 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.(expression에서 + 연산자는 나타나지 않았으므로, 고려할 필요가 없습니다.)
50*6-3*2
= 50*(6-3)*2
= (50*3)*2
= 150*2
= 300
따라서, 우승 시 받을 수 있는 상금은 300 입니다.

from _collections import deque

def solution(expression):
    # 6개의 연산자 우선순위
    priority = [['+','-','*'],['+','*','-'],['-','+','*'],['-','*','+'],['*','-','+'],['*','+','-']]
    answer = 0      # 리턴하는 결과값
    
    arr = []     # 수식을 저장하는 베열.
    num = ''    # 숫자를 판별.
    
    # 문자열인 수식을 배열에 저장
    for ch in expression:
        if ch.isnumeric():
            num += ch
        else:
            # 문자인 경우 숫자를 배열에 저장하고 연산자도 저장
            arr.append(int(num))
            num = ''
            arr.append(ch)
    # 마지막 숫자 베열에 저장
    arr.append(int(num))

    # 우선순위에 따라서 총 6번 계산.
    for formular in priority:
        queue = deque(arr)  # 배열을 Queue에 삽입.
        
        # 연산자 우선순위로 계산
        for operator in formular:
            # 해당 연산자 계산한 이후 수식.
            calculate = deque([])
            # Queue에 값이 없을때 까지
            while queue:
                chk = queue.popleft()   # Queue에 값을 하나씩 pop.

                if chk == operator:     # 만약 연산자일때 연산자마다 계산
                    if chk == '+':

                        num1 = calculate.pop()  # 연산자 이전 숫자
                        num2 = queue.popleft()  # 연산자 다음 숫자
                        calculate.append(num1+num2) # 연산자 계산
                    elif chk == '-':
                        num1 = calculate.pop()  # 연산자 이전 숫자
                        num2 = queue.popleft()  # 연산자 다음 숫자
                        calculate.append(num1 - num2)   # 연산자 계산
                    else:
                        num1 = calculate.pop()  # 연산자 이전 숫자
                        num2 = queue.popleft()  # 연산자 다음 숫자
                        calculate.append(num1 * num2)   # 연산자 계산
                else:
                    calculate.append(chk)   # 숫자인 경우 저장

            queue = calculate.copy()    # 완료된 수식을 다시 Queue에 저장하여 계산

        result_num = queue.pop()    # 수식 최종값
        answer = max(answer, abs(result_num))    # 수식값의 절대값이 크다면 결과값 수정


    return answer   # 결과값 출력

문제 설명

2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.

제한 조건

• 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
• 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
• 곱할 수 있는 배열만 주어집니다.

입출력 예

def solution(arr1, arr2):
    # 1번째 매트릭스의 row, col
    arr1_y, arr1_x = len(arr1), len(arr1[0])
    # 2번째 매트릭스의 row, col
    arr2_y, arr2_x = len(arr2), len(arr2[0])

    # 결과 매트릭스 생성
    answer = [[0] * arr2_x for _ in range(arr1_y)]

    # 1번째 매트릭스의 row
    for y_1 in range(arr1_y):
        # 2번째 매트릭스의 col
        for x_2 in range(arr2_x):

            # 1번째 매트릭스의 col == 2번째 매트릭스의 row
            for mul in range(arr1_x):

                answer[y_1][x_2] += arr1[y_1][mul] * arr2[mul][x_2]
    # 결과 매트릭스 return
    return answer

문제 후기

처음 피보나치 수라는 것을 보자마자 재귀를 생각해서 풀었습니다.

1차로 재귀만 사용하였을때 시간초과가 발생하여 2차로 재귀 + DP로 이전에 나온 값이 있는 경우 반복하지 않고 바로 사용하게 했습니다. 제출 결과로 다시 시간초과와 런타임에러가 발생했고 최대 입력값인 100,000을 입력해보니 maximum recursion depth exceeded 에러가 발생했습니다.

알고리즘을 다시 생각해보니 단순 O(n)으로 해결가능한 문제였습니다....😢

처음 문제 파악을 할 때 확실히 파악하는 것이 중요할꺼 같습니다. 문제파악을 더 잘해야겠습니다😂😂

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

* n은 1이상, 100000이하인 자연수입니다.

입출력 예

def solution(n):

    chk = 0     # 피보나치 홀수, 짝수 판별
    fibonacci_num1 = 1  # 피보나치 홀수 번째 값(1)
    fibonacci_num2 = 1  # 피보나치 짝수 번째 값(2)

    idx = 3     # 피보나치 3부터 시작
    
    # n 번째 까지 진행
    while idx < n+1:
        if idx % 2 == 1:    # 홀수 경우
            fibonacci_num1 += fibonacci_num2    # F(n) = F(n-1) + F(n-2)
            chk = 1     # 홀수 체크
        else:               # 짝수 경우
            fibonacci_num2 += fibonacci_num1    # F(n) = F(n-1) + F(n-2)
            chk = 0     # 짝수 체크
        idx += 1    # 숫자 증가


    if chk == 1:    # 홀수면 홀수 F(n)값 리턴
        return fibonacci_num1 % 1234567
    else:           # 짝수면 짝수 F(n)값 리턴
        return fibonacci_num2 % 1234567 
        
   
   
   
   # def fibonacci(num, num_dict):
#     if num in num_dict:
#         return num_dict[num], num_dict
#     # elif num < 2:

#     #     return num
#     else:
#         res2, num_dict = fibonacci(num - 2, num_dict)
#         num_dict[num - 2] = res2
#         res1, num_dict = fibonacci(num - 1, num_dict)
#         num_dict[num - 1] = res1
#
#
#         return res1 + res2, num_dict
#
# def solution(n):
#     num_dict = {0:0,1:1}
#     result, _ = fibonacci(n, num_dict)

#     return result % 1234567

문제 설명

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 두번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 첫번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예시

def solution(A,B):
    answer = 0
    
    A = sorted(A)   # 오름차순으로 정렬
    B = list(reversed(sorted(B)))   #  내림차순으로 정렬
    
    # index 별로 곱하여 더하기
    for idx in range(len(A)):
        answer += A[idx] * B[idx]

    return answer