목록알고리즘 문제 풀이 (81)

영벨롭 개발 일지

[백준 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
[프로그래머스/2021 KAKAO BLIND][C++]Level 1 코딩테스트 연습 - 신규 아이디 추천

https://programmers.co.kr/learn/courses/30/lessons/72410?language=cpp 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr [문제 설명] 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프..
알고리즘 문제 풀이/프로그래머스 2022. 4. 26. 16:24
이전 Prev 1 2 3 4 5 ··· 14 Next 다음