백준 문제풀이 코드저장소 (99) 썸네일형 리스트형 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.. Baekjoon 14517. 팰린드롬 개수 구하기 (Large) / Python https://www.acmicpc.net/problem/14517알고리즘 설명DP 배열 채우기:길이 2 이상인 부분 문자열에 대해 DP 배열을 채운다.dp[j][j + i]는 dp[j][j + i - 1]와 dp[j + 1][j + i]의 합에서 dp[j + 1][j + i - 1]을 뺀 값만약 s[j] == s[j + i]이면, dp[j][j + i]에 dp[j + 1][j + i - 1] + 1을 더한다결과 출력:dp[0][n-1] 값 = 전체 문자열에서 팰린드롬 부분수열의 개수s = input()# 문자열 길이n = len(s)# DP dp = [[0] * n for _ in range(n)]# 결과를 10007로 나눌 것이므로 이를 상수로 설정div = 10007# 길이가 1인 모든 부분 문자열.. Baekjoon 5719. 거의 최단 경로 / Python https://www.acmicpc.net/problem/5719문제 정리길의 최단 경로를 제외한 경로들 중의 최단 경로를 찾는다.문제 풀이 방식최단거리를 찾고 -> 최단 경로를 제거하고 -> 최단 경로를 찾는다.라고 하면 간단해 보이지만 생각보다 시간초과가 많이났던 코드다익스트라 알고리즘을 두 번 사용한다.import sysfrom heapq import heappop, heappushfrom collections import deque as dqinput = sys.stdin.readline inf = 1e10 def dijkstra(): dp = [inf] * n # 최단 거리 저장할 배열 q = [] heappush(q, (0, s, s)) # 시작점의 거리 0으로 설정하고 큐.. Baekjoon 2162. 선분 그룹 / Python https://www.acmicpc.net/problem/2162 2162번: 선분 그룹첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하www.acmicpc.net### Python- 함수 설명1. union_find : 노드의 루트 노드를 찾는 함수2. union_set : 두 노드가 속한 그룹을 합치는 함수3. CCW : 세 점의 방향을 계산하는 함수4. check : 두 선분의 교차여부를 판단하는 함수- 알고리즘 설명1. 입력된 선분들의 교차여부를 판단하여 같은 그룹으로 묶는다.2. 이 과정에서 유니온-파인드 알고리즘을 이.. Baekjoon 11014. 컨닝 2 / Python https://www.acmicpc.net/problem/11014 11014번: 컨닝 2최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한www.acmicpc.net같은 코드로 1014. 컨닝 도 풀린다.https://www.acmicpc.net/problem/1014 1014번: 컨닝최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한www.acmicpc.net- 함수 설명1. sol() : 내가 컨닝할 수 있거나, 컨닝당할 수 있는 위치에,.. 이전 1 ··· 7 8 9 10 다음