봄수의 연구실

문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 풀이 보아하니 Dynamic Programmi..

Programmers 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면..

Programmers 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 ..

Programmers_행렬과 연산 ShiftRow 모든 행이 아래쪽으로 한 칸씩 밀려납니다. 즉, 모든 행에 대해서 i번째 행은 i+1번째 행이 됩니다. (마지막 행은 1번째 행이 됩니다.) ShiftRow의 예 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 ShiftRow를 한 번 시행한 뒤의 행렬입니다. 1번째 행에 있던 [1,2,3]이 2번째 행으로, 2번째 행에 있던 [4,5,6]이 3번째 행으로, 3번째 행에 있던 [7,8,9]가 1번째 행이 된 것을 확인할 수 있습니다. Rotate 행렬의 바깥쪽에 있는 원소들을 시계 방향으로 한 칸 회전시킵니다. 행렬의 바깥쪽에 있는 원소들은 첫 행, 첫 열, 끝 행, 끝 열에 포함되는 원소들입니다. 한 칸 회전시킨다는 것은 이 원소들이 시계 방향으로 한 칸씩 밀..

백트래킹 (Backtracking) 정의 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만을 찾아내는 기법입니다. 해결 과정에서 더 이상 진행이 불가능하다고 판단되면, 이전의 분기점으로 돌아가 다른 가능성을 탐색합니다. 사용 예 문제: N-Queen, 순열, 조합 등 과정 설명 선택: 가능한 후보 중 하나를 선택합니다. 제약 조건 검사: 선택이 문제의 제약 조건에 위배되는지 확인합니다. 목표 확인: 현재 선택이 문제 해결의 목표에 도달했는지 확인합니다. 불가능한 경우 백트래킹: 선택이 불가능하다면 이전 단계로 돌아갑니다. Sudo Code def is_safe(board, row, col): # 해당 위치에 퀸을 놓을 수 있는지 확인하는 함수 def solve_n_queen(board..

너비 우선 탐색 (BFS, Breadth-First Search) BFS는 그래프의 모든 정점을 탐색하는 알고리즘 가장 가까운 정점부터 우선적으로 탐색하는 방식 특징 재귀적으로 동작하지 않는다 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다 (무한 루프의 위험) 방문한 노드들을 차례대로 저장 한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다 Prim 알고리즘, 다익스트라 알고리즘(Dijkstra’s Algorithm) 과정 설명 시작 정점 선택: 탐색을 시작할 정점을 선택합니다. 인접 정점 큐에 추가: 현재 정점에 인접한 모든 정점을 큐에 추가합니다. 큐에서 정점 추출: 큐에서 정점을 하나씩 추출하며 탐색합니다. 방문..

깊이 우선 탐색 (DFS, Depth-First Search) 정의 DFS는 그래프의 모든 정점을 탐색하는 알고리즘 중 하나로, 가장 깊은 부분을 우선적으로 탐색하는 방식입니다. 사용 예 문제: 그래프의 모든 정점 방문, 경로 탐색 등 과정 설명 시작 정점 선택: 탐색을 시작할 정점을 선택합니다. 인접 정점 탐색: 현재 정점에서 갈 수 있는 인접한 정점을 찾습니다. 깊이 우선 탐색: 인접한 정점 중 하나를 선택하여 더 깊게 탐색합니다. 방문 체크: 방문한 정점은 체크하여 중복 방문을 방지합니다. Sudo Code def dfs(graph, v, visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs(graph, i, visited)

Programmers_등산 코스 정하기 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다. 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다. 예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다. 등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 inte..

택배 배달과 수거하기 문제 설명 당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다. 배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n) 트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 ..

문제 설명 고객의 약관 동의를 얻어서 수집된 1~n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니다. 예를 들어, A라는 약관의 유효기간이 12 달이고, 2021년 1월 5일에 수집된 개인정보가 A약관으로 수집되었다면 해당 개인정보는 2022년 1월 4일까지 보관 가능하며 2022년 1월 5일부터 파기해야 할 개인정보입니다. 당신은 오늘 날짜로 파기해야 할 개인정보 번호들을 구하려 합니다. 모든 달은 28일까지 있다고 가정합니다. 다음은 오늘 날짜가 2022.05.19일 ..