개인사

리뷰MST인데 테스트케이스 여러개를 곁들인.. 문제였다. 예제만 보고 테케를 나눠주지 않아 첫시도에 틀렸다.https://www.acmicpc.net/problem/6497 문제 풀이정답을 저장할 벡터 ans, 간선 정보를 저장할 edges, 간선 전체길이를 저장할 max_dist를 초기화 해준다.while루프를 시작하고 1번에서 초기화한 리스트 들을 모두 초기값으로 변경해 준다.n과 m 값을 받고 해당 값들이 모두 0일 경우 while루프를 종료한다.간선의 정보 m개를 가중치, 시작 노드, 종료 노드 순으로 edges 벡터에 tuple형태로 추가해 준다.max_dist에 가중치를 더해주어 전체 길이를 최신화 해준다.간선 정보를 모두 받아왔으면 간선의 가중치를 기준으로 오름차순 정렬해 준다.이후 유니온 ..

개요1. Queue일반적인 큐의 경우 선입 선출을 통해 먼저 들어왔던 데이터가 먼저 처리되는 특성을 가진다.큐 내에 {1, 2, 3, 4, 5} 가 존재한다면, 6을 push하고 front에 존재하는 값을 pop 한다면 {2, 3, 4, 5, 6}이 되고, 6을 사용하기 위해선 앞에 존재하는 2, 3, 4, 5가 모두 pop 되어야 6을 pop 할 수 있다. 2. Priority Queue기본적인 큐에서 특정 조건으로 인해 큰 값으로 정렬 되어 있는 큐이다.만약 큐에 {5, 4, 3, 2, 1}이 존재한다고 가정했을때 6을 push한 후 front에 존재하는 값을 pop 한다면, 6이 pop이 될 것이다.pq의 기본형은 내림차순 정렬이지만, 특정 compare 함수를 작성할 경우 우선순위를 다양하게 설정..

리뷰쿼리와 업데이트를 모두 미리 받아준 다음 각 업데이트에 시점에 맞는 쿼리를 출력하는 문제우선순위 큐를 썼다가, 다른 요소까지 정렬이 되는 이유로 인해 오답을 맞아 sort를 사용했다.이후 int 범위를 넘어가는 케이스가 있어 long long 타입으로 변경하니 통과하였다. 문제 풀이n값을 입력 받고 lst에 수열의 정보를 입력 받고, tree 벡터의 사이즈를 4 * n만큼으로 초기화 해주고 build 해준다.m개의 쿼리를 받아준다, 업데이트 관련 쿼리인 경우 uq 큐에 변경할 인덱스와 값을 추가해 준다.질의 관련 쿼리인 경우 튜플을 통해 업데이트 순번, 시작, 종료 인덱스, 쿼리의 질문 순서를 4개 사이즈의 tuple형태로 temps 벡터에 추가해 준다.temps 벡터를 업데이트 순번을 기준 오름차순..

리뷰각 노드의 좌표를 입력 받고 모든 노드를 연결하는 가장 적은 거리를 도출하는 MST 문제 문제 풀이n줄에 걸쳐 입력되는 모든 좌표 값을 lst 벡터에 추가 해준다.float, int, int 형식의 튜플 벡터 edges를 초기화 해준다.각 노드간의 거리를 모두 구해 edges 벡터에 거리, 시작 노드, 도착 노드 순으로 추가해 준다.이후 edges 벡터를 거리 순으로 오름차순 정렬 해주고 유니온 파인드를 통해 최소 신장 트리를 구한다.최소 신장 트리를 과정에서 float 변수 sum에 누적 거리를 저장해 주고 소숫점 2자리 까지 출력해 준다. 참고 사항좌표가 float 형식으로 입력 되지만 vector> 형식으로 입력 받아도 통과 하는걸 보니 정수형으로 입력 받아도 무방한 것 같다.  정답 코드#in..

개요1. BFS의 특징 및 설계특징최단 경로를 찾는다.인접한 모드 노드를 방문 처리를 하며 탐색 한다.단계별로 확장 (방문 처리에 값을 할당) 하여 몇 차수만에 왔는지 기록을 한다.설계큐(대기열) 및 방문 배열 생성큐에 시작 노드 삽입 후 큐가 빌 때까지 순환 루프를 진행큐에서 맨 앞에 있는 노드를 확인 및 추출현재 노드와 인접한 노드를 탐색하여 존재 한다면 다음 후보를 노드에 추가2 ~ 4번의 루틴을 반복해 준다. 2. Flood FillFlood : 홍수, Fill : 채우다. 퍼져 나가면서 방을 채우듯이 채워 나가며 진행하는 N차원 맵상에서의 BFS  일반적인 BFS에서 노드가 아닌 시작 좌표를 기준으로 방향 배열을 통해 특정 방향으로 탐색을 진행하며, 방문 배열에 방문 체크가 아닌 값을 할당해 준..

리뷰아주 기초적인 MST 문제, 최소 스패닝 트리를 만든 후 각 간선의 가중치의 합을 출력하면 된다. 문제 풀이컴퓨터의 수는 최대 1000개 까지 주어지므로 1001 크기의 정수형 배열 nodes를 전역으로 초기화 해준다.n과 m 값을 받아오고 정수 세개를 인자로 받는 tuple의 1차 벡터 배열인 edges를 초기화 해준다.m개의 정보 출발 노드, 도착 노드, 간선의 가중치를 edges 배열에 가중치, 시작 노드, 도착 노드 순으로 추가한다.edges 벡터를 오름차순으로 정렬해 준다.nodes를 1부터 N까지 각각의 인덱스에 자기 인덱스를 value로 갖게끔 갱신해 준다.간선의 가중치 합을 저장할 정수형 변수 sum을 0으로 초기화 해준다.다시 간선의 개수 m개 만큼 for문을 시작하고, 각 간선의 정..

리뷰MST를 구하고 그 과정에서 가장 큰 가중치를 가진 간선의 가중치를 빼주는 문제 문제 풀이n의 최대값은 10만이므로 100001 크기의 nodes 배열을 초기화 해준다.n과 m 값을 받고 m만큼의 가중치와 노드 정보를 edges 벡터에 추가해 준 뒤 오름차순으로 정렬해 준다.Union-Find를 통해 최소 신장 트리를 만들어 주고, 트리를 만들며 각 가중치를 더해주며 가장 큰 가중치를 구해준다.가중치의 합에서 가장 큰 가중치를 뺀 값을 출력해 준다. 참고 사항간선의 유지비가 최대 1000이고, 간선은 최대 100만개 이므로 int 범위 내에서 문제를 해결할 수 있다.  정답 코드#include #include #include #include using namespace std;int nodes[100..

리뷰인접 행렬을 입력받아 최소 신장 트리를 구하는 문제 문제 풀이행성의 최대 수는 1000이니 nodes 배열을 1001 크기로 초기화 해준다.정수 인자 3개를 받는 튜플을 인자로 갖는 벡터 edges를 초기화 해준다.n값을 입력 받고 n * n 크기의 for문을 개행하여 값을 받아준다.단방향 간선을 받아도 무방하기에, j >= i 인 경우 가중치, 시작, 종료 노드를 튜플 형태로 edges 벡터에 추가한다.edges 벡터를 오름차순으로 정렬하고 nodes의 각 노드들의 value를 자기 자신을 갖도록 초기화 해준다.최소 가중치 합을 저장할 sum 변수를 0으로 초기화 하고 해당 변수에 최소 신장 트리의 가중치 합을 더한다.이후 sum을 출력해 준다. 참고 사항가중치는 최대 1억이 주어지기 때문에 int..

리뷰최소 신장 트리가 완성 되었는지의 체크 시 간선의 개수를 n개로 했다가 틀렸다 ㅠ최소신장트리가 잘 만들어 졌는지 체크가 필요한 문제 문제 풀이노드의 개수는 최대 10만이므로 nodes 배열을 100001크기로 생성해 준다.n, m값을 받아주고 각 간선의 정보를 가중치, 시작 노드, 도착 노드의 튜플 형태로 edges 벡터에 받아준다.모든 도로를 연결 했을때의 도로의 가중치를 알아야 하므로 max_sum 변수에 가중치를 모두 더해준다.edges벡터를 오름차순으로 정렬해 준 후 각 노드를 자기 자신을 value 값으로 갖게 끔 초기화 해준다.sum과 sum_cnt를 0으로 초기화 해주고 edges 배열을 순회하여 Union-Find를 통해 최소 신장 트리를 만들어 준다.만약 sum_cnt가 n - 1 크..

리뷰MST의 기초가 되는 문제이다. 문제 풀이노드의 개수 v와 간선의 개수 e를 입력 받고 간선의 개수 만큼의 for문을 개행 한다.튜플 벡터 edges 를 초기화 해주고, 숫자 a, b, c를 입력 받은 후 c, b, a 순으로 튜플에 푸시 해준다.edges 벡터를 오름차순으로 정렬 해준다, 이후 Union-Find를 통해 최소 신장 트리를 만들어 주면 된다.변수 sum을 0으로 초기화 하고 가중치를 기준으로 오름 차순으로 정렬 되어 있는 edges벡터를 순회를 돈다.만약 1번 인덱스와 2번 인덱스 요소의 루트 노드가 같다면 이미 간선이 추가되어 있는 상태이므로 continue아니라면 1번 인덱스와 2번 인덱스를 Union 해준 후 해당 간선의 가중치를 sum에 더해준다.for문이 종료된 후 sum을 ..