개인사

리뷰다익스트라를 활용하되 최단 경로까지의 시간이 아닌, 최단 경로 중 가장 먼저 밟아야 하는 노드를 출력하는 문제 문제 풀이인접리스트를 n + 1크기로 초기화 해주고 가중치와 시작, 도착 노드를 양방향으로 추가해 준다.이제 각 노드에 대해 해당 노드를 시작점으로 하는 다익스트라를 돌려주면 된다.거리를 나타낼 dist 벡터를 n + 1 크기, 기본값을 10억으로 초기화 해주었다.경로를 나타낼 path 벡터를 n + 1 크기로 초기화 해주었다.최소 힙을 정의해 주고 거리를 0으로 시작 노드를 추가해 준뒤 시작 노드의 거리를 0으로 초기화 해준다.이후 일반적인 다익스트라 로직을 실행 하되, 경로가 갱신되었을 경우 path 벡터를 변경해 준다.만약 현재 노드의 path가 비어있을 경우 다음 노드의 경로에 다음 ..

리뷰특정 노드를 무조건 방문하고, 방문하지 않는 조건을 가진 최단 경로 문제 문제 풀이n, m을 입력 받고 인접 리스트를 n + 1 크기로 초기화 해준 뒤 단방향으로 노드와 가중치를 벡터에 넣어준다.x, y, z를 입력 받고 first에 x 에서 y까지의 최단 경로를 구하고, y부터 z까지의 최단 경로를 구한 뒤 더해준다.second에 x부터 z까지 최단 경로를 구해준다. 이때 bfs에 flag를 전달 해 y를 들릴지 말지를 정해준다.bfs가 실행되면 n + 1크기의 거리 배열을 매우 큰 값으로 초기화 해준 뒤 최소힙을 만들어 준다.시작 위치를 힙에 넣고, 거리를 0으로 초기화 해준 뒤 while 루프를 돌려준다.만약 bfs에 전달된 flag가 0이라면 기존 bfs를 진행, flag가 1이라면 다음 노드..

리뷰문제 정보가 좀 애매해서 정답 도출에 어려움을 겪었다, 그냥 다익스트라로 s 부터 t까지의 최단 경로를 구하면 된다. 문제 풀이n, m값을 입력 받고 인접 리스트를 n + 1 크기로, 거리 벡터를 n + 1, 값을 최대한 크게 설정해 준다.연결이란 두 정점이 간선을 통해 방문 가능하다고 문제에 쓰여있으니 양방향 이동이 가능하다.시작 노드와 목적지 노드를 입력 받고 시작 노드를 힙에 추가, 시작노드의 거리를 0으로 초기화 한다.while 루프를 시작해 시작 노드로 부터 각 노드까지의 최단 경로를 찾아 준다.이후 목적지 까지의 노드를 출력해 주면 된다. 참고 사항특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 ..

리뷰너비우선 탐색을 통하여 해결하는 문제, 최단 거리를 출력하고 그 경로도 기억해 주고 있다가 출력해 줘야 한다. 문제 풀이n과 k값을 입력 받고 만약 n가 k보다 클 경우 n - k와 n에서 k까지의 정수를 모두 출력해 준다.아닐 경우 bfs를 실행해 주고 큐에 정수와 경로를 저장할 pair나 구조체를 활용해 준다.최단 경로는 방문 배열을 방문하지 않은 곳은 0, 방문할 곳은 현재 이동 횟수 + 1로 해주면 된다.경로를 벡터에 추가해 주고 큐에 푸시한 후에는 꼭 pop_back을 해줘야 다음 for문 탐사에 문제가 없다.목적지에 도달한 경우 방문배열의 k인덱스를 출력, 벡터에 들어있는 경로들을 공백을 두고 출력해 준다. 참고 사항테스트 케이스1 100000211 2 3 6 12 24 48 49 98 1..

리뷰실버 1문제에서 왜 틀렸나.. 고민했는데 부등호 하나 빼먹은게 원인이었다. BFS로 풀긴 했는데 for문을 세번 사용하는 플로이드-워셜로도 풀 수 있다고 한다. 문제 풀이n값을 입력 받고 인접리스트를 n + 1 크기로 초기화 해준다.m값을 입력 받고 m줄에 걸쳐 입력되는 두개의 노드를 쌍방향으로 연결 해준다.각 노드별 케빈 베이컨 숫자를 받아올 벡터 kb를 n + 1 크기로 초기화 해준 후 브루트포스로 bfs를 돌려준다.bfs 내에서 방문 배열을 0으로 초기화, 현재 노드를 방문처리, 다른 노드에 방문 할때마다 ct를 1 올려주고 cnt에 ct를 더해준다. 만약 cnt가 여태까지의 최소 cnt보다 클 경우 바로 return 해줘도 된다.모든 노드에 대해 bfs가 종료된 후 가장 적은 케빈 베이컨 숫자..

리뷰세그먼트 트리 누적합을 활용하여 푸는 문제 문제 풀이n개의 수를 입력 받을 때 홀수일 경우 -1로 짝수일 경우 1로 저장해 준다. (반대로 해도 상관 없다.)이후 누적합 세그먼트 트리의 build, update, query를 동일하게 작성해 준다.쿼리를 입력 받고 케이스2라면 짝수의 개수를 케이스3이라면 홀수의 개수를 노출해 줄 것이다.짝수를 1로 저장했을 경우 (구간의 범위 + 쿼리의 출력값)을 2로 나누어 주면 짝수의 개수를 알 수 있다.홀수를 -1로 저장했을 경우 (쿼리의 답 - 구간의 범위)의 절댓값을 2로 나누어 주면 홀수의 개수를 알 수 있다. 참고 사항구간의 범위가 4이고 짝수가 4 ~ 0개일때의 출력값4 4 44 3 24 2 04 1 -24 0 -44 4 4 일때 짝수의 개수는 4(범위..

리뷰누적곱을 활용한 응용문제 문제 풀이n개의 수를 입력받아 트리형태로 build 해주고, k에 줄로 입력되는 쿼리를 처리해 주어야 한다.n은 최대 10만, 입력되는 숫자의 범위는 -100 ~ 100 이므로 누적곱을 해버리면 long long 타입으로 감당되지 않는다.따라서 입력을 받을 때 0이라면 0으로, 양수면 1, 음수면 -1로 변환 후 저장해 주어야 한다.이후 업데이트 시에도 value 값에 동일한 조건을 추가해 준다.마찬가지로 쿼리를 통해 반환받은 값을 0과 음수, 양수로 나누어 출력을 해준다. 참고 사항누적곱 세그먼트 트리 로직은 같다, 입력과 출력에 신경을 써주면 되는 문제  정답 코드#include #include using namespace std;int n, k;vector tree;vo..

리뷰세그먼트 트리를 활용하여 최소값을 구하는 문제 문제 풀이상세 내용은 https://zzzz955.tistory.com/180를 참고 바란다.위 링크 문제에서 index가 아닌 최소 값을 구하는 문제, 폼은 거의 일치하며 오히려 더 쉬운 문제다.  참고 사항없음  정답 코드#include #include using namespace std;int n, m;vector tree;void build(vector& lst, int node, int start, int end) { if (start == end) { tree[node] = lst[start]; } else { int mid = (start + end) / 2; build(lst, node * 2, start, mid); build(ls..

리뷰세그먼트 트리를 통한 최소값을 찾고, 해당 값의 index를 찾는 문제 문제 풀이n값을 입력받고 n개의 수를 1차 벡터에  입력 받는다, tree는 4 * n 사이즈로 초기화 해준 뒤 build를 진행한다.이때 tree는 vector> 타입으로 최솟값과 해당 index를 모두 저장할 수 있게 해준다.m개의 줄에 걸쳐 쿼리를 받아주고 각 첫번째 숫자에 따라 업데이트 및 출력을 해주면 된다.쿼리 함수를 실행할때도 리턴 형식을 pair로 해주고 출력 시엔 second + 1을 해주면 된다. 참고 사항 ios::sync_with_stdio(false); cin.tie(NULL); 이건 꼭 해주기 정답 코드#include #include using namespace std;int n, m;vector> tre..

리뷰일반적인 세그먼트 트리를 활용한 구간합 문제인 줄 알았으나 함정이 있었다. 문제 풀이n, q값을 받아오고 벡터에 n개의 수를 받아온 뒤 n * 4 크기의 트리로 build해 준다.q개의 질문을 받고 첫 두개의 수 a, b에 해당하는 구간합을 출력해 준다.이후 두번째 두개의 수 c - 1번째 노드의 수를 d로 업데이트 해준다.q가 종료될 때까지 해당 작업을 반복해 주면 된다. 참고 사항노트에 힌트가 나와있다."x~y는 당연히 x번째 부터 y번째가 맞다. 하지만, 이 문제에서는 x > y인 경우 y번째 부터 x번째이다."이 말은 a, b가 입력될때 b보다 a가 큰 경우가 있다는 말이다. 정답 코드#include #include #include using namespace std;int n, q;vecto..