개인사

리뷰 https://www.acmicpc.net/problem/1167간선의 가중치가 있는 트리에서 두 노드의 거리가 가장 큰 길이를 구하는 문제 전역 변수n : 노드의 개수를 저장할 정수형 변수far_node : 첫 번째 dfs를 수행했을 때 가장 먼 거리를 가진 노드의 번호를 저장할 정수형 변수max_dist : 각 dfs마다 가장 먼 거리를 식별하기 위한 정수형 변수v : 깊이 우선 탐색을 할때 방문 처리를 확인하기 위한 정수형 배열, 크기는 100001로 초기화 한다.Edge : 노드의 자식과 간선의 가중치를 저장하기 위한 구조체edges : 각 노드의 인접리스트를 저장하기 위한 Edge타입 벡터, 크기는 100001로 초기화 한다. 함수1. dfsvoid dfs(int node, int dist..

리뷰 3 * 3 도형을 반전시켜 모든 땅을 흰색으로 만드는 문제https://www.acmicpc.net/problem/10472 전역 변수tc, target : 테스트케이스의 개수tc, 각 테케마다 초기 도형의 비트 정보targetlst : 초기 맵 상태를 얻어올 문자열 배열, 3 * 3크기이므로 크기는 3이다.dx, dy : 비트 반전을 시킬 구간의 방향 배열, 상하좌우 및 제자리를 포함하여 총 5개이다.v : 비트마스킹 시 방문 여부를 저장할 배열 9개의 상태를 저장해야 하므로 2^9보다 크게 설정한다.Pos : 큐 내부에서 현재 비트정보와 변환 횟수를 저장하여 사용할 구조체 함수1. getTargetvoid getTarget() 테스트케이스에서 입력된 도형의 비트 정보를 target변수에 저장하기..

리뷰 max이 하나가 정답을 좌지우지 했다 ㅠㅜhttps://www.acmicpc.net/problem/2056 전역 변수n : 작업의 개수 함수없음  문제풀이n값을 입력 받고 작업 시간 정보 times와 인접 리스트를 초기화할 정수 벡터 path를 n + 1크기로 초기화 한다.1부터 n개의 각각의 작업에 걸리는 시간을 times 벡터에 저장해 준다.이후 선행이 필요한 작업을 인접 리스트로 추가해 준다, 역방향으로 삽입해 주어야 한다.선행 작업의 개수를 저장할 벡터 cnt를 n + 1크기, 기본값은 0인 상태로 초기화 해준다.각 작업을 순회하며 작업의 인접리스트에 저장된 작업을의 cnt를 증가시켜준다.정수형 큐 q를 초기화 한 후에 cnt가 0인 작업을 큐에 넣어준다.정답을 저장할 정수형 벡터 ans를 ..

리뷰 2차원 다익스트라의 기본적인 문제https://www.acmicpc.net/problem/4485 전역 변수n : 각 테스트 케이스마다 주어지는 맵의 한 변의 길이lst : 각 테스트 케이스마다 주어지는 맵 정보를 저장할 2차원 정수 배열, 최대크기는 125*125다.dx, dy : 상하좌우 4방향을 탐색하기 위한 방향 배열Pos : 우선순위 큐에서 현재 위치 정보를 나타낼 구조체, w를 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() 다익스트라를 통해 출발지에서 도착지까지의 최단 거리를 구하는 함수Pos타입 우선순위 큐 pq를 초기화 하고 거기에 시작 지점 x, y좌표와 시작 지점의 값을 넣어준다.n * n크기의 2차원 정수형 벡터 dist를 기본값을 매우 크게 지정..

리뷰 플로이드 와샬을 사용해 풀 수 있는 기초적인 문제https://www.acmicpc.net/problem/11403 전역 변수n : 인접 행렬의 한 변의 길이(노드의 개수) 함수없음  문제풀이n값을 입력 받고 거리를 저장할 2차원 정수 벡터 dist를 n * n크기로 초기화 한다.dist에 인접 행렬을 입력 받아준다, 이때 0이 입력 되었다면 1보다 큰 적절한 수로 변환해 준다.플로이드 와샬을 통해 3중  for문을 통해 갈 수 있으면서 1보다 큰 간선을 찾아 1로 변경해 준다.모든 작업을 마친 후 dist벡터 정보를 출력해 준다, 이때 1보다 큰 수라면 0으로 변환해서 출력해 주면 된다. 참고 사항정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 ..

리뷰 노드의 개수가 적을 경우 고려할 수 있는 최단 경로를 구하는 방법인 플로이드 와샬을 사용하는 문제https://www.acmicpc.net/problem/11404 전역 변수MAX_D : 거리의 최대값 보다 크게 설정해줄 정수형 상수 변수, 10만 * 10만 이상으로 초기화 해주면 된다.n, m : 노드의 개수 n, 간선의 개수 mlst : 인접 리스트를 행렬으로 변환할 정수형 2차 배열, 행, 열을 노드의 최대 개수인 100보다 크게 설정해 준다.path : 인접 리스트를 저장할 벡터, 다음 노드, 간선 두개를 모두 저장해야 한다.dist : 특정 노드끼리의 거리를 저장할 정수형 2차 벡터 함수1. inputvoid input() 노드와 간선의 개수를 입력 받고 인접리스트와 인접 행렬을 초기화 해..

리뷰 각 단계별 맵과 현재 위치를 고려하여 목표 위치까지 이동할 수 있는지를 구하는 문제https://www.acmicpc.net/problem/16954 전역 변수lst : 초기 맵 정보를 저장할 문자열 벡터, 크기는 8로 설정한다.ans : 정답 정보를 저장할 정수형 변수v : 각 단계별 현재 위치에 대한 방문 정보를 저장할 3차원 정수형 배열, 8 * 8 * 8크기로 설정한다.dx, dy : 상하좌우, 대각선, 제자리를 고려한 방향배열Pos : 현재 위치를 나타낼 구조체 함수1. movingvoid moving(vector& map) 현재 맵에 존재하는 벽들을 모두 한칸씩 내려주는 시뮬레이션을 진행한다.맵의 아래서 부터 swap을 통해 각 행을 변경해 주고, 마지막에 0번행을 빈 칸으로 세팅해 준다..

리뷰 간단한 다익스트라를 통한 시작점 > 도착점으로 가는 최단 경로를 구하는 문제https://www.acmicpc.net/problem/5972 전역 변수n, m : 노드의 개수를 저장할 정수형 변수 n, 간선 개수를 저장할 정수형 변수 mPos : 간선 정보를 저장할 구조체, 다음 노드와 가중치가 저장되며, 우선순위 큐의 compare 함수를 정의했다.path : 각 노드의 인접리스트를 저장할 Pos타입 2차원 벡터 함수1. dijkstraint dijkstra(int start, int end) start에서 end까지의 최단 경로를 구하는 함수Pos타입 우선순위 큐 pq에 start를 삽입하고 end까지 가는길의 최단경로를 dist벡터에 최신화 해준다.pq가 빌때까지 while루프를 통해 위 작업..

리뷰 각 순위별 간선을 생성하고, 쿼리로 입력되는 노드간 간선을 반전시킨 후 위상 정렬을 수행하는 문제https://www.acmicpc.net/problem/3665 전역 변수tc, n, m : 테스트 케이스의 개수 tc, 팀의 개수 n, 순위 변경 쿼리의 개수 mlst : 작년 순위 정보를 저장할 정수형 벡터cnt : 선순위의 개수를 저장할 정수형 벡터result : 금년 순위 정보를 저장할 정수형 벡터path : 인접 리스트를 저장할 정수형 2차원 벡터 함수1. initvoid init() 각 테스트 케이스마다 lst, cnt, result, path 벡터를 clear해주는 함수 2. input()void input() n값을 입력 받고 각 테스트 케이스 마다 lst, cnt, path의 크기를 n..

리뷰 다른 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까지 행성 정..