본문 바로가기

전체 글

 (147)
Baekjoon 30805. 사전 순 최대 공통 부분 순열 / Python 문제 요약두 수열 AAA와 BBB가 주어졌을 때, 이 두 수열의 공통 부분 수열 중 사전 순으로 가장 나중에 오는 수열을 구하는 문제다. 부분 수열이란 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장하는 것을 의미한다. 사전 순으로 나중이라는 것은 첫 번째 수가 큰 쪽을 의미하고, 첫 번째 수가 같다면 두 번째 수로 비교를 이어가는 것을 의미한다.알고리즘 설명알고리즘 개요최대 공통 부분 수열 찾기: 두 수열에서 공통으로 등장하는 가장 큰 값을 찾아 나감.재귀적 접근: 가장 큰 값을 찾으면 그 값을 결과에 추가하고, 그 이후의 부분 수열에 대해 다시 같은 작업을 반복한다.탐색 및 제거: 각 단계마다 가장 큰 값을 찾고, 해당 값을 제거하면서 다음 단계로 넘어감.종료 조건: 어느 한 수열이 빈 리스트가..
Baekjoon 1941. 소문난 칠공주 / Python https://www.acmicpc.net/problem/1941문제 요약5×5의 정사각형 격자에 'S' (이다솜파) 또는 'Y' (임도연파)로 표시된 여학생들이 있다. 이다솜파의 학생 4명 이상을 포함해 7명의 여학생이 가로나 세로로 인접하게 모여 "소문난 칠공주"를 결성할 수 있는 모든 경우의 수를 구하는 문제다.알고리즘 설명알고리즘 개요백트래킹으로 조합 생성: 5×5 격자에서 7명의 여학생을 선택하는 모든 조합을 생성한다.BFS로 인접 확인: 선택된 7명의 여학생이 가로나 세로로 인접해 있는지 BFS로 확인한다.이다솜파 학생 수 확인: 선택된 7명의 여학생 중 이다솜파 학생이 4명 이상인지 확인한다.결과 계산: 위 조건을 모두 만족하는 경우의 수를 계산한다.시간복잡도백트래킹을 통해 25명 중 7명을..
Baekjoon 2638. 치즈 / Python https://www.acmicpc.net/problem/2638문제 요약N×M의 격자판에 치즈가 놓여 있다. 치즈의 각 격자(작은 정사각형 모양)는 4변 중 2변 이상이 공기와 접촉하면 한 시간 만에 녹아 없어지게 된다. 이때 치즈가 모두 녹아 없어지는 데 걸리는 시간을 구하는 문제다.알고리즘 및 코드 설명알고리즘치즈 외부 공기 탐색: BFS를 사용하여 외부 공기를 탐색하고, 외부 공기와 접촉한 치즈를 표시한다.치즈 녹이기: 외부 공기와 2변 이상 접촉한 치즈를 녹인다.반복: 치즈가 모두 녹을 때까지 1~2의 과정을 반복한다.시간 측정: 치즈가 모두 녹을 때까지 걸린 시간을 측정하여 출력한다.시간복잡도BFS 탐색은 O(N×M) 시간 복잡도를 가진다.치즈를 녹이는 과정도 O(N×M)이다.최악의 경우, 치..
Baekjoon 11049. 행렬곱셈순서 / Python https://www.acmicpc.net/problem/11049문제 설명주어진 여러 개의 행렬을 순서대로 곱할 때, 필요한 곱셈 연산의 최소 횟수를 구하는 문제행렬의 곱셈 연산 수는 행렬을 곱하는 순서에 따라 달라지기 때문에, 최적의 곱셈 순서를 찾는 것이 중요하다.알고리즘 및 코드 설명알고리즘 설명DP : dp[i][j] : i부터 j 까지의 행렬을 곱하는 데 필요한 최소 곱셈 연산 수코드 설명DP 테이블 채우기:간격(interval)을 1부터 n−1n-1n−1까지 변화시키며, 각 간격에 대해 start와 end를 설정.start부터 end까지의 최소 연산 수를 찾기 위해 mid를 사용하여 분할 정복.dp[start][mid]와 dp[mid+1][end]의 연산 수와 추가적으로 두 부분 행렬을 곱하..
Baekjoon 1937. 욕심쟁이 판다 / Python https://www.acmicpc.net/problem/1937알고리즘 설명문제 설명주어진 n * n 크기의 대나무 숲에서 판다가 최대로 많은 칸을 이동할 수 있는 경로를 찾는 문제상, 하, 좌, 우 로만 이동할 수 있다.현재 칸에 있던 대나무보다 더 많은 대나무가 있는 칸으로만 갈 수 있다.풀이 설명알고리즘DFS, DP : 각 칸에서 이동 가능한 모든 경로를 탐색하고, 이미 계산된 경로라면 DP를 활용한다.시간 복잡도최악의 경우 O(n ** 2)의 시간 복잡도를 가진다. n from collections import deque as dqimport sys; input = sys.stdin.readlinesys.setrecursionlimit(250000)n = int(input())arr = [lis..
Baekjoon 20303. 할로윈의 양아치 / Python https://www.acmicpc.net/problem/20303알고리즘 설명문제 설명스브러스는 할로윈 밤에 혼자서 돌아다니며 다른 아이들의 사탕을 빼앗기로 결정했다.스브러스는 아이들의 친구 관계를 알고 있으며, 한 아이의 사탕을 빼앗으면 그 아이의 친구들의 사탕도 모두 빼앗는다.스브러스가 최대로 뺏을 수 있는 사탕의 양을 구하는 것이 목표다.단, K명 이상의 아이들이 울면 어른들이 나와서 스브러스를 멈추게 합니다.코드 설명Union-Find: 친구 관계를 통해 연결된 모든 아이들을 하나의 그룹으로 묶는다.그룹 내 사탕과 친구 수 집계: 각 그룹별로 총 사탕의 수와 친구의 수를 계산한다.DP (동적 계획법): 각 그룹을 대상으로 하여 그룹을 선택하거나 선택하지 않는 경우를 고려하여 최대 사탕 수를 계산..
Baekjoon 31885. Yunny's Trip / Python https://www.acmicpc.net/problem/31885알고리즘 설명문제 설명회윤이는 특정 목적지 (Ex, Ey)로 이동해야 한다.이동하는 방법은 두 가지가 있다.인접한 격자판으로 한 칸 이동한다. -> 기력 1 소모아이템을 사용하여 (a, b) 만큼 이동한다. -> 기력 2 소모조건초기 기력 K로 목적지에 도달할 수 있는지 확인한다.도달 가능하다면 최소 기력을 구한다.기력은 0 이상으로 유지해야 한다.코드 설명초기 거리 계산 : 목적지로 아이템 없이 직접 이동하는 경우의 거리를 계산한다.아이템의 좌표와 목적지의 상대 좌표를 활용하여, 코드를 최대한 단축시킨다. : 시간 복잡도를 N으로 나누는 효과를 얻을 수 있다.도달 가능한 경우의 최소 소모 기력을 계산한다.import sys; input ..
Baekjoon 31963. 두 배 / Java, Python https://www.acmicpc.net/problem/31963알고리즘 설명문제 설명문제는 주어진 수열에서 어떤 연속된 두 수 a[i-1]와 a[i]가 있을 때, a[i-1]가 a[i]보다 작지 않도록 하기 위한 최소한의 조작 횟수를 구하는 문제, 조작은 a[i]를 2의 제곱만큼 증가시키는 것입니다.코드 설명비율 계산: 현재 수 arr[i]와 이전 수 arr[i-1]의 비율을 계산. arr[i-1]가 arr[i]보다 크면 arr[i]를 적절히 증가시키는 것이 필요하다. 비율을 구하는 식은 Math.log(arr[i-1] / arr[i]) / Math.log(2). 이를 Math.ceil 함수를 사용해 올림조작 횟수 누적: 각 단계에서 필요한 조작 횟수를 누적합니다. cnt_arr는 각 단계에서의 조작..
Baekjoon 4307. 개미 / Java https://www.acmicpc.net/problem/4307알고리즘 설명문제 설명개미들이 만나면 방향을 바꾸지만, 만났을 경우 서로 지나쳐간다라고 생각해도 논리가 같다.라는 생각을 해내면 굉장히 쉬워지는 문제코드 설명개미의 현재 위치로부터 막대 양 끝으로 가는 시간을 구해서 최소시간, 최대시간을 구한다.import java.io.*;import java.util.StringTokenizer;public class Main { public static int tc; // 테스트 케이스 수 public static int n; // 개미의 수 public static int l; // 막대의 길이 public static int[] arr; // 각 개미의 초기 위치를 저장하는..
Baekjoon 1865. 웜홀 / Python https://www.acmicpc.net/problem/1865알고리즘 설명문제 설명주어진 그래프에 음수 가중치가 있는지를 확인하여 시간 여행이 가능한지(즉, 음수 사이클이 존재하는지) 판단하는 문제코드 설명모든 노드에서 출발하여 음수 사이클이 존재하는지 확인한다.dp 배열을 사용하여 각 노드까지의 최단 거리를 저장하고, 그래프의 모든 간선을 N - 1번 반복하여 최단 거리를 갱신한다.N번째 반복에서도 최단 거리가 갱신되면 음수 사이클이 존재한다고 판단한다.import sysinput = sys.stdin.readlineinf = 1e10 # 벨만-포드 알고리즘을 사용하여 음수 사이클을 탐지하는 함수def sol(start=1): # 각 노드까지의 최단 거리를 저장하는 dp 배열 dp = ..

티스토리툴바