개인사

[P4] 백준 13907번 세금 C++ 다익스트라, 다이나믹 프로그래밍

리뷰 https://www.acmicpc.net/problem/13907슬슬 고난도 다익스트라 + DP문제도 어떻게 접근해야할지 최적해가 보이기 시작했다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수k : 쿼리의 개수를 저장할 변수s, d : 시작 지점과 도착 지점의 노드 번호를 저장할 변수Edge : 이동할 노드 번호와 간선의 가중치를 정의할 구조체, 간선의 가중치를 기준으로 오름차순 정렬한다.edges : 인접 리스트를 저장하기 위한 Edge타입 벡터 배열Pos : 현재 위치와 사용한 간선의 개수, 누적 가중치를 정의할 구조체, 누적 가중치 기준으로 오름차순 정렬한다. 함수1. dijkstravector dijkstra() {..

리뷰 https://www.acmicpc.net/problem/1162다익스트라 + DP의 또다른 유형의 문제, 풀면 풀수록 이 유형이 재밌다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수k : 최대로 포장할 수 있는 도로의 개수를 저장할 변수Edge : 간선 정보를 정의할 구조체, 간선의 가중치를 기준으로 오름차순 정렬한다.edges : 간선 정보를 인접 리스트로 저장하기 위한 Edge타입 벡터 배열Pos : 현재 노드와 포장 횟수, 누적 가중치를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstrall dijkstra() { priority_queue pq; pq.push({ 1, 0, 0 });..

리뷰 https://www.acmicpc.net/problem/13308다익스트라 + DP문제에 대해 어느정도 이해가 가기 시작했다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수p : 각 노드의 가중치들을 저장할 배열Edge : 이동할 노드와 가중치 등 간선 정보를 정의할 구조체, 간선 가중치를 기준으로 오름차순 정렬한다.edges : 간선 정보를 저장할 Edge타입 벡터 배열Pos : 현재 노드와 누적 연료 최소값, 누적 비용을 정의할 구조체, 누적 비용을 기준으로 오름차순 정렬한다. 함수1. dijkstrall dijkstra() { priority_queue pq; pq.push({ 1, p[1], 0 }); vector> ..

리뷰 https://www.acmicpc.net/problem/12930간선이 두개인 그래프에서 최단 경로를 찾는 DP + 다익스트라를 활용한 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수Edge : 간선의 두 가중치를 정의할 구조체Pos : 현재 노드 번호와 누적 가중치를 정의할 구조체, 두 가중치의 곱을 기준으로 오름차순 정렬한다.edges : 간선 정보를 인접 행렬로 저장하기 위한 Edge타입 2차원 배열 함수1. get_edgesvoid get_edges(int index) { for (int i = 0; i > ch; if (ch == '.') continue; int w = ch - '0'; if (index == 1) edges[i][..

리뷰 https://www.acmicpc.net/problem/13418크루스칼 알고리즘으로 문제를 풀이하였다. 문제에 함정이 많다. 조심! 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 건물의 개수를 저장할 변수m : 도로의 개수를 저장할 변수Edge : 간선 정보를 정의할 구조체edges : 간선 정보를 저장할 Edge타입 벡터nodes : 각 건물이 속한 그룹 정보를 저장할 배열 함수1. bestbool best(const Edge& left, const Edge& right) { return left.v 간선을 내리막길을 기준으로 정렬하기 위한 함수 2. worstbool worst(const Edge& left, const Edge& right) { return left.v > ..

리뷰 https://www.acmicpc.net/problem/16991간선의 가중치가 실수인 외판원 순회 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 도시의 수를 저장할 변수Pos : 도시의 좌표를 정의할 구조체poses : 도시의 좌표들을 저장할 Pos타입 배열Edge : 간선 정보를 정의할 구조체edges : 간선 정보를 저장할 Edge타입 벡터 배열dp : 방문 최소값을 저장할 2차원 배열 함수1. get_distdouble get_dist(const Pos& pos1, const Pos& pos2) { return sqrt(pow(pos1.x - pos2.x, 2) + pow(pos1.y - pos2.y, 2));} 두 좌표 사이의 거리를 구하기 위한 함수 2. dfsdou..

리뷰 https://www.acmicpc.net/problem/2632문제를 쉽게 접근했다가 피자가 원형꼴이라는 것에 대한 처리에 애를 먹은 문제 전역 변수없음 함수1. get_slicesvoid get_slices(vector& pizza, unordered_map& dic, int size, int k) { vector prefix(2 * size + 1, 0); for (int i = 0; i 피자의 연속된 구간합을 구하기 위한 함수 문제풀이k, n, m에 값을 입력 받고, 벡터 a를 n크기로, b를 m크기로 초기화 한다. 해시맵 A, B도 초기화 해준다.a, b에 각각 n, m개의 요소를 입력 받아 저장해 준다.get_slices함수에 a, b와 관련된 요소들을 매개변수로 전달하여 호출해 ..

리뷰 https://www.acmicpc.net/problem/22860해시를 활용한 자료구조 + 파싱을 통한 간선 제작 + 깊이 우선 탐색을 활용하여 푼 문제 폴더 정리 관련 문제는 시작은 어렵지만 풀다 보면 재미가 있다. 전역 변수folders : 폴더명을 정수로 치환하기 위한 해시맵files : 파일명을 정수로 치환하기 위한 해시맵childs : 현재 폴더에 존재하는 파일의 번호를 저장하기 위한 해시맵 + 해시셋edges : 폴더 간 간선 정보를 정의하기 위한 인접 리스트f1 : 폴더의 번호를 인덱싱 하기 위한 변수f2 : 파일의 번호를 인덱싱 하기 위한 변수total : 각 탐색 시 마다 전체 파일의 개수를 저장할 변수 함수1. dfsvoid dfs(short sn, unordered_set& ..

리뷰 https://www.acmicpc.net/problem/3649투 포인터 말고 이분 탐색으로 풀려고 접근 했다가 틀렸다. 이분 탐색 접근이 정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다. 라는 조건이 좀 까다로운 것 같다. 전역 변수x : 구멍이 너비를 저장할 변수n : 레고 조각의 개수를 저장할 변수 함수없음 문제풀이x를 입력 받는 것을 조건으로 while루프를 수행한다.매 루프마다 x에 1000만을 곱해주어 나노미터 단위로 변경해 준다.매 테스트 케이스 마다 n값을 입력 받고, 벡터 legos를 n크기로 초기화해 준다.n개의 레고의 길이 정보를 legos벡터에 입력 받고, sort함수를 통해 legos벡터를 오름차순으로 정렬해 준다.변수 l을 0, r을 n - 1로 ..

리뷰 https://www.acmicpc.net/problem/9694최단 거리를 구하고 방문한 노드의 번호를 출력하는 문제 전역 변수t : 테스트 케이스의 개수를 저장할 변수n : 노드의 개수를 저장할 변수m : 간선의 개수를 저장할 변수Edge : 간선 정보를 정의할 구조체Pos : 현재 노드와 누적 가중치를 정의할 구조체, 누적 가중치를 기준으로 오름차순 정렬한다. 함수1. dijkstravector dijkstra(const vector>& edges) { priority_queue pq; pq.push({ m - 1, 0 }); vector dist(m, 2e9); vector path(m); dist[m - 1] = 0; while (!pq.empty()) { Pos pos = pq.top..