[Algorithm] 트리에서 BFS, DFS

개요보통 그래프 순회를 위해서 BFS, DFS를 활용한다.그래프의 일종인 트리도 BFS와 DFS로 순회를 할 수 있는데 방문했는지의 여부를 vis 배열로 확인하지 않고 방문할 노드가 부모노드인지만 확인하면 된다.기존 BFS기존 BPS의 경우 방문했는지의 여부를 알기 위해 vis 배열을 사용한다.int board[502][502];bool vis[502][502];그리고 방문할 때마다 vis가 true인지 확인한다. queue> Q; vis[0][0] = 1; Q.push({ 0, 0 }); int area = 0; while (!Q.empty()) { //탐색마다의 행동 area++; pair cur = Q.front(); Q.pop(); for (int dir = 0..

  • format_list_bulleted Algorithm
  • · 2025. 4. 2.
  • textsms

[Algorithm] 다익스트라

다익스트라그래프에서 한 정점에서 다른 모든 정점 까지의 최단 거리를 구할 수 있는 알고리즘이다.시간복잡도는 ElogE or ElogV자료구조다익스트라 알고리즘에서 저장해야하는 정보는 다음과 같다.노드별 최소 비용을 저장할 배열간선의 노드 연결과 비용을 저장할  vector 배열경로 탐색을 위해 prev 배열여기서 adj에는 adj[시작노드] = {비용, 끝노드} 형태로 정보를 저장한다.비용이 key인 이유는 비용을 기준으로 priority_queue에 넣기 위해서...!int d[1005];vector> adj[1005];int pre[1005];이때 최소 비용 배열 d는 INF 값으로 초기화 해줘야한다.int INF = 0x3f3f3f3f;fill(d, d+n+1, INF);구현다익스트라 알고리즘은 시..

  • format_list_bulleted Algorithm
  • · 2025. 4. 1.
  • textsms
[Algorithm] 이진수로 변경 & 산모양 출력

[Algorithm] 이진수로 변경 & 산모양 출력

문제110 진수를 입력으로 받아 이진수로 변경하는 프로그램을 작성하시오.입력입력으로 1000 이하의 자연수가 주어진다. 출력이진수로 변환된 자연수풀이이진수로 변환은 2로 계속나누다가 몫이 1이거나 없을때 지금까지 나온 나머지를 역순으로 출력하면 된다,11 % 2 = 111 / 2 = 5---5 % 2 = 15 / 2 = 2---2 % 2 = 02 / 2 = 1---1---1011따라서 점화식을 k의 2진수 출력인 print(k)로 정한다.print(k) = print(k/2) (+) cout void print(int n){ if (n > 1) print(n / 2); cout > n; print(n);}문제2봉우리가 여러개인 산 모양을 출력한다. 산 모양은 그림과 같고 좌우 대칭이다.출력 예시를 ..

  • format_list_bulleted Algorithm
  • · 2025. 3. 15.
  • textsms

[Algorithm] 백준 2579 - 계단 오르기

문제https://www.acmicpc.net/problem/2579 풀이DP로 문제를 풀면 된다.DP로 풀기 위해 점화식을 먼저 찾아야하는데 Step(int k)는 k번째 계단에서 최대 점수라 하자.계단을 오르는 규칙은 다음과 같다.한 번에 하나의 계단 or 두개의 계단을 오를 수 있음연속된 3개의 계단을 밟아서는 안됨이를 바탕으로 k번째 계단을 밟는 경우의 수를 생각해보면하나의 계단을 연속으로 밟는 경우건너뛰기로 밟는 경우1번의 경우 건너뛰기->하나 밟기 -> 마지막 밟기가 되며 연속된 계단을 2개까지 밟으므로 규칙을 준수한다.2번은 건너뛰기->마지막 밟기가 된다.!! 건너뛰기->밟기->밟기->마지막 밟기는 연속 3번이므로 성립 X 위의 결과를 바탕으로 점화식을 작성하면 2가지 경우의 수 중 최대인 ..

  • format_list_bulleted Algorithm
  • · 2025. 3. 14.
  • textsms

[STL] STL && STL 관련 함수 정리

https://dongg.notion.site/STL-19e20ce5e92480d3afdde3420ce72e2b?pvs=4 STL 정리 | Notion목차dongg.notion.site

  • format_list_bulleted C++
  • · 2025. 2. 19.
  • textsms
[Algorithm] 옥상 정원 꾸미기 (백준 6198)

[Algorithm] 옥상 정원 꾸미기 (백준 6198)

문제https://www.acmicpc.net/problem/6198풀이처음 풀이vector의 빌딩들의 높이를 차례대로 할당한 후 빌딩별로 자신보다 높거나 같은 빌딩이 나올때까지의 빌딩 수를 count하는 방식으로 풀었다.이 방법은 이중 for문을 사용해서 시간복잡도는 O(N^2)이다.하지만 시간복잡도를 O(N)으로 줄이는 방법이 있다는데.....#include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); int n; long long ans = 0; cin >> n; vector h(n, 0); for (int i = 0; i > h[i]; for (int i = 0; i monotonic st..

  • format_list_bulleted Algorithm
  • · 2024. 12. 29.
  • textsms