개인사

리뷰 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 알고리즘 고득점 Kit 그리디에서 왜 MST가 나오는지는 모르겠지만 기본적인 문제라 쉽게 풀었다.  전역 변수nodes : 유니온 파인드를 통해 섬의 그룹화를 하기 위한 정수형 배열, 크기는 섬의 최대 100으로 설정한다.Bridge : 간선 정보를 저장하기 위한 구조체, 내부적으로 sort를 해주어야 하니 내부에 cmp함수를 작성한다. 함수1. Findint Find(int a) 매개변수로 받은 노드의 그룹 정보를 찾기 위한 함수매개변수로 노드 번호를 변수 a로 받아준다.nodes배열의 a인덱스가 a라면 a를 리턴해 준다.nodes배열의 a인덱스가 ..

리뷰 다른 MST 문제와는 다르게 모든 간선을 구하는 것이 아닌 필요한 간선만 구해 MST를 구하는 문제기존의 모든 간선을 구하는 방식을 사용했더니 바로 메모리 초과가 출력되었다.https://www.acmicpc.net/problem/2887 문제 풀이전역 변수n : 행성의 개수를 저장할 변수nodes : Union-Find를 통해 MST를 구할 노드의 배열, 노드의 최대 크기인 10만보다 1크게 설정해 준다.Pos : 행성의 각 축 좌표 위치 정보를 나타낼 구조체, sort가 필요하므로 compare함수를 작성해 준다.Edge : 행성간 간선의 정보를 나타낼 구조체, 마찬가지로 sort가 필요하다.PI : x, y, z축과 행성의 번호를 저장할 Pos타입 벡터n값을 입력 받고, 1 ~ n까지 행성 정..

리뷰double 조심! int 오버플로우 조심!각 노드의 좌표가 주어지고 모든 노드를 연결하는 최소값을 구하는 문제https://www.acmicpc.net/problem/1774 문제 풀이n과 m 값을 받아오고 각 노드의 좌표를 구조체 배열로 받아오고, 자신의 인덱스를 value로 갖는 nodes 배열을 초기화m줄에 걸쳐 이미 연결되어 있는 노드들 끼리는 Union 처리를 해준다.모든 노드들 간의 간선을 edges 벡터에 저장해 준다. 이때 각 간선의 거리를 구해주어야 한다.간선의 거리를 기준으로 오름차순 정렬해 준 후 모든 노드가 연결 되도록 부분 집합을 활용해 연결해 준다.각 간선이 연결 될때마다 total 변수에 거리의 합을 구해준 후 total을 출력해 준다. 참고 사항dist를 구할때 좌표를 ..

리뷰모든 노드를 연결하는 최소비용을 구하는 문제, 노드가 섬이라는 점에서 2차원 시뮬레이션 구현 문제이다.https://www.acmicpc.net/problem/17472 문제 풀이n과 m값을 입력 받고 2차원 맵을 입력 받는다.각각의 섬을 노드화 시켜준다. n * m맵을 순회하며 1을 만날 경우 바다가 아닌 지형은 모두 index로 맞추어 준다, 나는 2부터 index를 매겨줬고, 이때 노드의 개수 또한 세어주고, 해당 노드의 시작 좌표를 구조체 형태로 큐에 추가해 준다.큐에 추가된 노드를 기준으로 bfs를 실행해 각 섬까지의 모든 간선을 구해 edges 벡터에 추가해 준다.edges 벡터를 간선 기준으로 정렬 해주고, 유니온 파인드를 통해 최소 간선 비용을 구해준다.만약 모든 노드가 연결되지 못한다..

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

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

리뷰아주 기초적인 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 크..