개인사

리뷰 https://www.acmicpc.net/problem/17400홀수 및 짝수 세그먼트 트리 2개를 사용해 푼 문제, 충분히 더 최적화 할 수 있는 방법이 있어 보인다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 배열의 크기를 저장할 변수q : 쿼리의 개수를 저장할 변수odd : 배열의 홀수 부분을 저장할 배열even : 배열의 짝수 부분을 저장할 배열to : 홀수 배열의 세그먼트 트리 정보를 저장할 배열te : 짝수 배열의 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) { if (s % 2) to[node] = odd[s]; else te[node] = even[s]; } else ..

리뷰 https://www.acmicpc.net/problem/9463두 배열간 같은 수끼리 간선을 이을때 겹치는 간선의 개수를 구하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수t : 테스트 케이스의 개수를 저장할 변수n : 배열의 크기를 저장할 변수lst1, lst2 : 두 배열의 요소 순서를 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열 함수1. updatevoid update(int node, int s, int e, int idx) { if (s == e) tree[node]++; else { int mid = (s + e) / 2; if (idx 세그먼트 트리의 업데이트를 진행할 함수 2. queryint query(int node, int s, int e, i..

리뷰 https://www.acmicpc.net/problem/16397골드 4보단 실버 1정도가 어울리는 문제인 것 같다. 전역 변수n : 십진수의 초기값을 저장할 변수t : 버튼을 누를 수 있는 최대 수를 저장할 변수g : 십진수의 목표값을 저장할 변수v : 방문 정보를 저장할 배열Cur : 현재 숫자와 누적 버튼 클릭 횟수를 정의할 구조체 함수1. bfsint bfs() { queue q; q.push({ n, 0 }); v[n] = true; while (!q.empty()) { Cur cur = q.front(); q.pop(); int p = cur.x, ct = cur.y; if (ct > t) continue; if (p == g) return ct; //cout = 1e5) c..

리뷰 https://www.acmicpc.net/problem/22352백신을 한번 투여하여 놓기 전의 상태가 놓은 후의 상태가 될 수 있는지를 판단하는 문제 전역 변수n, m : 맵의 세로/가로 길이를 저장할 변수lst1, lst2 : 백신을 놓기 전/후의 상태를 저장할 2차원 배열v : 플러드 필 도중 방문 여부를 체크하기 위한 2차원 배열dx, dy : 4방향 탐색을 위한 방향 배열Pos : 현재 위치 정보를 정의하기 위한 구조체 함수1. bfsvoid bfs(int sx, int sy, int c, int g) { queue q; q.push({ sx, sy }); lst1[sx][sy] = g; v[sx][sy] = true; while (!q.empty()) { Pos pos = q.fro..

리뷰 https://www.acmicpc.net/problem/16973맵에서 직사각형을 움직이며 목적지 까지 이동이 가능한지를 구하는 문제 전역 변수n, m : 맵의 세로/가로 크기를 저장할 변수lst : 맵 정보를 입력 받고 저장할 2차원 배열v : 방문 정부를 체크하기 위한 2차원 배열h, w : 직사각형의 세로/가로 크기를 저장할 변수dx, dy : 4방향 탐색을 위한 방향 배열Pos : 현재 위치와 누적 소요시간을 정의할 구조체 함수1. bfsint bfs(int sx, int sy, int ex, int ey) { queue q; q.push({ sx, sy, 0 }); v[sx][sy] = true; while (!q.empty()) { Pos pos = q.front(); q.pop()..

리뷰 https://www.acmicpc.net/problem/143954가지 연산을 통해 초기 숫자 s를 t로 만들 수 있는 방법을 찾는 문제 전역 변수s, t : 초기 정수와 목표 정수를 저장할 변수v : 방문 여부를 체크할 해시 셋 함수1. bfsstring bfs() { queue q; q.push({ s * s, "*" }); v.insert(s * s); q.push({ s * 2, "+" }); v.insert(s * 2); q.push({ 0, "-" }); v.insert(0); q.push({ 1, "/" }); v.insert(1); while (!q.empty()) { P p = q.front(); q.pop(); ll c = p.v; string s = p.s; if (c..

리뷰 https://www.acmicpc.net/problem/11909흠.. 골드5 수준의 문제는 아닌 것 같기는 하다. 다익스트라만 써도 풀리긴 하는데 시간이 아슬아슬했다. 전역 변수N : 배열의 한 변의 최대값을 정의할 상수 변수n : 배열의 한 변의 길이를 저장할 변수lst : 배열의 값을 입력 받기위한 2차원 배열dx, dy : 2방향 탐색을 위한 방향 배열Pos : 현재 위치, 누적 비용, 현재 높이를 정의할 구조체, 누적 비용을 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() { priority_queue pq; pq.push({ 0, 0, 0, lst[0][0] }); vector> dist(n, vector(n, 2e9)); dist[0][0] = 0; w..

리뷰 https://www.acmicpc.net/problem/15971로봇 두개가 만나 통신하기까지 이동한 거리의 합이 최소를 만들기 위한 문제 전역 변수N : 노드 관련 배열의 최대 크기를 정의할 상수 변수n : 노드의 개수를 저장할 변수r1, r2 : 로봇 1, 2가 위치한 노드 번호를 저장할 변수v : 방문 여부를 체크할 배열Edge : 간선 정보를 정의할 구조체edges : 간선 정보를 저장할 Edge타입 벡터 배열Pos : 현재 위치, 누적 이동 거리, 최대 간선 길이를 정의할 구조체 함수1. bfsint bfs() { queue q; q.push({ r1, 0, 0 }); v[r1] = true; while (!q.empty()) { Pos pos = q.front(); q.pop(); ..

리뷰 https://www.acmicpc.net/problem/13265DFS로 풀이하려고 했는데... 그냥 BFS로 했다, DFS를 다시 좀 연습해야겠는데 전역 변수N : 동그라미 관련 배열의 최대 크기를 정의할 상수 변수t : 테스트 케이스의 개수를 저장할 변수n : 동그라미의 개수를 저장할 변수m : 직선의 개수를 저장할 변수edges : 간선 정보를 인접리스트로 저장할 벡터 배열colors : 각 노드의 색을 저장할 배열 함수1. bfsbool bfs(int snode) { queue q; q.push({ snode, 0 }); colors[snode] = 0; while (!q.empty()) { pii cur = q.front(); q.pop(); int cn = cur.first, cc..

리뷰 https://www.acmicpc.net/problem/23563루시우가 되어 출발지부터 목적지까지의 이동하는 최단 시간을 구하는 문제 전역 변수n, m : 맵의 세로/가로 길이를 저장할 변수sx, sy, ex, ey : 출발 및 도착지의 좌표를 저장할 변수dx, dy : 4방향 탐색을 위한 방향 배열lst : 맵 정보를 정수로 파싱하여 저장할 2차원 배열Pos : 현재 위치와 누적 소요시간을 정의할 구조체, 누적 소요시간을 기준으로 오름차순 정렬한다. 함수1. dijkstraint dijkstra() { priority_queue pq; pq.push({ sx, sy, 0 }); vector> dist(n, vector(m, 2e9)); dist[sx][sy] = 0; while (!pq.em..