[TIL][Krafton Jungle] 1주차 - (5) : 알고리즘 공부 마지막

내일이면 2주차가 시작되서 오늘 안에 알고리즘 문제를 전부 다 풀어내야 한다.

 

---

BaekJun - #1629 solving (분할 정복 : 중)

a를 b만큼 거듭제곱 한 뒤 c로 나눈 나머지를 출력하는 문제이다.

b가 10^8값을 넘기 때문에 for문으로 b만큼 곱하여 풀지 말라는 의도이다.

 

아래 코드로 해결했다.

from collections import deque
import sys
import heapq

a,b,c = map(int,sys.stdin.readline().strip().split())



def div_mup(a,b):
    if b == 1:
        return a%c
    elif b%2 == 1:
        return div_mup(a, b//2)**2*a%c
    else:
        return div_mup(a, b//2)**2%c
result = div_mup(a,b)


print(result)

 

처음엔 시간초과가 발생해서 왜 그런지 고민하다가

재귀 return 줄의 함수호출을 두번이 아니라 1번한 뒤 제곱하는 방식을 사용했다.

 

각 재귀 시 호출 되는 함수의 갯수마다 시간 소요가 크기 때문에 불필요한 재귀 함수 호출을 줄여 해결한 케이스이다.

 

---

 

Baekjun - #10830 solving (분할 정복 : 상)

행렬의 곱을 구하는 알고리즘을 만드는데도 고생 좀 했다. (머리 터지는 줄)

행렬의 곱을 출력해주는 함수를 만들고 인자로 함수 두개를 받도록 만들어 봤다.

 

그 이후에 분할 정복 방법을 도저히 모르겠어서 ChatGPT에게 아이디어를 제시받았는데,

위의 문제와 비슷하게 접근하도록 했다.

 

위의 문제보다 어려웠던건 함수 한개로 return을 바로 해주면 되서 직관적이었지만,

매개 함수인 연산함수를 사용한 재귀함수여서 조금 어려웠다.

 

그리고 마지막으로 연산을 하지 않더라도 1000을 나눈 나머지를 출력해야 하므로 1일때도 나머지 연산을 실행해줬다.

from collections import deque
import sys
import heapq

n,b = map(int,sys.stdin.readline().strip().split())

matrix = []
for i in range(n):
    temp = list(map(int,sys.stdin.readline().split()))
    matrix.append(temp)

def matrix_solve(matrixA, matrixB):
    global n
    result = [[0 for _ in range(n)]for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += matrixA[i][k]*matrixB[k][j]
            result[i][j] = result[i][j]%1000

    return result

def problem_solve(b):
    global n
    if b == 1:
        for i in range(n):
            for j in range(n):
                matrix[i][j] = matrix[i][j]%1000
        return matrix
    elif b%2 == 0:
        half = problem_solve(b//2)
        return matrix_solve(half,half)
    else:
        half = problem_solve(b//2)
        temp = matrix_solve(half,half)
        return matrix_solve(temp,matrix)



list = problem_solve(b)
for i in range(n):
    print(' '.join(map(str,list[i])))

---

Python 문법들

절댓값  출력 메소드

abs(정수)

---

리스트의 얕은 복사 / 깊은 복사 개념

리스트를 다른 자료구조에 대입하는 형식으로 값을 넣게 되면

대입했던 리스트의 값이 변경될 때, 자료구조 안의 값도 같이 변경되는 원하지 않은 결과가 초래될 수 있다.

 

따라서 얕은 복사와 깊은 복사의 개념을 알아야한다.

 

얕은 복사는 슬라이싱, 일반 대입과 같은 복사 즉, 리스트의 주소를 참조하는 형식의 자료 복사를 말하고,

이 경우 참조된 주소의 리스트가 변경되면 같이 값이 변경된다.

 

깊은 복사는 아예 쌩 상관없는 새로운 복사본을 생성하는 것인데,

copy.deepcopy(list)를 이용하면 된다.

 

---

리스트에 문자 낱개로 입력받기  --->    .split() 제거 !

평소에 코딩할 때 리스트에 입력받을 때는

nums = list(map(int,sys.stdin.readline().split())

이런 방식으로 입력받았었다.

 

근데 문자를 각 개별로 리스트에 한 인덱스씩 넣고 싶을때는 어떻게 하는지 몰라서 찾아봤는데

words = list(map(str,sys.stdin.readline().strip())

을 사용하는 것이다.

 

그럼 split()는 뭐하는놈인가?

 

split()은 앞의 문자열 또는 숫자 데이터를 공백 기준으로 나눠주는 역할을 한다.

따라서 문자를 char단위로 나눌때는 .split()을 사용하면 안된다.