본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 2522 별 찍기 - 12 출처: https://www.acmicpc.net/problem/2522 Approach Input 3 Output * ** *** ** * ▶ 높이는 주어진 입력(N)에서 {2 × N - 1} 만큼 가진다. ▶ 각 줄을 {start...k} + {k...N} 구조로 구현 ▶ k는 N번째 줄까지는 -- 되고, N번째 줄 이후로는 ++ 된다. ▶ [문제] BOJ 별 찍기 시리즈 [문제] BOJ 별 찍기 시리즈 [BOJ] 2438 별 찍기 - 1 [BOJ] 2439 별 찍기 - 2 [BOJ] 2440 별 찍기 - 3 [BOJ] 2441 별 찍기 - 4 [BOJ] 2442 별 찍기 - 5 [BOJ] 2443 별 찍기 - 6 [BOJ] 2444 별 찍기 - 7 [BOJ] 2445 별 찍기 - 8 [BOJ] 24.. 2021. 4. 18.
[BOJ] 백준 2446 별 찍기 - 9 출처: https://www.acmicpc.net/problem/2446 Approach Input 5 Output ********* ******* ***** *** * *** ***** ******* ********* ▶ 높이는 주어진 입력(N)에서 {2 × N - 1} 만큼 가진다. ▶ 각 줄을 {start...left} + {left...right} + {right...end} 로 구성 ex) 2번째 줄 : {0...1} + {1...N-1} + {N-1...N} ▶ 높이 = N 이전까지는 left++, right-- 높이 = N 이후로는 left--, right++ ▶ 유사한 문제: [BOJ] 2445 별 찍기 - 8 [BOJ] 백준 2445 별 찍기 - 8 출처: https://www.acmic.. 2021. 4. 18.
[BOJ] 백준 2445 별 찍기 - 8 출처: https://www.acmicpc.net/problem/2445 Approach Input 5 Output * * ** ** *** *** **** **** ********** **** **** *** *** ** ** * * 모양을 세로로 출력하면 쉽게 풀 수 있지만 출력은 가로 방향이므로 이에 맞춰서 설계해야 한다. ▶ 높이는 주어진 입력(N)에서 {2 × N - 1} 만큼 가진다. ▶ 시작 위치(start)에서 left++되면서 start ~ left 까지 별(*) 출력 ▶ 우측(right) 위치까지는 공백 출력 (left ~ right 사이) ▶ right ~ 끝 위치(end)까지 별(*) 출력 높이 N까지는 right-- ▶ 높이가 N만큼 되었을 때, 아래와 같이 처리 left++ → .. 2021. 4. 18.
[BOJ] 백준 2556 별 찍기 - 14 출처: https://www.acmicpc.net/problem/2556 Approach Input 1 Output * 문제 설명에서는 N = 1 인 경우만 주어지기 때문에 N = 2, 3, 4일 때 어떻게 출력되지는지 알 수 없는 어려움이 있다. ▶ 높이는 주어진 입력(N) 만큼 가진다. ▶ N × N 크기의 사격형 모양의 별(*)을 구성한다. Input 2 Output ** ** Input 3 Output *** *** *** Input 4 Output **** **** **** **** ▶ [문제] BOJ 별 찍기 시리즈 [문제] BOJ 별 찍기 시리즈 [BOJ] 2438 별 찍기 - 1 [BOJ] 2439 별 찍기 - 2 [BOJ] 2440 별 찍기 - 3 [BOJ] 2441 별 찍기 - 4 [B.. 2021. 4. 18.
[BOJ] 백준 2439 별 찍기 - 2 출처: https://www.acmicpc.net/problem/2439 Approach [BOJ] 2438 별 찍기 - 1 문제와 달리 앞쪽에 공백이 위치하며, 별(*)은 우측에 위치한다. 입력받은 수치(n)만큼 높이를 가지되, 아래와 같이 해서 출력 ▶ 공백 개수-- ▶ 별(*) 개수++ ※ [문제] BOJ 별 찍기 시리즈 [문제] BOJ 별 찍기 시리즈 [BOJ] 2438 별 찍기 - 1 [BOJ] 2439 별 찍기 - 2 [BOJ] 2440 별 찍기 - 3 [BOJ] 2441 별 찍기 - 4 [BOJ] 2442 별 찍기 - 5 [BOJ] 2443 별 찍기 - 6 [BOJ] 2444 별 찍기 - 7 [BOJ] 2445 별 찍기 - 8 [BOJ] 2446 별.. zoosso.tistory.com #i.. 2021. 4. 18.
[BOJ] 백준 2438 별 찍기 - 1 출처: https://www.acmicpc.net/problem/2438 Approach 줄 (row)이 증가함에 따라서 별의 개수가 증가한다. 이중 for문을 이용해서 간단하게 구현할 수 있는 문제 ▶ [문제] BOJ 별 찍기 시리즈 [문제] BOJ 별 찍기 시리즈 [BOJ] 2438 별 찍기 - 1 [BOJ] 2439 별 찍기 - 2 [BOJ] 2440 별 찍기 - 3 [BOJ] 2441 별 찍기 - 4 [BOJ] 2442 별 찍기 - 5 [BOJ] 2443 별 찍기 - 6 [BOJ] 2444 별 찍기 - 7 [BOJ] 2445 별 찍기 - 8 [BOJ] 2446 별.. zoosso.tistory.com Input 5 Output * ** *** **** ***** #include using name.. 2021. 4. 17.
[BOJ] 백준 2660 회장뽑기 출처: https://www.acmicpc.net/problem/2660 Approach 플로이드 와샬 (Floyd Warshall)을 이용할 수 있다. 플로이드 와샬 (Floyd Warshall) 개념 아래와 같은 가중 그래프에서 최단 경로를 찾는 알고리즘. ex) 정점 ③ → ⑤로 가는 최단 경로는 다음과 같습니다. 경로Path: ③ → ② → ④ → ① → ⑤ 비용Cost: +4 +1 +2 -4 = 3.. zoosso.tistory.com #include const int MAX_N = 55; int N, s, e, ans = MAX_N; int dist[MAX_N][MAX_N], score[MAX_N]; int arr[MAX_N], acnt; void input() { scanf("%d", &N).. 2021. 4. 3.
[BOJ] 백준 2463 비용 출처: https://www.acmicpc.net/problem/2463 Approach Disjoint-Set & Union-Find Disjoint-Set & Union-Find Disjoint-Set, 상호 배타적 집합 서로 중복되지 않는 부분 집합들을 의미 (교집합 존재 X) Union-Find Disjoint-Set을 표현할 때 사용하는 알고리즘. ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 zoosso.tistory.com #include typedef long long LL; const int MOD = (int)1e9; const int LM = 100005; int N, M; int group[LM]; int urr[LM], vrr[LM]; LL sum, ans, cnt[.. 2021. 4. 3.
[BOJ] 백준 2529 부등호 출처: https://www.acmicpc.net/problem/2529 Approach DFS (depth-first search, 깊이 우선 탐색) 깊이 우선 탐색(depth-first search, DFS) DFS 그래프의 모든 정점을 방문할 때 최대한 깊숙히 정점을 방문하는 방식입니다. - Stack 이용 즉, 연결된 정점을 따라 계속 순회하다가 갈 곳이 없어지며 바로 이전단계로 가는 백트래킹 방식. zoosso.tistory.com DFS와 BFS 비교 DFS와 BFS 비교 출처: 나무위키 경로 비교 BFS - Queue 이용 - 최소신장트리(Minimum Spanning Trees), 최단경로(Shortest Paths) 장점: 무한히 깊거나 무한에 가까운 트리인 경우에 효과적 단점: 목표 노.. 2021. 4. 1.
[BOJ] 백준 2665 미로만들기 출처: https://www.acmicpc.net/problem/2665 Approach BFS 혹은 DFS 이용해서 해결할 수 있다. BFS (Breadth-First Search, 너비 우선 탐색) BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서 zoosso.tistory.com DFS (depth-first search, 깊이 우선 탐색) 깊이 우선 탐색(depth-first search, DFS) DFS 그래프의 모든 정점을 방문할 때 최대한 깊숙히 정점을 방문하는 방.. 2021. 3. 31.
반응형

티스토리툴바