ehdbs0903 ehdbs0903

문제https://www.acmicpc.net/problem/11726    코드1. Python# 미리 계산된 값들을 저장하는 리스트 dp를 선언dp = [0, 1, 2, 3]# n을 입력받음 (계산할 n번째 값)n = int(input())# dp 리스트에 저장된 값이 부족할 경우를 대비하여 n번째 값까지 계산for i in range(len(dp), n + 1): # dp[i] = dp[i-1] + dp[i-2]의 점화식을 사용하여 값을 계산하고 리스트에 추가 dp.append(dp[i - 1] + dp[i - 2])# n번째 값을 10007로 나눈 나머지를 출력print(dp[n] % 10007) 2. C++#include using namespace std;int main() { ..

문제https://www.acmicpc.net/problem/11724    코드1. Pythonimport syssys.setrecursionlimit(10**6) # 파이썬의 재귀 한도를 늘려 DFS가 깊게 호출될 수 있도록 설정input = sys.stdin.readline # 입력 속도를 빠르게 하기 위해 sys.stdin.readline 사용# 입력값으로부터 노드 수 n과 간선 수 m을 입력받음n, m = map(int, input().split())# 그래프를 인접 행렬로 표현 (n+1 크기의 2차원 리스트를 생성)# 1번 노드부터 시작하기 때문에 n+1 크기로 설정graph = [[0] * (n+1) for _ in range(n+1)]visited = [0] * (n+1) # 방문 여..

비트마스킹(Bitmask) 알고리즘이란?비트마스킹 알고리즘은 상태나 집합을 효율적으로 표현하고 조작하기 위해 비트 연산을 사용하는 알고리즘이다. 주로 배열 대신 비트를 사용하여 메모리를 절약하고, 빠른 연산을 통해 성능을 개선할 수 있다.알고리즘의 기본 아이디어는 각 상태나 원소를 비트로 표현하고, 비트 연산을 통해 빠르게 조작하는 것이다.  시간복잡도비트마스킹 알고리즘의 시간 복잡도는 문제의 특성에 따라 달라진다. 예를 들어, 비트마스킹을 사용하여 방문 여부를 표시하고 탐색하는 경우, 비트 연산 자체는 O(1)로 매우 빠르다. 그러나 상태를 표현하는 비트마스크가 n개의 비트를 사용하는 경우, 모든 가능한 상태를 탐색하거나 확인해야 한다면, 최악의 경우 시간 복잡도는 O(2^n)이 될 수 있다. 이는 모..

문제https://www.acmicpc.net/problem/11723    코드1. Pythonimport sysinput = sys.stdin.readline # 빠른 입력을 위해 sys.stdin.readline 사용m = int(input()) # 명령의 수 입력s = set() # 집합을 사용하여 숫자 저장# m개의 명령어 처리for _ in range(m): temp = input().rstrip() # 명령어를 입력받고 공백을 제거 op = temp[:2] # 명령어의 앞 두 글자를 사용하여 명령 종류를 판단 # 'add' 명령어: 집합에 숫자를 추가 if op == "ad": x = int(temp[-2:]) # 명령의 마지막 두 글자에서..

문제https://www.acmicpc.net/problem/11659    코드1. Pythonimport sysinput = sys.stdin.readline # 빠른 입력을 위해 sys.stdin.readline 사용sums = [] # 누적 합을 저장할 리스트nums = [] # 입력받은 숫자 리스트# n: 숫자의 개수, m: 구간 합을 계산할 횟수n, m = map(int, input().split())# n개의 숫자 입력받기nums = list(map(int, input().split()))# 첫 번째 숫자의 누적 합을 sums에 추가sums.append(nums[0])# 나머지 숫자들의 누적 합을 계산하여 sums 리스트에 저장for i in range(1, n): sums.app..

플로이드-워셜(Floyd-Warshall) 알고리즘이란?플로이드-워셜 알고리즘은 그래프 내의 모든 정점 쌍에 대해 최단 경로를 찾는 알고리즘이다. 인접 행렬을 사용하여 구현되며, 그래프의 가중치가 음수일 수 있지만, 음수 사이클이 없는 경우에만 유효하다.알고리즘의 기본 아이디어는 모든 가능한 경로를 시도하면서 더 짧은 경로가 발견되면 이를 갱신하는 것이다.  시간복잡도플로이드-워셜 알고리즘의 시간 복잡도는 O(n^3)이다. 그래프의 모든 정점 쌍에 대해 경로를 확인하기 때문이다. 여기서 n은 그래프의 정점 수를 의미한다.  플로이드-워셜의 기본 원리초기화:각 정점 간의 최단 경로를 저장할 2차원 배열 dist를 초기화그래프의 직접 연결된 정점 사이의 가중치로 dist 배열을 설정dist[i][i]는 0으..

문제https://www.acmicpc.net/problem/11403    코드1. Pythonimport sysinput = sys.stdin.readline # 빠른 입력을 위해 sys.stdin.readline 사용# 정점의 수 n 입력받기n = int(input())# 그래프의 인접 행렬 입력받기graph = [list(map(int, input().split())) for _ in range(n)]# 플로이드-워셜 알고리즘 적용# 모든 정점 쌍 (i, j)에 대해 경로가 존재하는지 확인for k in range(n): # 경유할 정점 k for i in range(n): # 출발 정점 i for j in range(n): # 도착 정점 j # 정점 ..

문제https://www.acmicpc.net/problem/11399    코드1. Pythonimport sysinput = sys.stdin.readline # 빠른 입력을 위해 sys.stdin.readline 사용n = int(input()) # 사람의 수 n 입력받기# 각 사람이 돈을 인출하는 데 걸리는 시간을 리스트로 입력받기p = list(map(int, input().split()))p.sort() # 시간을 오름차순으로 정렬 (최소 시간으로 만들기 위함)# 인출 시간이 누적되도록 리스트를 갱신for i in range(n-1): p[i+1] += p[i] # 이전 사람까지의 총 시간을 다음 사람의 시간에 더함print(sum(p)) # 모든 사람이 돈을 인출하는 데 걸리는..