전체 글

행렬의 곱셈

# 두 행렬 A,B를 곱해서 결과를 return한다 # input format은 [[1,2,3]],[[1],[2],[3]] 와 같이 곱할 두 행렬을 넣어주면 된다. # 만약 곱셈이 불가능한 경우 assertion에 걸린다. def multiple_matrix(A,B): # find dimension (row -> m, column -> n) m_A = len(A) n_A = len(A[0]) m_B = len(B) n_B = len(B[0]) assert(n_A == m_B) # return matrix return_matrix = [[] for _ in range(m_A)] tmp = list(zip(*B)) for i in range(m_A): for j in range(n_B): return_mat..

N*N 행렬의 제곱

# N*N행렬의 제곱을 구하는 함수 # matrix 에는 [[1,0],[0,1]] 과 같이 행렬이 N*N의 format으로 들어오면 된다. # return 또한 input format 과 같이 return된다 def square(matrix): N = len(matrix) return_matrix = [[] for _ in range(N)] tmp = list(zip(*matrix)) for i in range(N): for j in range(N): return_matrix[i].append(sum(map(lambda x : x[0] * x[1],zip(matrix[i], tmp[j])))) return return_matrix ''' # testcase print(square([[1,2,3],[1,2..

[백준] N-Queen

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백 트래킹을 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, N이 주어질 때, N*N의 체스판에 N개의 Queen을 배열하는 가짓수를 return해야 합니다. 사실 이전에 프로그래머스를 통해 해결한 적이 있는 문제입니다. https://life318.tistory.com/5 [프로그래머스] N-Queen https://programmers.co.kr/learn/courses/30/lessons/12952 ..

[백준] 스티커

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 위 그림처럼 스티커와 점수가 있습니다. 이때, 한 스티커를 떼어내면 그 스티커의 바로 이웃한 스티커들은 사용할 수 없다고 할 때, 스티커를 최대한 높은 점수로 떼어낼 때의 점수를 구해야 합니다. 이 문제는 다이나믹프로그래밍을 이용해야 합니다. 우선 스티커를 떼어내는 경우들을 생각해보면, 항상 지그재그 모양인 것..

[백준] 이진 검색 트리

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리 자료구조를 이용하고, dfs 또는 재귀를 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 이진 검색트리를 preorder traversal한 결과가 주어질 때, 이 이진 검색트리를 postorder traversal한 결과를 return 해야 합니다. 사실 이 문제는 이전에 포스팅 했던 https://life318.tistory.com/80 [백준] 트리의 순회 https..

[백준] 치즈

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net bfs를 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 치즈가 펼쳐져 있는 모눈종이가 주어지는데, 가장 바깥쪽 공기와 두면 이상 접촉해 있는 치즈는 한시간 만에 녹아 없어집니다. 이 때, 모든 치즈가 사라지는데 까지 걸리는 시간을 return 해야 합니다. (단, 치즈 내부에 있는 공기와 접촉한 것은 면 수에 포함하지 않습니다) 간단한 예시로 문제를 더 추가설명 해보면, 다음..

하이퍼버닝 캐릭터 결정!

하이퍼 버닝 캐릭터로 제로를 골랐다! 250 몸제로? 가 될지 더 애정을 가지고 키울지는 지켜보아야 할 듯 싶다. 4카루타 5아케인 세트로 템셋했다. 무기는 제로는 유니크까지 직접 띄울 수 있는데 요롷게 공 3줄 뽑혀서 사냥은 꽤나 수월하다. 그리고 흙 아케인 템셋 하다가 장갑 추옵이 은근 잘나왔는데 강화 하다가 12성에서 17성까지 스트레이트로 가서 장갑은 꽤나 좋은 것 같다.

[백준] 별 찍기 - 11

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 재귀를 이용하는 문제입니다. 우선 문제부터 요약하면, 첫쨰줄부터 N번째 줄까지 별을 출력해야 하는 문제입니다. N은 항상 3×2^k의 형태로 주어지며, 간단한 예시로는 k=0 -> N=3 k=1 -> N=6 k=2 -> N=12 다음과 같이 규칙성이 있게 출력이 되어야 합니다. 문제에 대한 이해 자체는 쉽습니다. 구현은 어떻게 해야할까요? 위의 표 안의 상황에서 k=0에서 k=1로 변하는 상황을 통해 이후에도 같은 과정을 반복해서 더 큰 별들을 만들..