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

영벨롭 개발 일지

[백준 BOJ][C++]2263번 트리의 순회: 분할 정복

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 이 문제는 재귀 함수를 통한 분할 정복을 이용하여 해결할 수 있습니다. 인오더는 왼쪽 자식 → 부모 → 오른쪽 자식 포스터오더는 왼쪽 자식 → 오른쪽 자식 → 부모 프리오더는 부모 → 왼쪽 자식 → 오른쪽 자식 예를 들어 다음과 같은 트리의 인오더와 포스터오더가 주어진다고 가정하겠습니다. index 0 1 2 3 4 5 6 7 8 인오더 4 8 2 5 1 9 6 3 7 포스터 8 4 5 2 9 6 7 3 1 이때 포스터 오..
알고리즘 문제 풀이/BOJ 2022. 7. 19. 14:21
[백준 BOJ][C++]1197번 최소 스패닝 트리 풀이 - Kruskal MST 알고리즘

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net [ 풀이 과정 ] 1. 입력 정보를 받는다. 2. 간선의 정보를 가중치 오름차순 우선순위 큐 edges에 추가한다. 3. 각 정점들의 root 정점을 자기 자신으로 설정한다. parent[i] = i 4. edges에서 간선을 pop 한다. 5. 해당 간선에 양 끝 정점의 root 정점이 같다면 4 단계로 돌아간다. 6. 양 끝 정점의 root 정점이..
알고리즘 문제 풀이/BOJ 2022. 6. 9. 16:11
[백준 BOJ][C++]1339번 단어 수학 풀이: 브루트 포스

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 초기 풀이에선 자리수에 따라 단어들을 일일이 비교하며 해당 알파벳에 숫자를 부여하였더니 틀렸습니다가 떠서 구글링에 힘을 얻어 해결하였습니다..ㅎㅎ 몇몇 사이트를 참고하니 풀이과정은 생각보다 간단했습니다. 각각의 단어에서 해당 알파벳의 자릿수를 저장해두고 해당 자릿수들의 모임을 내림차순 정렬하여 9부터 차례대로 숫자를 곱하여 더해주면 됩니다. #include #include #include #..
알고리즘 문제 풀이/BOJ 2022. 5. 11. 14:09
[백준 BOJ][C++]1931번 회의실 배정 풀이: 그리디 알고리즘

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이 문제는 그리디 알고리즘으로 해결할 수 있습니다. [ 풀이 과정 ] 1. 종료 시각이 빠른 순으로 회의 정보 배열 정렬합니다. 2. 반복문을 통해 이전 종료 시각보다 시작 시각이 같거나 느리면 회의이 개수 ans 증가 ( 정렬했기 때문에 이전 종료 시각보다 시작 시각이 같거나 느린 회의가 자동적으로 지역적 솔루션이 됩니다. ) #include #include #include #include #include #include #include #include #include using namespace std; ty..
알고리즘 문제 풀이/BOJ 2022. 5. 10. 14:20
[백준 BOJ][C++]2146번 다리 만들기 풀이: DFS & BFS

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net [ 풀이 과정 ] 1. 지도 정보를 입력받습니다. 2. 각 대륙을 구분하기 위해 dfs()를 호출하여 대륙에 번호를 부여합니다. 3. 번호 부여가 완료되면, 각 대륙으로부터 다른 대륙으로의 최단 걸이를 구하기 위해 bfs()를 호출합니다. 4. bfs() 인자로 전달받은 대륙 번호에 해당하는 위치를 방문 표시 후 queue에 푸쉬합니다. 5. queue의 현재 노드 curr를 pop 합니다. 6. 현재..
알고리즘 문제 풀이/BOJ 2022. 5. 7. 16:25
[백준 BOJ][C++]1654번 랜선 자르기 풀이: 이진 탐색

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net #include #include #include #include #include #include #include #include #include using namespace std; int k, n; long long ans; vector line; int main(void) { cin >> k >> n; for (int i = 0; i < k; i++) { int x..
알고리즘 문제 풀이/BOJ 2022. 5. 4. 19:42
이전 Prev 1 2 3 4 ··· 14 Next 다음