백준 문제풀이 코드저장소 (99) 썸네일형 리스트형 Baekjoon 14500. 테트로미노 / Python https://www.acmicpc.net/problem/14500문제 설명n * m 크기의 종이에 테트로미노 하나를 놓아 테트로미노가 놓인 칸들의 수들의 합을 최대로 만들어야 한다.회전, 대칭이 가능하다.코드 설명 DFS 함수 구현:dfs 함수는 재귀적으로 테트로미노의 각 칸을 탐색한다.현재까지의 합 sums와 탐색한 칸의 수 cnt를 추적한다.가지치기를 통해 가능성이 없는 경로는 미리 차단한다.상하좌우로 이동하면서 테트로미노의 모양을 형성한다.ㅗ 모양의 테트로미노를 만들기 위해 두 번째 칸에서 다시 시작하는 경우도 고려한다.최대 합 계산:모든 칸을 시작점으로 하여 DFS를 수행하고, 최댓값을 갱신한다.최종적으로 최대 합을 출력한다.시간복잡도 : O(N * M * 256) import sysinput.. Baekjoon 2503. 숫자 야구 / Python, Java https://www.acmicpc.net/problem/2503알고리즘 설명문제 설명숫자 야구 게임세 자리 숫자를 맞춥니다.말한 세 자리의 숫자 중에 위치와 숫자가 모두 일치하는 경우엔 스트라이크,숫자는 정답숫자 안에 있으나, 위치가 다르다면 볼이 됩니다.코드 설명102 부터 987까지 모든 가능한 세자리 숫자를 생성한다.스트라이크와 볼의 입력에 따라서 숫자 후보를 제거하는 방식1. 자바코드import java.io.*;import java.util.*;import java.text.*;public class Main { public static ArrayList arr = new ArrayList(); public static ArrayList noAns = new ArrayList(); .. Baekjoon 11729. 하노이 탑 이동 순서 / Python https://www.acmicpc.net/problem/11729알고리즘 설명문제 설명이 문제는 유명한 하노이의 탑(Tower of Hanoi) 문제입니다.세 개의 장대와 여러 개의 원판을 사용하여 특정 규칙을 따라 첫 번째 장대에 있는 원판을 세 번째 장대로 옮기는 문제입니다.각 원판은 크기가 다르고, 큰 원판은 작은 원판 아래에만 놓일 수 있습니다.한 번에 하나의 원판만 이동할 수 있으며, 더 큰 원판은 작은 원판 위에 올려 놓을 수 없습니다.하노이 탑의 이동 횟수는 2 ^ n - 1 로 잘 알려져 있습니다.이 문제는 그 이동 횟수와 이동 순서를 구하는 문제입니다.풀이를 3번 했는데,앞선 두번의 풀이를 하고나면 좋은 방법이 떠올라서 한번씩 더 풀었습니다.코드 설명 1from copy import d.. Baekjoon 1202. 보석 도둑 / Python https://www.acmicpc.net/problem/1202문제요약상덕이는 보석을 훔치려 한다. 각 보석은 무게와 가격이 있으며, 상덕이는 각 가방에 최대 한 개의 보석만 넣을 수 있다. 주어진 가방의 최대 무게를 초과하지 않으면서 보석의 가격 합이 최대가 되도록 해야 한다.알고리즘 설명보석을 무게 기준으로 오름차순 정렬한다.가방을 무게 기준으로 오름차순 정렬한다.각 가방에 대해, 해당 가방에 담을 수 있는 모든 보석을 선택해 힙에 넣는다.힙에서 가장 비싼 보석을 선택해 결과에 더한다.시간복잡도보석 정렬: O(NlogN)가방 정렬: O(KlogK)각 가방에 대해 보석을 힙에 넣는 작업: 최악의 경우 모든 보석을 힙에 넣는 경우 O(NlogN)힙에서 가장 비싼 보석을 꺼내는 작업: 최악의 경우 .. 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 (동적 계획법): 각 그룹을 대상으로 하여 그룹을 선택하거나 선택하지 않는 경우를 고려하여 최대 사탕 수를 계산.. 이전 1 2 3 4 5 6 7 8 ··· 10 다음
