빛의 경로 사이클 문제설명 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다. 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다. 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다. 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다. 당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다 제한사항 ..

교점에 별 만들기 문제 설명 Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다. 직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요. 제한사항 ine의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다. line의 가로(열) 길이는 3입니다. line의 각 원소는 [A, B, C] 형태입니다. A, B, C는 -100,000 이상 100,000 이하인 정수입니다. 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다. A = 0이면서 B = 0인 경우는 주어지지 않습니다. 정답은 1,000 * 1,0..

점프와 순간 이동 문제 설명 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요. 제한사항 숫자 N: 1 이상 10억 이하의 자연수 숫자 K: 1 이상의 자연수 풀이 처음에는 bottom-up dp를 생각했다. 만약에 i가 2로 나눠떨어지면 i//2 와 i-1 중에 작은 거를 선택해서 + 1 홀수면 i -1 +1 그런데 입력값이 10억이므로 O(n)으로 풀면 시간 초과가 날 것 같았고 O(logn)으로 풀어야했다. 그래서 이진 탐색인가 싶어서 혼란스러웠다. 결론적으로 top-down 방식으로 접근하면 O(logN)으로 해결할 수 있었다. N에서 2로 나눠떨어지는 곳은 순간이동으로 갈 수 있다. 나눠떨어지지 ..

삼각 달팽이 문제 설명 정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 1,000 이하입니다. 풀이 숫자가 채워지는 방향을 보면 아래, 오른쪽, 왼쪽대각선으로 반복되는 것을 알 수 있다. 채워지는 숫자의 개수는 n, n-1, n-2, n-3 ,... 으로 1일때까지 줄어든다. n*n 2차원 배열을 만들어서 방향을 아래, 오른쪽, 왼쪽 대각선으로 바꿔가면서 채워준다. 현재 시점의 방향을 나타내는 i로 for문을 돌리면서 i부터 n까지로 이중 for문을 돌려준다. 채워..

n^2 배열 자르기 문제 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n 에 대해서, 다음 과정을 반복합니다. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다. 정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요. 제한사..

가장 큰 정사각형 찾기 문제 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.) 제한사항 표(board)는 2차원 배열로 주어집니다. 표(board)의 행(row)의 크기 : 1,000 이하의 자연수 표(board)의 열(column)의 크기 : 1,000 이하의 자연수 표(board)의 값은 1또는 0으로만 이루어져 있습니다. 풀이 처음에는 무지성으로 순회하는 방식을 생각했고 틀렸다. 알고보니 DP를 이용해서 풀어야하는 문제였다. 좌, 상, 좌측 대각선의 값 중 최소 값을 찾는다 1을 더..

행렬의 곱셈 문제 2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요. 제한사항 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다. 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다. 곱할 수 있는 배열만 주어집니다. 풀이 arr2의 행, 열을 바꿔서 계산한다 def solution(arr1, arr2): answer = [] arr2 = [list(i) for i in zip(*arr2)] for arr in arr1: row = [] for col in arr2: tmp = sum([a * b for a, b in zip(arr, col)]) row.append(tmp) answer.a..

2개 이하로 다른 비트 문제 양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다. x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수 예를 들어, f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다. 수비트다른 비트의 개수 2 000...0010 3 000...0011 1 f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다. 수비트다른 비트의 개수 7 000...0111 8 000...1000 4 9 000...1001 3 10 000...1010 3 11 000...1011 2 정수들이 담긴 배열 numbers가 ..