목록알고리즘 문제풀기/백준(Acmicpc) (21)
문제링크 : https://www.acmicpc.net/problem/11727 길이 n이 주어진다. 2 x n 크기의 직사각형을 채우는 방법의 수 (%10,007) 계단을 1칸 2칸씩 오를 때의 경우의 수와 같은 전형적인 dp문제이다. 따라서 (2 x (n-1))의 경우와 (2 x (n-2))의 경우를 더해주면 된다. 여기서 주의해야할 점은 (2 x (n-1))의 경우를 2번 더해줘야 한다는 점이다. (즉, x 2) 이유는 2 x n 크기의 직사각형을 채울 수 있는 방법을 시뮬레이션 해보면 알 수 있다. 위 사진에서 ?가 그려진 직사각형을 2 x n 크기로 보자. 그러면 아래 그림처럼 1칸 적은 직사각형에서 2 x 1을 더하는 경우와 2칸 적은 직사각형에서 2 x ..
문제링크 : https://www.acmicpc.net/problem/1967 노드의 개수 n (n-1)개의 간선 정보 (부모, 자식, 가중치) 트리의 지름(트리의 두 정점 간의 거리 중 가장 최대값) 우선, 트리의 가중치가 음수 혹은 0인 경우가 존재하지 않는다면 두 정점간의 거리의 최대값은 리프 - 리프 노드 사이에 존재한다. 이 생각을 시작으로 문제를 접근했다. 루트 노드의 번호는 언제나 1이다. 이 문제는 부분으로 나눌 수 있다. 6번 노드가 루트인 서브 트리의 최대값은 (10+6=16)이고 5번 노드가 루트인 서브 트리의 최대값은 (15+4=19)이다. 그리고 각각 위로 갈 수 있는 최대 경로인 10과 15를 넘겨준다. 다음으로 3번 노드가 루트인 서브트리의 최대값은 5번 노드로부터 받은 (15..
문제링크 : https://www.acmicpc.net/problem/1008 간단한 문제지만 확실히 알아야하는 문제이다. Codeforces 라운드에서 많이 틀렸던 유형이기도 하다. 정수형의 수들은 알고리즘 문제를 해결하며 많이 다뤄보지만 소수점은 많이 다뤄보지 않는다. 그래서 확실하게 알아놓지 않으면 갑작스럽게 문제가 생겼을 때 당황하기 쉽다. 먼저, 오답이다. - 소스 코드(오답) - #includeusing namespace std;int main(void) {float a, b;cin >> a >> b;float c = a / b;printf("%.9f", c);} 소수점을 계산하기 위해 float으로 입력을 받았다. 그리고 10^-9 이하의 오차만 허용하므로 .9f를 사용해 아홉번 째 자리까지..
문제링크 : https://www.acmicpc.net/problem/3111 먼저 결과만 말하자면 이 문제는 내 힘으로 풀지 못했다. 그래서 잘못 생각한 점, 도움을 받은 방법을 적으려고 한다. 이 문제의 설명은 간단하다. A, T라는 2개의 문자열이 주어지고1. T에 A가 없으면 알고리즘을 종료한다.2. T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.3. T에 A가 없으면 알고리즘을 종료한다.4. T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.5. 1번으로 돌아간다. 이 문제를 보고 시도한 방식은 문제에서 주어진 것과 같다. 1. 문제에서 주어지는 방식대로 T의 맨 앞부터 A가 나올 때까지 탐색을 하고,2. A가 나올 경우 index를 A의 길이만큼 더한다. ( 새롭게 만들어진 문자열에 추가하지..
문제 링크 : https://www.acmicpc.net/problem/16510 cin / cout의 입출력 속도를 높이지 않고 풀었을 때 시간초과가 났던 문제이다. 먼저 일의 개수인 N이 주어진다. 매번 일을 수행할 때 앞에서부터 수행해서 시간안에 할 수 있는 일의 개수를 물어보는 문제이기 때문에 N을 입력받으면서 누적합을 하여 값을 저장해야한다. 단순히 값을 저장할 경우 매번 앞에서부터 합하며 결과를 확인해야하기 때문이다. 다음 과제는 주어진 일의 시간이 어느 구간에 들어가는지를 확인하는 것이다. 일할 수 있는 시간이 충분히 작다면 최대크기의 배열을 생성해서 N을 받으면서 값을 늘려가는 방법으로 들어온 시간을 인덱스로 하여 확인할 수 있지만 시간, 즉 T의 범위가 2*10^9이다. 배열로 만들기에는..