목록알고리즘 문제 풀이/BOJ (77)

영벨롭 개발 일지

[백준 BOJ][C++]2805번 나무 자르기 풀이: 이진 탐색

https://www.acmicpc.net/problem/2805 풀이 이 문제는 이진 탐색 알고리즘을 사용하여 해결할 수 있습니다. 시작 수 s = 0, e = 배열의 가장 큰 원소의 값으로 지정 mid = (s+e)/2 는 절단기의 높이, sum = 절단기의 높이 보다 큰 나무에 대해 잘린 나무의 길이의 총합 계산 sum과 가져가려고 하는 나무의 길이 m 비교 sum과 m이 같다면 현재 mid가 절단기의 높이의 최댓값이므로 break sum이 m보다 크다면 절단기의 높이 ans를 갱신, s = mid + 1 sum이 m보다 작다면 e = mid -1 s > n >> m; for (int i = 0; i > x; tree.push_back(x); if (e <..
알고리즘 문제 풀이/BOJ 2022. 5. 4. 15:49
[백준 BOJ][C++]16940번 BFS 스페셜 저지 풀이: BFS

https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 처음 풀이에선, 입력으로 주어진 순서에 따라 해당 노드에서 연결된 노드들 중 현재 순서인 노드를 찾는 반복문을 돌렸더니 시간초과가 떴습니다 ㅠ 시간초과를 해결하기 위해선 그래프 내의 연결된 노드들을 순서에 맞게 정렬 후, bfs를 실행해야 하는 것을 발견했습니다. [변수 설명] 1. vector graph[MAX] : 그래프 정보, graph[u] = 노드 u에 연결된 노드들 2. order[MAX]: 각 노드의 순서, order[x] = 노드 x의 순서 3. visit[MAX]: 각 노드의 방문 여부, visi..
알고리즘 문제 풀이/BOJ 2022. 5. 3. 17:08
[백준 BOJ][C++]1068번 트리 풀이: DFS

이 문제는 DFS로 해결할 수 있습니다. 아이디어는 간단합니다. 탐색 과정에서 자식 노드 중 혹은 자기 자신이 삭제할 노드 dnode라면 그 방향으로의 탐색은 하지 않으면 됩니다. 리프 노드는 자식 노드가 없는 노드이므로, 자식 노드가 있다는 것을 나타낼 flag가 false라면 리프 노드라는 의미이므로 그때 리프 노드의 개수 leaf를 증가 시킵니다. #include #include #include #include #include #include #include #include #include using namespace std; int n; int tree[50][50]; int dnode; int leaf; void dfs(int node) { if (node == dnode) return; boo..
알고리즘 문제 풀이/BOJ 2022. 4. 29. 14:16
[백준 BOJ][C++]2250번 트리의 높이와 너비 풀이: DFS

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net [변수 설명] int n : 노드의 개수 int curr_col : 현재 노드를 배치할 열 ( curr_col - 1번째 열까지는 배치 완료되어 있음 ) int tree[MAX][2] : 트리 정보, tree[node][0]은 node의 왼쪽 자식 노드, tree[node][1]은 node의 오른쪽 자식 노드 vector depth_width : 각 레벨의 양 끝 노드 정보, d..
알고리즘 문제 풀이/BOJ 2022. 4. 28. 18:44
[백준 BOJ][C++]9663번 N-Queens 풀이: DFS & 백트래킹

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 초기 구현에서는 2차원 배열을 사용하여 퀸의 위치에서 동, 서, 남, 북, 대각선 방향의 모든 칸을 해당 열의 번호로 설정하고 dfs의 재귀호출이 끝나면 다시 이 칸들을 0으로 설정하여 구현하였습니다. 맞았습니다! 가 떴지만 실행 시간이 9초 정도가 나와서 보완하고자 구글링을 통해 보다 좋은 성능을 가진 코드를 구현하였습니다. col[x] = x열의 Queen이 위치한 행, y를 의미합니다. dfs(x)는 x열,..
알고리즘 문제 풀이/BOJ 2022. 4. 27. 20:34
[백준 BOJ][C++]1967번 트리의 지름 풀이: DFS

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이 문제는 DFS를 이용하여 해결할 수 있습니다. tree[n] 은 노드 n의 연결된 노드와 그 가중치의 쌍을 저장한 벡터입니다. 어느 노드이든지간에 dfs()를 실행하여 가장 멀리 떨어진 리프 노드를 찾으면 그 노드는 트리의 지름의 양 끝 점 중, 한 점이 됩니다. 때문에 dfs를 호출한 노드로부터 가장 멀리 떨어진 리프 노드를 찾도록 dfs를 구현합니다. dfs(n, 0) ..
알고리즘 문제 풀이/BOJ 2022. 4. 26. 15:37
이전 Prev 1 2 3 4 5 ··· 13 Next 다음