ehdbs0903 ehdbs0903

문제https://www.acmicpc.net/problem/11286    코드1. Pythonimport sysimport heapqinput = sys.stdin.readline # 빠른 입력을 위해 sys.stdin.readline 사용heap = [] # 절댓값 힙을 저장할 리스트 초기화for _ in range(int(input())): # 첫 번째 입력: 명령어의 수 x = int(input()) # 각 명령어에 대한 입력 값 if x: # x가 0이 아닌 경우 (힙에 값을 추가하는 경우) # 절댓값을 기준으로 하는 우선순위 큐를 위해 (절댓값, 실제 값) 형태로 저장 heapq.heappush(heap, (abs(x), x)) else: ..

문제https://www.acmicpc.net/problem/11279    코드1. Pythonimport heapqimport sysdef main(): input = sys.stdin.read # 표준 입력 전체를 한 번에 읽어오는 함수 data = input().split() # 읽어온 입력을 공백을 기준으로 분리하여 리스트로 저장 n = int(data[0]) # 첫 번째 값은 입력의 개수 n pq = [] # 최대 힙을 구현하기 위한 리스트 (우선순위 큐로 사용) for i in range(1, n + 1): x = int(data[i]) # 입력된 정수 x if x: heapq.heappush(pq, -x) #..

문제https://www.acmicpc.net/problem/11047    코드1. Pythondef main(): # n: 동전의 종류 수, k: 목표 금액 n, k = map(int, input().split()) coins = [] # 동전의 종류를 저장할 리스트 for _ in range(n): coins.append(int(input())) # 각 동전의 가치를 입력받아 리스트에 추가 cnt = 0 # 필요한 동전의 최소 개수를 저장할 변수 # 동전 리스트를 큰 값부터 순차적으로 사용하기 위해 역순으로 접근 for i in range(n - 1, -1, -1): cnt += k // coins[i] # 현재 동전으로 만들 수..

문제https://www.acmicpc.net/problem/10026    코드1. Pythonfrom collections import dequedef bfs(x, y, n, graph, visited): """ BFS를 사용하여 연결된 영역을 탐색하는 함수. :param x: 시작 위치의 행 인덱스 :param y: 시작 위치의 열 인덱스 :param n: 그래프의 크기 (nxn) :param graph: 색상 정보를 담고 있는 2차원 리스트 :param visited: 방문 여부를 기록하는 2차원 리스트 """ queue = deque() # BFS를 위한 큐 초기화 color = graph[x][y] # 현재 위치의 색상 저장 ..

누적 합(Prefix Sum) 알고리즘이란?주어진 배열에서 각 요소까지의 합을 계산하여 새로운 배열을 생성하는 알고리즘이다. 이는 특정 구간의 합을 빠르게 계산할 때 유용하며, 특히 큰 데이터를 다룰 때 효율적이다.알고리즘의 기본 아이디어는 원래 배열의 첫 번째 요소부터 마지막 요소까지의 합을 점진적으로 계산하여 새로운 배열에 저장하는 것이다.  시간복잡도누적합 알고리즘의 시간복잡도는 O(n)이다. 배열의 각 요소에 대해 한 번씩만 계산하면 되기 때문에 매우 효율적이다.누적합을 통해 구간 합을 계산할 때는 추가적인 반복 없이 O(1) 시간에 계산할 수 있다.  누적 합의 기본 원리초기화:첫 번째 요소를 그대로 사용하여 누적합 배열의 첫 번째 요소를 초기화계산:두 번째 요소부터 마지막 요소까지의 합을 계산..

C++에서 map과 unordered_map는 둘 다 키-값 쌍을 저장하는 연관 컨테이너로, 유사한 기능을 제공하지만 내부 구현 및 성능 특성에서 큰 차이가 있다. 각각의 차이점을 아래와 같이 비교할 수 있다.  map vs unordered_map1. map:  구조: Red-Black 트리와 같은 이진 탐색 트리로 구현된다.원소 순서: 키를 기준으로 정렬된 상태로 원소들이 저장된다.탐색, 삽입, 삭제 속도: 평균적으로 O(log n)의 시간 복잡도.메모리 사용량: 트리 구조를 유지하기 위해 각 노드가 추가적인 포인터(부모, 자식)를 포함하므로 메모리 사용량이 많을 수 있다.키의 비교: 기본적으로 operator범위 기반 함수 지원: lower_bound, upper_bound, equal_range와..

문제https://www.acmicpc.net/problem/9461    코드1. Pythondef main(): # DP 테이블 초기화 (1부터 100까지) dp = [0] * 101 # 기본값 설정 (문제에서 주어진 초기 조건) dp[1] = 1 # 1번째 삼각형 숫자 dp[2] = 1 # 2번째 삼각형 숫자 dp[3] = 1 # 3번째 삼각형 숫자 dp[4] = 2 # 4번째 삼각형 숫자 dp[5] = 2 # 5번째 삼각형 숫자 # DP를 이용한 점화식 계산 # dp[i] = dp[i-1] + dp[i-5] -> i번째 삼각형 숫자는 i-1번째와 i-5번째 삼각형 숫자의 합 for i in range(6, 101): ..

문제https://www.acmicpc.net/problem/9375    코드1. Pythondef main(): t = int(input()) # 테스트 케이스의 수 입력 for _ in range(t): # 각 테스트 케이스에 대해 반복 n = int(input()) # 각 테스트 케이스에서의 아이템 수 입력 mp = {} # 아이템 종류별 개수를 저장할 딕셔너리 초기화 for _ in range(n): # 아이템 수만큼 반복 name, type_ = input().split() # 아이템의 이름과 종류 입력 if type_ in mp: # 이미 해당 종류가 딕셔너리에 있으면 ..