ehdbs0903 ehdbs0903

문제https://www.acmicpc.net/problem/1149    코드1. Pythonimport sysinput = sys.stdin.readline # 빠른 입력을 위해 sys.stdin.readline 사용# 집의 수 입력n = int(input())# 각 집을 칠하는 비용을 저장할 리스트 pp = []for _ in range(n): p.append(list(map(int, input().split()))) # 각 집을 칠하는 비용을 입력받아 리스트에 추가# 1번째 집부터 n번째 집까지 최소 비용을 누적 계산for i in range(1, n): # 현재 집을 빨간색으로 칠하는 최소 비용은 이전 집을 초록색 또는 파란색으로 칠한 비용 중 최소값에 현재 집을 빨간색으로 칠하는..

문제https://www.acmicpc.net/problem/1043    코드1. Pythonimport sysinput = sys.stdin.readline # 빠른 입력을 위해 sys.stdin.readline 사용# n: 사람 수, m: 파티 수n, m = map(int, input().split())# 진실을 알고 있는 사람들의 집합. 처음 입력은 첫 번째 숫자가 진실을 아는 사람 수이므로 [1:]로 슬라이싱하여 사람들의 번호만 가져옴knowing = set(input().split()[1:])# 각 파티에 참여하는 사람들의 정보를 저장하는 리스트 (각 파티는 집합으로 표현)parties = [set(input().split()[1:]) for _ in range(m)]# 모든 파티에 대해 진..

유니온-파인드(Union-Find) 알고리즘이란? 유니온-파인드 알고리즘은 서로소 집합(Disjoint Set)을 효율적으로 관리하는 자료구조이다. 주로 그래프에서 사이클을 판별하거나, 네트워크 연결 문제에서 각 노드 간의 연결 여부를 확인하는 데 사용된다.알고리즘의 기본 아이디어는 여러 개의 원소가 존재하는 집합을 트리 구조로 표현하고, 두 집합을 합치거나(Union) 특정 원소가 속한 집합을 찾는(Find) 연산을 효율적으로 수행하는 것이다.  시간복잡도유니온-파인드 알고리즘의 시간 복잡도는 경로 압축(Path Compression)과 랭크에 의한 합치기(Union by Rank)를 사용할 경우, 거의 상수 시간인 O(α(n))이 된다. 여기서 α(n)은 아커만 함수의 역함수로, 매우 느리게 증가하는..

C++에서 map에 키가 존재하는 지 확인할 때, 아래 두 코드를 볼 수 있다.map mp;// 1if (mp[a] == 0)// 2if (mp.find(a) == mp.end())  두 코드의 차이점을 알려면 컴퓨터가 어떻게 동작하는 지를 알아야한다.  map[a] vs map.find(a)1. map[a]:map에서 키 a를 찾고 그에 해당하는 값을 반환한다.만약 a가 map에 존재하지 않는 경우, a를 맵에 자동으로 삽입하고, 값은 0이나 기본값으로 초기화한다.2. map.find(a):키가 존재하면 해당 키의 이터레이터를, 존재하지 않으면 map.end()를 반환한다.  결론map[a]는 의도치 않게 키 추가가 일어나고, 이는 메모리 사용량을 증가시킨다.키의 존재 여부만 확인하고 싶을 때는 map..

auto 타입 추론은 대체로 템플릿 타입 추론과 같지만, auto 타입 추론은 중괄호 초기치가 std::initializer_list를 나타낸다고 가정하는 반면 템플릿 타입 추론은 그렇지 않다는 차이가 있다.더보기//-----------------------------------------------------------------------------// auto를 이용해서 변수를 선언할 때// auto는 템플릿의 T와 동일한 역할을// 하며, 변수의 타입 지정자(type specifier)는// ParamType과 동일한 역할을 한다. auto x = 27; // 여기서 x의 타입 지정자는 그냥 auto// 자체이다. 반면, 다음 선언에서 const auto cx = x; // 타입 지정자는 cons..

문제https://www.acmicpc.net/problem/30804     코드1. C++#include #include #include using namespace std;int main() { int n; cin >> n; // 과일의 수 입력 vector fruits(n); // 과일의 종류를 저장할 벡터 // 과일 종류 입력 for (int i = 0; i > fruits[i]; } unordered_map cnt; // 과일의 종류별 개수를 저장할 맵 int left = 0, max_len = 0; // 슬라이딩 윈도우의 왼쪽 포인터와 최대 길이를 저장할 변수 // 슬라이딩 윈도우를 사용하여 최대 연속 부분 배열 찾기 for (in..

문제https://www.acmicpc.net/problem/21736    코드1. Pythonimport sysfrom collections import dequeinput = sys.stdin.readline # 빠른 입력을 위해 sys.stdin.readline 사용# BFS(너비 우선 탐색) 함수 정의def bfs(x, y): # 상하좌우 탐색을 위한 방향 벡터 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 방문 여부를 기록하는 2차원 리스트 visited = [[0] * m for _ in range(n)] cnt = 0 # 만날 수 있는 사람의 수를 저장하는 변수 # BFS를 위한 큐 초기화 및 시작 위치 삽입 q = d..

문제https://www.acmicpc.net/problem/18870    코드1. Pythonn = int(input()) # 배열의 크기를 입력받음arr = list(map(int, input().split())) # n개의 정수를 입력받아 리스트로 저장arr2 = sorted(set(arr)) # 중복을 제거하고 정렬하여 순서를 정함# 각 값에 대해 해당 값이 정렬된 리스트에서 몇 번째인지 저장하는 딕셔너리 생성dic = {arr2[i]: i for i in range(len(arr2))}# 입력받은 배열의 각 원소에 대해 압축된 좌표를 출력for i in arr: print(dic[i], end=' ') 2. C++#include #include #include #include usi..