Algorithms 검색 결과

해당 글 123건

[BOJ 1167] 트리의 지름(C++)

트리의 지름(Gold 3) 문제 전체 문제 보기 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 접근법 이 문제는 BFS/DFS를 두 번 탐색하여 풀 수 있다. 아래의 그림을 보자. 위와 같은 트리가 주어졌을 경우 트리의 지름은 아래와 같이 노드 5에서 출발해서 노드 7로 연결하는 길이인 24이다. 이문제를 풀기 위해서 생각해볼 점은 "임의의 노드에서 가장 멀리 떨어진 노드는 반드시 '노드 5' 혹은 '노드 7'이다."라는 점이다. 임의의 노드에서 탐색을 진행하여 그 노드와 가장 멀리 떨어져 ..
Algorithms/DFS & BFS 2021. 9. 3. 12:04

[BOJ 1043] 거짓말 (C++)

거짓말 (Gold 4) 문제 전체 문제 보기 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 접근법 이 문제에서 진실을 모르는 사람들만 있는 파티의 수를 구해야 한다. 이 문제에서 진실은 같은 파티에 참석한 사람들에게 전파되는 특징이 있다. 파티의 참석자를 노드, 파티의 참석 정보를 인접 노드에 대한 정보, 진실이 전파되는 특징을 인접 노드 탐색으로 본다면 BFS로 풀 수 있는 문제이다. 자료구조 선택 BFS 알고리즘을 활용하여 문제를 풀어본다. BFS로 풀이하기 위하여 다음과 같은 노드를 정의할 수 있다. BFS에서는..
Algorithms/DFS & BFS 2021. 9. 2. 08:31

[BOJ 2579] (DP)계단 오르기(C++)

계단 오르기 (Silver 3) 문제 전체 문제 보기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 접근법 이 문제는 예전에 풀었던 BOJ 2156 포도주 시식 문제와 상당히 비슷하다.(포도주 시식 풀이) 포도주 시식 문제와의 차이점은 이 문제에서는 반드시 마지막 계단을 포함해야 한다는 점이다. 이번 문제에서도 3개의 계단을 연속으로 밟을 수 없다. 그래서 임의의 위치 \(n\)에서 점수의 최댓값을 \(f(n)\), \(n\)의 점수를 \(a(n)\)이라고 했을 때 \(f(n)\)은 아래의 두 가지 경우 중 큰 값이 이..
Algorithms/DP 2021. 8. 27. 17:29

[BOJ 10844] (DP) 쉬운 계단 수 (C++)

쉬운 계단 수 (Silver 1) 문제 전체 문제 보기 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 접근법 N자리의 계단수가 되기 위해서는 N자리에 숫자는 N-1자리의 숫자와 1만큼 차이가 나야 한다. 각 자릿수마다 끝자리 숫자를 기준으로 만들 수 있는 수의 개수를 카운트할 수 있다. 예를 들어 두 자릿수들 중 3으로 끝나는 계단 수는 23, 43 두 개가 존재하고, 5로 끝나는 계단 수는 45, 65가 존재한다. 그렇다면 세 자리 수중 4로 끝나는 계단수는 몇 개가 존재할까? 두 자리 수중 3으로 끝나는 수들의 개수와 5로 끝나는 수로 세 자릿수 중 4로 끝나는 계단 수를 만들 수 있기 때문에 총 4개를 만들 수 있다...
Algorithms/DP 2021. 8. 26. 20:43