백준 문제풀이 코드저장소/Platinum (14) 썸네일형 리스트형 Baekjoon 3946. 랜덤 걷기 / Python 3946. 랜덤 걷기난이도 : 플래티넘 3소요 시간 : 1시간날짜 : 2025.01.05언어 : 파이썬알고리즘 유형 : dp설명 보기전에 문제 풀어보러 가기1. 문제 설명동전 던지는 횟수 N, 앞면이 나올 확률(왼쪽으로 갈 확률)L, 뒷면이 나올 확률(오른쪽으로 갈 확률)R 이 주어진다.N번 동전을 던졌을 때, '전체 이동경로의 가장 오른쪽 위치'의 기댓값을 구하기옆면이 나올 수도 있고, 가만히 있는다.2. 해결 방식2차원 dpdp[i][j] = i개의 동전을 던졌을 때, 시작 위치가 j인 경우 가장 오른쪽 위치의 기댓값점화식 설명l * (dp[i-1][j+1] - 1) : 왼쪽으로 이동할 확률 * (그 전 dp의 오른쪽 위치의 기댓값 - 1)(1-l-r) * dp[i-1][j] : 가만히 있을 확률 *.. Baekjoon 6549. 히스토그램에서 가장 큰 정사각형 / Python 6549. 히스토그램에서 가장 큰 정사각난이도 : 플래티넘 5소요 시간 : 35분날짜 : 2025.01.05언어 : 파이썬알고리즘 유형 : 분할정복, 세그머트트리, 스택설명 보기전에 문제 풀어보러 가기1. 문제 설명히스토그램의 내부의 직사각형들 중 가장 넓이가 큰 직사각형을 구하기2. 해결 방식스택 활용히스토그램을 순회하면서 현재 높이보다 낮은 높이를 만날 때마다 직사각형 넓이를 계산한다.0을 만난다면 스택을 초기화한다.시간복잡도 : O(n)세그먼트트리각 구간의 최소 높이를 세그먼트 트리로 저장한다.구간의 최소높이 * 구간의 크기 = 넓이전체 시간복잡도: O(nlongn)분할정복(사용하지 않았지만, 가능한 방법)(히스토그램에서 가장 낮은 높이를 기준으로 좌우로 분할)을 반복하는 방식시간 복잡도 : O(n.. Baekjoon 32034. 동전 쌍 뒤집기 / Python 32034. 동전 쌍 뒤집기난이도 : 플래티넘 5소요 시간 : 25분날짜 : 2025.01.02언어 : 파이썬알고리즘 유형 : 스택, 그리디설명 보기전에 문제 풀어보러 가기1. 문제 설명N개의 동전이 일렬로 놓여있다.조작을 원하는대로 할 수 있다.서로 이웃하고, 같은 면인, 두 개의 동전을 둘 다 뒤집기모든 동전이 앞면이 보이게 할 수 있는가? 가능하다면 최소 조작횟수를 구하라.2. 해결 방식자료구조 : 스택을 활용한다.먼저 뒷면의 위치를 저장하고 개수를 센다.뒷면의 개수가 2로 나누어지지 않으면 불가능, 0이면 답이 0뒷면인 동전들을 돌면서 스택을 활용한다.스택이 비어있다면 스택에 넣기스택의 마지막 요소와 현재 요소의 인덱스 차이가 짝수라면, 가운데의 앞면을 다 뒤집고 다시 뒷면으로 다 뒤집으면 모두 .. Baekjoon 1019. 책 페이지 / Python 1019. 책 페이지난이도 : 플래티넘 5소요 시간 : 20분날짜 : 2024.12.31언어 : 파이썬알고리즘 유형 : 구현, 수학설명 보기전에 문제 풀어보러 가기1. 문제 설명1부터 n까지 [0, 1 ,2, ,,, 9]가 각각 몇 번 나오는지 구하기1 2. 해결 방식자리수 별로 반복하기. (최대 9번)factor = 1 ($10^0$)부터 시작해서 10씩 곱해가며 반복한다.현재 자리를 기준으로, 현재자리 숫자와 더 높은 자리 숫자, 더 낮은 자리 숫자로 구분한다.0부터 9까지 확인하여 결과값에 더해준다.현재자리수보다 작은 수 : (높은자리 숫자 + 1) * factor를 더 해준다.현재자리 수 : 높은자리 숫자 * factor + 낮은자리 숫자 + 1을 더 해준다.현재자리 수보다 큰 수 : 높은자리 숫.. Baekjoon 16566. 카드 게임 / Python 알고리즘 설명입력 처리:N, M, K는 각각 카드의 총 개수, 빨간색 카드의 수, 카드 게임의 횟수를 나타냅니다.pushed_h20는 철수가 선택한 M개의 빨간색 카드의 번호를 오름차순으로 정렬한 리스트입니다.fe_h20는 철수가 게임에서 낼 카드의 번호를 나타내는 리스트입니다.Union-Find 자료구조 초기화:arr 리스트는 각 카드의 부모 노드를 저장합니다. 초기 상태에서 모든 카드의 부모는 자기 자신입니다.Find 함수:주어진 카드의 최종 부모를 찾는 함수입니다. 경로 압축을 통해 효율성을 높입니다.Sol 함수:카드의 부모를 통합하는 함수입니다. 이 함수는 find 함수에서 얻은 부모 노드를 통해 카드의 그룹을 연결합니다.이진 탐색:bisect_right를 사용하여 fe_h20의 각 카드에 대해,.. Baekjoon 18122. 색깔 하노이 탑 / Python print((2**(int(input())+2)-5)%(10**9+7))https://www.acmicpc.net/problem/18122사실상 수학 문제이다.하노이 탑 기본 원리하노이 탑은 N개의 원판을 시작 기둥에서 목표 기둥으로 이동하는 문제입니다. 한 번에 하나의 원판만 이동할 수 있으며, 큰 원판이 작은 원판 위에 놓일 수 없습니다. 기본 하노이 탑 문제에서 N개의 원판을 이동하는 데 필요한 최소 이동 횟수는 다음과 같습니다:T(N) = 2^N - 1이 공식은 재귀적으로 문제를 해결하는 방식에서 유도된 것입니다.두 개의 색깔이 있는 하노이 탑문제에서는 원판이 두 색 (빨간색과 검은색) 이고, 각 크기별로 빨간색 원판과 검은색 원판이 번갈아 놓여 있습니다.하노이 탑 게임의 목표는 모든 원판을 두 .. Baekjoon 13977. 이항 계수와 쿼리 / Python 설명이 코드는 이항 계수 (nr)\binom{n}{r}(rn)를 효율적으로 계산하기 위한 방법을 사용하고 있습니다.팩토리얼 계산은 사전에 미리 처리하여 빠르게 조회할 수 있도록 합니다.역수는 페르마의 소정리(Fermat's Little Theorem)를 이용하여 ap−2mod pa^{p-2} \mod pap−2modp로 계산합니다.시간 복잡도:팩토리얼 계산: O(n)O(n)O(n)거듭제곱 계산: O(logn)O(\log n)O(logn) (재귀 호출 방식)이 코드의 주요 시간 복잡도는 입력 크기에 비례하여 매우 효율적입니다.import sys# 1부터 4000000까지의 팩토리얼 값을 계산하여 저장하는 리스트factorial = [1] * 4000001for i in range(2, 4000001).. Baekjoon 2568. 전깃줄 - 2 / Python https://www.acmicpc.net/problem/2568문제 설명주어진 두 전봇대 사이에 연결된 전깃줄이 교차하지 않도록 하기 위해 최소 개수의 전깃줄을 제거해야 합니다. 각 전깃줄의 연결 정보를 바탕으로, 전깃줄이 교차하지 않는 최장 증가 부분 수열(LIS)을 찾아야 합니다. 이 문제는 LIS를 활용하여 해결할 수 있습니다.알고리즘 설명입력 처리 및 정렬:전깃줄의 정보를 입력받아 정렬합니다.두 전봇대 A와 B의 연결 위치 정보를 입력받아 전봇대 A의 위치를 기준으로 정렬합니다. 이는 전봇대 B의 위치에서 LIS를 찾기 위함입니다.LIS를 이용한 전깃줄 제거:정렬된 전깃줄 정보를 바탕으로 전봇대 B의 위치 값들에 대해 LIS를 구합니다.LIS의 길이를 통해 남아있는 전깃줄의 개수를 파악합니다.전.. Baekjoon 14003. 가장 긴 증가하는 부분 수열 5 / Python https://www.acmicpc.net/problem/14003알고리즘 설명이진 탐색을 활용한 LIS 찾기:LIS를 효율적으로 찾기 위해 이진 탐색을 사용합니다.LIS 배열 Lis를 유지하며, 새로운 원소가 들어올 때 적절한 위치에 삽입합니다.Lis 배열은 항상 정렬된 상태로 유지됩니다.LIS 길이 저장:각 원소에 대해 LIS 배열에 추가할 때 그 위치와 원소를 기록하는 dp 배열을 유지합니다.이는 나중에 실제 LIS 수열을 복원하는 데 사용됩니다.이진 탐색 구현:binary(goal) 함수는 goal 값을 LIS 배열에서 찾고, 적절한 위치를 반환합니다.LIS 복원:dp 배열을 역순으로 탐색하여 실제 LIS 수열을 복원합니다.LIS 길이에 해당하는 값들을 뒤에서부터 찾습니다.n = int(input.. Baekjoon 2887. 행성 터널 / Python https://www.acmicpc.net/problem/2887문제 설명2040년, 이민혁은 우주에 자신만의 왕국을 만들었습니다. 왕국은 N개의 행성으로 이루어져 있으며, 이 행성들을 터널로 연결하여 효율적으로 지배하려고 합니다. 각 행성은 3차원 좌표계의 한 점으로 생각할 수 있고, 두 행성 A와 B를 연결하는 터널의 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)로 계산됩니다. 민혁이는 모든 행성을 최소 비용으로 연결하려고 합니다.이 문제는 최소 신장 트리(MST)를 구하는 문제로, 크루스칼 알고리즘을 활용하여 해결할 수 있습니다.알고리즘 설명Union-Find (Disjoint Set):union_find(x): x가 속한 집합의 대표자, 부모노드를 찾는다.union_set(x, y.. 이전 1 2 다음