📌 프로그래머스 [리코쳇 로봇]🔗 문제 링크문제 설명 📄2차원 보드에서 R(로봇) → G(목표 지점)까지의 최소 이동 횟수를 구하는 문제.로봇은 상하좌우로 움직일 수 있지만, 한 번 움직이면 벽 또는 D(장애물)에 부딪힐 때까지 미끄러진다.최소 이동 횟수를 반환하고, 도달할 수 없는 경우 -1을 반환해야 한다. 문제 접근 방식 💡BFS(너비 우선 탐색) 를 사용하여 최단 경로 탐색.R의 시작 위치를 찾고, 큐에 (좌표, 이동 횟수) 를 넣어 탐색 시작.4방향 이동 후 벽이나 장애물에서 멈춘 지점을 새로운 탐색 지점으로 추가.방문한 위치를 visit 집합으로 저장하여 중복 탐색 방지.목표 지점 G에 도달하면 이동 횟수를 반환, 끝까지 도달하지 못하면 -1을 반환.Solution 💻from coll..
알고리즘
📌 프로그래머스 [행렬 테두리 회전하기]🔗 문제 링크문제 설명 📄rows × columns 크기의 행렬이 주어지며, 일부 영역의 테두리를 시계방향으로 회전시키는 연산을 수행해야 한다.각 회전 후, 회전된 값들 중 최솟값을 반환하는 문제.문제 접근 방식 💡2차원 배열을 생성하여 초기 행렬을 구성.주어진 queries를 순회하며 해당 범위의 테두리를 회전.회전 과정:상, 우, 하, 좌 순서로 테두리를 이동.이동 중 만난 숫자들의 최솟값을 추출.최솟값을 answer 리스트에 추가 후 반환.Solution 💻def solution(rows, columns, queries): answer = [] arr = [[i + (columns * j) for i in range(1, columns + ..
📌 프로그래머스 [수식 최대화]🔗 문제 링크문제 설명 📄주어진 수식에서 연산자의 우선순위를 조정하여 최댓값을 구하는 문제.가능한 연산자는 +, -, *이며, 이들의 우선순위를 자유롭게 설정할 수 있음.연산자의 우선순위에 따라 계산을 수행한 후, 최댓값을 반환해야 함.문제 접근 방식 💡토큰화: 정규 표현식을 활용하여 숫자와 연산자를 분리.우선순위 조합 생성: permutations을 이용하여 연산자 우선순위 경우의 수 생성.계산 수행:현재 우선순위에 따라 반복적으로 연산을 수행.deque를 활용하여 좌에서 우로 연산을 적용하며 피연산자를 갱신.최댓값 갱신: 모든 경우의 수를 수행한 후, 절댓값이 가장 큰 결과 반환.Solution 💻import refrom itertools import permu..
📌 백준 [11052]: 카드 구매하기🔗 문제 링크문제 설명 📄카드 팩의 개수 n이 주어지고, 각 팩의 가격이 주어진다.n개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 최대 구매 비용을 계산.dp[i]를 i개의 카드를 구매할 때의 최대 비용으로 정의.점화식:dp[i] = max(dp[i], dp[i-j] + cards[j])여기서 j는 선택한 카드 팩의 개수를 의미.초기값:dp[0] = 0 (카드를 구매하지 않은 경우).Solution 💻n = int(input())cards = [0] + list(map(int, input().split()))dp = [0] * (n + 1)for i in range(1, n + 1): ..
📌 백준 [1309]: 동물원🔗 문제 링크문제 설명 📄가로의 길이가 2이고 세로의 길이가 N인 우리에 사자를 배치하려 한다.사자는 가로로 붙어있는 두 칸에 함께 있을 수 없다.우리에 사자를 배치하는 방법의 수를 9901로 나눈 나머지를 구하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 사자를 배치하는 경우의 수를 계산.세 가지 경우를 고려:사자를 왼쪽 칸에 배치 (b)사자를 오른쪽 칸에 배치 (c)사자를 배치하지 않음 (a)점화식:a(n) = a(n-1) + b(n-1) + c(n-1) (배치하지 않는 경우)b(n) = a(n-1) + c(n-1) (왼쪽에 배치)c(n) = a(n-1) + b(n-1) (오른쪽에 배치)최종 답은 a + b + cSolution 💻n = int(inpu..
📌 백준 [1890]: 점프🔗 문제 링크문제 설명 📄N×N 크기의 게임판이 주어진다. 각 칸에는 해당 칸에서 이동할 수 있는 거리가 적혀 있다.오른쪽 또는 아래쪽으로만 이동 가능하며, 도착점 (N-1, N-1)에 도달할 수 있는 경로의 개수를 구하시오.시작점은 (0,0)이며, 도착점의 값은 항상 0이다.문제 접근 방식 💡재귀 + 메모이제이션을 사용하여 도착점까지의 경로 개수를 계산.dp[x][y]를 (x, y)에서 도착점까지 도달할 수 있는 경로의 수로 정의.종료 조건:(x, y)가 도착점이면 1 반환.arr[x][y] == 0이면 이동 불가하므로 0 반환.점화식:오른쪽과 아래쪽 이동을 고려해 dp[x][y] = count_paths(x + step, y) + count_paths(x, y + s..
📌 백준 [11053]: 가장 긴 증가하는 부분 수열🔗 문제 링크문제 설명 📄수열 A가 주어졌을 때, 그 수열의 부분 수열 중에서 가장 긴 증가하는 부분 수열의 길이를 구하시오.예를 들어, A = [10, 20, 10, 30, 20, 50]일 때 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]로 길이는 4이다.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 각 원소를 기준으로 증가하는 부분 수열의 길이를 계산.dp[i]를 arr[i]를 끝으로 하는 가장 긴 증가하는 부분 수열의 길이로 정의.점화식:dp[i] = max(dp[j] + 1) (단, j 초기값:dp[i] = 1 (최소한 자기 자신 하나로 구성된 수열의 길이는 1).Solution 💻n = int(input())arr ..
📌 백준 [10844]: 쉬운 계단 수🔗 문제 링크문제 설명 📄길이가 N인 계단 수의 개수를 구하시오.계단 수는 다음 조건을 만족하는 숫자이다:숫자의 각 자릿수가 인접한 자릿수보다 1만큼 차이가 남.0으로 시작하는 숫자는 계단 수가 아님.결과를 1,000,000,000으로 나눈 나머지를 출력하시오.문제 접근 방식 💡동적 프로그래밍(DP)을 사용하여 길이가 N인 계단 수를 계산.dp[i][j]를 길이가 i이고 마지막 자릿수가 j인 계단 수의 개수로 정의.점화식:dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]경계 조건:j=0이면, dp[i][j] = dp[i-1][1]j=9이면, dp[i][j] = dp[i-1][8]초기값:dp[1][j] = 1 (단, j ≠ 0).Solutio..
