개인사

리뷰 그래프의 정보가 주어지고 두 노드간의 거리를 구하는 문제, 루트 노드가 1이 고정이 아니여서 직접 구해주어야 한다.LCA는 개념만 잘 잡는다면 응용 문제에 적용하는 방법이 어렵지 않은 것 같다.https://www.acmicpc.net/problem/1761 문제 풀이main 함수에 init, ds, pre_process, query 네개의 함수를 순차적으로 실행시켜 문제를 풀었다.init 함수에서 n값을 받고 n - 1개의 간선 정보를 tree 벡터 배열에 저장한 뒤 Union 작업을 수행해 준다.1부터 n까지의 노드를 탐색 한 후 자기 자신을 value로 갖는 노드를 찾아 root로 저장한다.root 부터 dfs 함수를 통해 각 노드의 깊이와, 루트 노드로 부터의 거리, 자기 자신의 바로 윗 조..

리뷰 0, 1 좌표에서 파이프를 옮겨 n - 1, n - 1 좌표까지 이동 가능한 모든 경로를 구하는 문제 문제 풀이전역 변수로 변의 크기 n, 정답용 변수 ans, 맵을 나타낼 lst 배열, 방문 처리를 나타낼 v 배열, 방향 배열을 초기화 한다.n값을 입력 받고 ans를 0으로 초기화 한 뒤에 n * n크기의 맵을 lst에 초기화 해준다.0, 0과 0, 1을 방문 처리해 주고 0, 1 좌표 및 방향 배열 인덱스는 0 (오른쪽)으로 dfs를 시작해 준다.dfs의 매개변수로는 현재 좌표 x, y값과 방향 위치인 dir을 받는다.기저 조건으로 x, y 좌표가 n - 1일때 ans를 증가시키고 리턴을 해준다.현재 방향 인덱스에 -1 ~ 1범위로 더해주고 만약 인덱스 범위를 벗어난다면 continue 처리를 ..

리뷰 치열한 전투의 흔적이 보이십니까?LCA의 기본기가 있다면 쉽게 풀 수 있을 거라 생각했는데, 문제가 친절하지 않아 고생한 문제https://www.acmicpc.net/problem/13511 문제 풀이input 함수에서 n값을 받고, 각 노드간의 간선 n - 1개를 입력 받는다.solution함수에서 dfs 함수와 pre_process 함수를 돌려주어 각 노드의 부모, 깊이, 비용값을 구해주었다.dfs 함수에서는 각 함수의 깊이 및 루트 노드로부터의 비용, 자신의 바로 위 부모를 구해 각 배열에 저장해줬다.pre_process 함수에서는 각 노드의 2^i 번째 상위 부모를 찾아 부모 배열을 마저 초기화 해주었다.query 함수에서 m값을 받고, 입력된 m개의 쿼리를 처리해 주었다.쿼리의 인덱스가 ..

리뷰 LCA 문제의 상위 호환버전, 노드의 개수가 2배로 많아졌고, 쿼리의 개수도 증가하였다.시간을 좀 아껴보려고 LOG의 크기를 줄여주었더니 OutofBounds 에러가 출력되었다, LOG값을 높혀주니 AChttps://www.acmicpc.net/problem/11438 문제 풀이n값을 입력 받고, n - 1개의 간선을 tree 벡터 배열에 양방향 간선으로 저장해 준다.루트 노드는 항상 1이기에 1부터 dfs 함수를 통해 모든 노드에 자기 자신의 깊이와 바로 윗 조상을 초기화 해준다.pre_process 함수를 통해 각 노드에 변수 LOG의 값 즉 2^20개의 부모 노드를 탐색하여 저장해 준다. (메모제이션)m개의 쿼리를 받고, 각 쿼리마다 두 노드의 최소 공통 조상을 lca 함수를 통해 찾아준 뒤 ..

리뷰  문제 풀이테스트 케이스를 입력 받고, 해당 테스트 케이스 만큼 while문을 돌려준다.각 테스트 케이스 마다 n, root, tree, parent정보를 초기화 해준다.유니온 파인드용 노드 배열을 노드의 1 ~ n 노드까지 자기 자신을 값으로 갖게끔 인덱스를 설정해 준다.이후 n - 1개의 간선을 입력 받고, tree벡터 배열에 양방향 간선으로 추가, b를 a의 자식으로 유니온 해준다.1부터 n까지 노드를 탐색해 자기 자신을 value로 갖고있는 노드를 찾고 root로 할당해 준다.dfs함수를를 root 부터 돌려 각 자신의 바로 위 부모를 구해준다.preprocess 함수를 통해 그 위의 부모들까지 초기화를 해준다.비교할 노드 두개를 입력 받고 lca 함수의 매개변수로 전달해준 뒤 리턴값을 출력..

리뷰새로운 알고리즘인 LCA를 배우게 되었다, 로직이 매우 복잡했지만 세그먼트 트리처럼 외워서 쓴다면 괜찮을 것 같다. 문제 풀이nodes를 최대 노드의 개수로, LOG를 최대 노드의 개수를 log2를 취한 수보다 크게 설정해 준다.tree벡터 배열에 인접 리스트를 저장하고, depth에 각 노드의 깊이, parent에 각 노드의 부모 정보를 저장한다.dfs 함수를 통해 인접리스트를 사용하여 자신의 바로 윗 부모와 depth를 알 수 있다.process 함수를 통해 모든 노드의 조상에 대해 탐색이 가능하다, 조상이 없을 경우 -1m개의 쿼리문을 받아와 u와 v의 최소 공통 부모를 lca 함수를 통해 구해준 후 출력해 준다. 참고 사항자세한 내용은 정답 코드의 주석 참고  정답 코드#include#incl..

리뷰쉬운 구현, 시뮬레이션 문제였다, 접목할 알고리즘은 딱히 없는듯 문제 풀이각 테스트 케이스마다 ans를 0으로 초기화 해주고, 한변의 길이 n과 경사로의 길이 x, 2차원 맵 정보를 입력 받아준다.각 행의 0번째 열부터 n - 1번째 열까지 탐색을 돌리고, 각 열의 0번째 행부터 n - 1번째 행까지 탐색을 돌려준다.맵의 범위를 벗어날 때 까지 각 행과 열을 증가시키며 탐색을 한다.만약 현재보다 2이상 큰 땅을 만난다면 더이상 탐색할 필요가 없이 return 해주면 된다.만약 더 높은 땅을 만난 경우 현재 위치로부터 x - 1 이전의 땅에 경사로를 설치할 수 있는지 체크해 준다.설치가 가능하다면 현재 높이를 높여주고, 뒤쪽의 땅에 경사로 설치를 하고 한칸 올라왔다는 표시를 해준다.더 낮은 땅을 만난 ..

리뷰재귀의 깊이와 맵의 크기가 그리 크지 않아 완전 탐색으로 쉽게 구현이 가능할 줄 알았는데, 생각보다 신경써 주어야 할 것이 많았다... 어렵네 ㅜㅠ 통과한 코드도 시간이 아슬아슬 한 걸 보니 최적화가 더 필요해 보인다...  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 풀이테스트 케이스 tc를 입력 받고 각 테케마다 for문을 돌려주어 init, input, solution 함수를 실행하고 정답 ans를 출력했다.1. init()ans값을 10억으로 초기화 해주고, 방문 배열 v를 0으로 초기화 해주었다.2.input()n, w, h값을 입력 받아주고 h * w크기의 맵에 벽돌 정보를 받아주었다.3.s..

리뷰 SWEA를 풀면서 처음으로 만난 덱을 써서 푸는 문제 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 풀이tc를 입력 받고 각 테스트 케이스를 개행한다, 이후 init, input, solution 함수를 실행하고 각 테케마다 ans를 출력해줬다.1. init()ans를 0으로 초기화 해주고 각 자석 정보를 clear를 통해 초기화 해준다.2. input()k값을 받아와 주고, 4개의 자석에 각각 N극과 S극 정보를 받아와 준다.3. solution()k번을 순회하며 회전시킬 자석과 방향정보를 입력 받고 각 자석을 돌려준다.자석을 돌리기 전에 방문배열 초기화와 회전시킬 자석의 방문처리가 필요하다.4.bt..

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