개인사

[P4] 백준 1298번 노트북의 주인을 찾아서 C++ 이분 매칭

리뷰 https://www.acmicpc.net/problem/1298n값이 작고 m값이 큰 이분매칭 문제  전역 변수N : 학생 배열의 최대 크기를 정의할 상수 변수M : 노트북 배열의 최대 크기를 정의할 상수 변수n : 학생의 수를 저장할 변수m : 노트북의 수를 저장할 변수ans : 정답을 저장할 변수mat : 노트북을 가진 학생의 번호를 저장할 배열v : 노트북을 참조한 시간을 저장할 배열t : 탐색 시간을 정의할 변수 함수1. dfsbool dfs(int node) { if (v[node] == t) return false; v[node] = t; for (int next : edges[node]) { if (!mat[next]) { mat[next] = node; return tru..

[P4] 백준 2188번 축사 배정 C++ 이분 매칭

리뷰 https://www.acmicpc.net/problem/2188이분 매칭의 기초적이 문제, 최적화를 하는 것에 신경을 써봤다.  전역 변수N : 소 관련 배열의 최대 크기를 정의할 상수 변수M : 축사 관련 배열의 최대 크기를 정의할 상수 변수n : 소의 개수를 저장할 변수m : 축사의 개수를 저장할 변수c : 소가 원하는 축사의 개수를 저장할 변수j : 소가 원하는 축사의 번호를 저장할 변수ans : 축사의 들어갈 수 있는 소의 개수를 저장할 변수edges : 각 소가 원하는 축사의 번호를 저장할 벡터 배열mat : 축사에 배정된 소의 번호를 저장할 배열v : 축사를 방문한 시간을 저장할 배열t : 방문 시간을 저장할 변수 함수   문제풀이1. dfsbool dfs(int node) { if (..

[P4] 백준 11376번 열혈강호 2 C++ 이분 매칭

리뷰 https://www.acmicpc.net/problem/11376작업자가 최대 2개까지의 작업을 수행할 수 있는 문제  전역 변수N : 작업자 관련 배열의 최대 크기를 정의할 상수 변수M : 작업 관련 배열의 최대 크기를 정의할 상수 변수n : 작업자의 수를 저장할 변수m : 작업의 개수를 저장할 변수c : 작업자 당 작업의 개수를 저장할 변수j : 작업의 번호를 저장할 변수ans : 수행할 수 있는 작업의 개수를 저장할 변수edges : 작업자가 수행할 수 있는 작업의 번호를 저장할 벡터 배열match : 작업을 맡은 작업자 번호를 저장할 배열v : 마지막으로 작업을 순회한 시간을 저장할 배열t : 순회 시간을 저장할 변수 함수1. dfsbool dfs(int node) { for (int ne..

리뷰 https://www.acmicpc.net/problem/11375이분 매칭의 기본이 되는 문제  전역 변수N : 배열의 최대 크기를 정의하기 위한 상수 변수n : 직원의 수를 저장할 변수m : 일의 개수를 저장할 변수mat : 일을 담당하는 직원의 번호를 저장할 배열v : 일이 탐색된 시간을 저장할 배열t : 현재 탐색 중인 시간을 저장할 변수edges : 직원이 담당할 수 있는 일의 번호를 저장할 벡터 배열 함수1. dfsbool dfs(int node) { for (int next : edges[node]) { if (v[next] == t) continue; v[next] = t; if (!mat[next] || dfs(mat[next])) { mat[next] = node; r..

리뷰 https://www.acmicpc.net/problem/182231에서 v까지의 최단 경로와 p를 거쳐가는 경로의 길이가 같은지 여부를 찾는 문제  전역 변수V : 배열의 최대 크기를 저장할 상수 변수v : 정점의 개수를 저장할 변수e : 간선의 개수를 저장할 변수p : 건우가 위치한 정점을 저장할 변수Edge : 간선 정보 다음 노드 nn, 간선의 크기 nv를 정의할 구조체edges : 간선 정보를 저장할 Edge타입 벡터Pos : 시뮬레이션 정보 현재 노드 cn, 누적 간선 크기 cv를 정의할 구조체, cv를 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra(int sn, int dn) { priority_queue pq; pq.push({ sn, 0 }); vecto..

리뷰 https://www.acmicpc.net/problem/12895맞왜틀 하고 있는데 질문게시판에서 쿼리의 범위 중 L이 R보다 크게 나오는 케이스가 있다는 것을 봤다.그걸 해결해주니 AC를 받았는데 음 문제에 기재하거나 예제에 있었으면 좋겠다는 생각이 들었다.로직은 맞게 구현해도 이런 것 때문에 틀린다면 시간을 많이 날릴 것 같다.  전역 변수N : 인덱스의 최대 크기를 저장할 상수 변수n : 집의 개수를 저장할 변수t : 사용할 색의 개수를 저장할 변수q : 작업의 개수를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열lazy : 업데이트 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = ..

리뷰 https://www.acmicpc.net/problem/1777[P4] 백준 1849번 순열 C++ 세그먼트 트리 [P4] 백준 1849번 순열 C++ 세그먼트 트리리뷰 https://www.acmicpc.net/problem/1849구간 합 세그먼트 트리를 통해 답을 도출하는 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 수열 원소의 개수를 저장할 변수s : 매 원소를 입력zzzz955.tistory.com위 문제의 반대 버전  전역 변수N : 순열의 최대 크기를 저장할 상수 변수n : 순열의 크기를 저장할 변수s : 각 인버전 시퀀스 값을 저장할 변수lst : 순열의 인버전 시퀀스를 저장할 배열ans : 순열의 요소를 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열..

리뷰 https://www.acmicpc.net/problem/1849구간 합 세그먼트 트리를 통해 답을 도출하는 문제  전역 변수N : 배열의 최대 크기를 저장할 상수 변수n : 수열 원소의 개수를 저장할 변수s : 매 원소를 입력 받을 변수lst : 초기엔 모두 1로, 이후엔 수열의 순서로 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = lst[s]; else { int mid = (s + e) / 2; build(node * 2, s, mid); build(node * 2 + 1, mid + 1, e); tree[node] = tree[node * 2] +..

리뷰 https://www.acmicpc.net/problem/11962구간 업데이트 + 최소값 및 구간합 세그먼트 트리 문제  전역 변수N : 배열 크기의 최대값을 저장할 상수 변수n : 배열의 크기를 저장할 변수q : 쿼리의 개수를 저장할 변수lst : 배열의 초기값을 저장할 배열MS : 세그먼트 트리의 최소값 M, 구간 합 S를 정의할 구조체tree : 세그먼트 트리 정보를 저장할 MS타입 배열lazy : 세그먼트 트리의 느린 업데이트 처리를 위한 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = { lst[s], lst[s] }; else { int mid = (s + e) / 2; build(node * 2,..

리뷰 https://www.acmicpc.net/problem/2934문제를 봤을 때 이해가 잘 되지 않았는데 예시 그래프를 보고 이해 된 내용으로 시도했다.  전역 변수N : 좌표의 최대 범위를 저장할 상수 변수n : 식물을 심은 날의 수를 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열lazy : 업데이트 정보를 저장할 배열 함수1. propagatevoid propagate(int node, int s, int e) { if (lazy[node]) { tree[node] += (e - s + 1) * lazy[node]; if (s != e) { lazy[node * 2] += lazy[node]; lazy[node * 2 + 1] += lazy[node]; } lazy[no..