본문 바로가기

Algorithm197

[실전 알고리즘] DFS DFS? 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 예시 1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 4. 스택이 빌 때 까지 2번을 반복 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N). BFS vs DFS 거리 측정은 BFS만 할 수 있다. 출처 BaaaaaaaarkingDog | [실전 알고리즘] 0x0A강 - DFS (encrypted.gg) 2022. 9. 7.
[백준 1074] Z 1074번: Z (acmicpc.net) 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 배운 것 정답 풀이 // http://boj.kr/fd805e1226e949f9b6b2eff59e5be642 #include using namespace std; int func(int n, int r, int c){ if(n == 0) return 0; int half = 1= half && c < half) return 2*half*half + func(n-1, r-half, c); return 3*half*.. 2022. 9. 7.
[백준 1629] 곱셈 1629번: 곱셈 (acmicpc.net) 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 정답 코드 using namespace std; typedef long long ll; ll a, b, c; ll go(ll a, ll b) { cout b >> c; cout 2022. 9. 6.
[백준 6593] 상범 빌딩 (tuple 사용법) 6593번: 상범 빌딩 (acmicpc.net) 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 배운것 - 3차원이라고 쫄 것 없음. L(층) 하나만 추가해주면 되고 다 똑같음 - tuple 사용하기 tuple ti; int a, b, c; int main(){ ti = make_tuple(1, 2, 3); a = get(ti); b = get(ti); c = get(ti); cout c; if(l == 0 && r == 0 && c == 0) break; queue Q; char board[MX][MX][MX];.. 2022. 9. 6.
[백준 2468] 안전 영역 2468번: 안전 영역 (acmicpc.net) 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 배운 것, 생각해야 할 포인트 - 여러번 테스트할 때 ( limit이 계속 바뀔때) vis 배열 초기화해주기 - max함수 써서 cnt 리셋 정답 코드 // Authored by : std-freejia // Co-authored by : BaaaaaaaaaaarkingDog // http://boj.kr/4b36ea477ba8433c9cf9d053a711e07b #include #define X first #define.. 2022. 9. 6.
[백준 5014] 스타트링크 5014번: 스타트링크 (acmicpc.net) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 내 풀이 - 런타임에러남 #include using namespace std; int f, s, g, u, d; int dist[1000002]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> f >> s >> g >> u >> d; fill(dist + 1, dist + f + 1, -1); queue q; q.push(s); dist[s] = 1; int cnt.. 2022. 9. 4.

티스토리툴바