반응형

알고리즘 공부/C++ 366

백준 10868번 최솟값 C++ 세그먼트 트리

리뷰세그먼트 트리를 활용해 구간 내 최솟값을 찾는 문제 문제 풀이n, m값을 입력 받고 정수형 벡터 nodes를 초기화 하고 정수형 벡터 tree를 4 * n크기로 초기화 한다.n개의 줄로 입력되는 정수를 nodes 벡터에 푸시 해주고 nodes를 바탕으로 tree를 build 해준다.update를 해주는 경우는 없으므로 query를 통해 b - 1 ~ c - 1범위를 탐색하여 최소값을 출력해 주면 된다. 참고 사항각각의 정수는 1,000,000,000 이하의 값을 가지므로 query 탐색 시 범위 조건에 맞지 않는 경우 1000000001를 리턴해 준다.  정답 코드#include #include #include using namespace std;int n, m;vector tree;void buil..

백준 11505번 구간 곱 구하기 C++ 세그먼트 트리

리뷰세그먼트 트리를 활용한 구간 곱 문제 문제 풀이세그먼트 트리 구간합 문제에서 query 실행 시 범위를 완전 벗어났을 때의 return값을 1로 바꿔준다.그리고 build, update, query 실행 시 tree[node]값이나 return값을 + 대신 *로 변경해 주면 된다.자세한 내용은 해당 링크를 참조 https://zzzz955.tistory.com/175 참고 사항곱셈의 결과를 1000000007로 나누어 줄때 내부의 값이 int 타입인 경우 오버플로우가 발생했다.(long long)을 써서 명시적으로 형변환을 시켜주거나 1LL을 곱해줘 자동 형변환이 필요하다.  정답 코드#include #include #include using namespace std;int n, m, k;vector..

백준 2042번 구간 합 구하기 C++ 세그먼트 트리

리뷰세그먼트 트리로 구간 합을 구하는 문제 문제 풀이n, m, k 값을 입력 받고 n개의 줄로 입력되는 값을 nodes 배열에 받아준다.트리를 4 * n크기로 초기화 하고 nodes 배열을 세그먼트 트리로 빌드해 준다.m + k를 합친 수만큼 반복문을 실행하고 a, b, c를 입력 받는다.만약 첫번째 수가 1이라면 b - 1인덱스의 노드 트리를 v 값으로 update 해준다.첫번째 수가 2라면 query 함수를 통해 b - 1 ~ c - 1 사이의 값을 출력해 준다. 참고 사항입력 값이 -2^63 ~ 2^63-1 범위 이므로 int가 아닌 long long 타입을 사용해 준다.  정답 코드#include #include #include using namespace std;int n, m, k;vector..

백준 14427번 수열과 쿼리 15 C++ 세그먼트 트리

리뷰세그먼트 트리를 공부하며 실습용으로 선택한 문제, 이제 슬슬 C++에서도 입출력을 신경 써줘야 할때가 온 것 같다. 문제 풀이배열의 크기와 배열을 받아와 주고 4 * n크기로 트리를 초기화 해준다. 받아온 배열로 세그먼트 트리를 최소값 형식으로 build 해준다.이후 m을 입력 받고 m크기 만큼 루프를 실행해 준다.order값이 2일 경우 최소값을 출력하는 query를 실행해 준다.order값이 1일 경우 트리의 i - 1번째 요소를 v로 바꿔준다. 참고 사항m이 최대 10만이므로 ios::sync_with_stdio(false); cin.tie(NULL);로 입력 속도를 최적화 해주니 통과하였다.인덱스도 사용해야 하니 세그먼트 트리를 pair 형식으로 초기화 하였다. 첫번째 정수는 노드 번호, 두번..

백준 16236번 아기 상어 C++ BFS

리뷰조건에 쉬워보였으나 굉장히 까다로웠던 문제, bfs함수 내에서 2중 while문과 sort를 통해 풀었다. 문제 풀이2차 배열 필드를 입력받고 만약 현재 입력값이 9라면 아기 상어 이므로 좌표를 저장해 준다.bfs를 시작하고 total_time을 0으로 초기화 한 후 while문을 항상 true인 상태로 개행해 준다.이후 일반적인 bfs와 동일하게 큐와 방문 배열(여기선 거리계산 역할까지 병행)을 초기화 하고 큐에 시작 위치를 담은 pos 구조체를 추가해 준 뒤 현재 위치의 거리를 0으로 초기화 해준다.잡아먹은 물고기 정보를 저장할 fishes 벡터를 초기화 해주고 최소 거리를 -1로 잡은 후 bfs를 실행해 준다.4방향 탐색을 하고 만약 거리가 -1(방문하지 않은)이면서 2차 배열의 값이 아기 상어..

백준 7562번 나이트의 이동 C++ BFS

리뷰나이트가 출발지로 부터 도착지까지 이동하는 최단거리는 구하는 문제 문제 풀이나이트가 이동할 수 있는 방향 배열을 만들어 주고, 현재의 위치와 이동 시간을 체크할 구조체를 만들어 준다.각 테케마다 출발지와 도착지를 입력 받고 bfs를 시작한다. 큐에 시작 위치를 추가하고 방문 체크용 2차배열을 만든다.while루프를 시작하고 현재 위치가 도착지라면 이동 시간을 리턴, 출력해 주면 된다. 참고 사항int dirx[] = { -1, -2, -2, -1, 1, 2, 2, 1};int diry[] = { -2, -1, 1, 2, 2, 1, -1, -2};방향 배열은 위와 같다. 정답 코드#include #include #include using namespace std;int tc, n, sx, sy, dx,..

백준 2589번 보물섬 C++ BFS, 브루트포스 알고리즘

리뷰진짜 아무리봐도 잘못된게 없는데 계속 틀려서 다시 보니 브루트포스를 돌리는 과정에서 n * m크기가 아닌 n * n크기로 돌리고 있었다... 근데 왜 97% 까지 맞는거야? 문제 풀이n 크기의 문자열을 받아와 준 뒤 n * m크기의 for문을 개행하고 현재 위치가 L일 경우 bfs를 시작한다.현재 위치와 이동 횟수 0을 큐에 넣어주고 방문 체크용 2차 배열을 0으로 초기화 하고 현 위치를 방문 체크해 준다.while루프를 돌려 4방향을 체크하고 갈 수 있는 공간이라면 방문 체크 및 이동 횟수를 1 올려 준 후 큐에 추가한다.이동 횟수가 변경 되었으므로 현재 이동 횟수가 최대 이동 횟수 보다 클 경우 갱신해 준다.for문이 종료된 후 최대 이동 횟수를 출력해 준다. 참고 사항반복문을 사용할땐 항상 범위..

백준 5214번 환승 C++ BFS

리뷰인접 리스트와 방문 배열 2개를 활용하여 해결한 문제 문제 풀이노드 배열을 n + 1 크기로, 하이퍼 튜브 배열을 m + 1배열로 초기화 해준다.m * k 크기의 for문을 개행하고, 입력값을 받을 때 하이퍼 튜브와 노드의 인접 리스트에 쌍방향으로 push 해준다.큐에는 도시(노드) 정보와 이동 횟수, 현재가 노드인지 하이퍼 튜브인지를 구별할 변수를 구조체로 넣어준다.BFS를 실행하고 현재가 하이퍼 튜브일 경우 방문 처리 및 튜브 안의 노드 인자를 큐에 추가해 준다. 이때 이동 횟수를 증가 시키고 노드 정보라는 표시를 해 준다.현재가 노드일 경우 방문 처리 및 연결된 하이퍼 튜브를 큐에 추가해 준다. 이번엔 이동 횟수를 증가 시키지 않는다. 마찬가지로 하이퍼 튜브라는 표시를 해 준다.큐에서 pop한 ..

백준 2536번 버스 갈아타기 C++ BFS

리뷰BFS로 문제를 풀었다. 굉장히 까다로웠던 문제 문제 풀이구조체 배열 busInfo를 k + 1개로 초기화 해준 후 각 버스 번호의 index에 버스 구조체를 넣어준다.이때 항상 x2가 x1보다 크고 y2가 y1보다 크다는 보장이 없기 때문에 큰 값을 x2, y2로 변환하여 넣어준다.버스 노선은 직선형 이기 때문에 x가 서로 같거나 y가 서로 같을 경우도 체크해 준 후 type 변수로 넣어준다.2차 배열 buslist를 k + 2 크기로 초기화 해준다, 각 버스 노선이 인접한 경우 쌍방향으로 index를 추가해 인접 리스트를 만들어 준다.시작점과 도착점 정보를 받아준 후 각각을 인접 리스트의 0번 index, k + 1번 index로 인접 리스트를 확장해 준다.0번 index부터 bfs를 시작해 준다..

백준 16928번 뱀과 사다리 게임 C++ BFS

리뷰쉬워보이나 판별조건을 잘 설정해 주어야 하는 문제 문제 풀이방문배열을 일반 방문배열, 사다리 방문배열, 뱀 방문배열 총 세개 만들어 준다. 사다리와 뱀의 위치를 index로 이동할 위치를 value로 입력 받아준다.1부터 bfs를 시작해 주고 현재 위치부터 1 ~ 6까지 for문을 돌려준다.도착 위치가 사다리라면 사다리를 타고 해당 위치로 이동 후 방문 배열에 추가해 준다.도착 위치가 뱀이라면 뱀을 타고 해당 위치로 이동 후 방문배열에 추가해 준다.둘 다 해당하지 않다면 주사위 위치로 이동 후 방문 배열에 추가해 준다.현재 위치가 100이라면 소요 시간을 출력해 준 후 리턴해 준다. 참고 사항사다리나 뱀이 이미 방문한 위치라면 continue를 해줘야 한다. 해당 부분땜에 시간이 좀 걸렸다.  정답 ..

728x90
반응형