알고리즘 문제풀이/백준134 [백준 5427] 불 www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net bfs 응용문제이다. "불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. " -> 불이 먼저 이동한다는 말이다. 불을 먼저 이동시킨다음에 상근이가 배열을 벗어날 수 있다면 탈출! #include #include #include using namespace std; int t, w, h; int src_x, src_y; char arr[1001][1001]; int person_visited[1001][100.. 2020. 12. 3. [백준 9466] 텀 프로젝트 www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net directed graph에서 cycle detection 응용문제이다. 사이클에 해당하지 않는 노드를 찾는 문제로 dfs를 사용하거나 indegree + 위상정렬을 사용한다. 1. dfs를 사용할 때 사이클이 있는지 확인할 때 지나간지 여부를 체크하는 배열 path와 확인이 끝났다는 표식인 done 배열 두 가지를 사용한다. 1부터 n까지 done이 아니라면 dfs에 들어가는데 dfs에 들어가서 방문 체크path를.. 2020. 12. 3. [백준 2493] 탑 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 스택을 사용하는 문제이다. 골5였지만 구현은 단순했다. 이전 문제와 마찬가지로 거꾸로 배열을 돌면서 현재값 스택의 탑이라면 pop을 한다. #include #include using namespace std; int n; int arr[500000]; int res[500000]; stack s; int main(void) { scanf("%d", &n); for (i.. 2020. 11. 30. [백준 6198] 옥상 정원 꾸미기 www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 스택을 사용하는 문제이다. 리트코드에서 유사한 문제를 풀어본 경험이 있어서 접근하기가 어렵지 않았지만... 처음 보면 당황할 꺼 같다. 배열 사이즈가 꽤 크기 때문에 모든 배열에 대해 자기자신보다 큰 수가 나올때까지 카운트한다면 시간 초과가 날 것이다. 스택을 이용하여 거꾸로 배열을 순회하며 o(n)에 끝내도록 한다. 1. 맨 마지막 배열 인덱스를 넣는다. 2. 배열 인덱스를 n-2부터 0까지 돌면서 a.. 2020. 11. 30. 이전 1 ··· 23 24 25 26 27 28 29 ··· 34 다음
