알고리즘 및 자료구조

백준 4803 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이 전 나의 생각 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성해야 한다. 조건 - n ≤ 500 - m ≤ n(n-1)/2 과정 주어진 조건들은 입출력의 값에 관한 것들이기 때문에 크게 신경쓰지 않아도 된다. 이 문제에서 신경써야할 것은 트리는 사이클이 없는 연결 요소라는 것이다. 그럼 이 문제에서 신경써야 할 부분은 트리의 사이클이 존재하는 부분을..

백준 1991 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 전 나의 생각 이진 트리를 입력 받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력해야 한다. 조건 - N(1 ≤ N ≤ 26) - 항상 A가 루트 노드가 된다. 과정 노드는 26개 만들 수 있기 때문에 노드의 값을 담을 배열은 데이터 타입 int, 크기를 27로 설정해준다. A가 항상 루트 노드가 되기 때문에 전위, 중위, 후위 순회의 첫 시작은 무조건 A다. ..

백준 13144 https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 전 나의 생각 길이가 N인 수열이 주어질 때, 1개 이상의 연속된 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구해야 한다. 조건 - (1 ≤ N ≤ 100,000) - 수열에 나타나는 수는 모두 1 이상 100,000 이하 과정 수열 N이 10만의 범위로 주어지기 때문에 단순히 2중 for문을 이용한 풀이를 진행한다면 10만 * 10만의 계산 횟수로 시간 제한을 ..

백준 2003 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 전 나의 생각 N개의 수로 된 수열이 주어진다. 이 수열의 i번째 수부터 j번째 수까지의 합이 M이 되는 경우의 수를 구해야 한다. 조건 - N(1 ≤ N ≤ 10,000) - M(1 ≤ M ≤ 300,000,000) - A[x]는 30,000을 넘지 않는 자연수 과정 N, M, A[x]는 int의 범위를 벗어나지 않기 때문에 데이터 타..

백준 1644 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 전 나의 생각 자연수 N이 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해야 한다. 조건 - (1 ≤ N ≤ 4,000,000) 과정 N은 1이상 400만 이하의 값의 범위를 가지기 때문에 데이터 타입을 int로 설정한다. 소수들을 더해줄 누적합의 공간은 400만을 크게 벗어나지 않을 것이기 때문에 데이터 타입을 int로 설정한다. -> 목표로하는 소수의 합은 N이기 때문 소수를 구할 때 최적화 된 방법없이 2중 for문을 사용하면 400만 * 400만의 계산 횟..

백준 1806 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 전 나의 생각 N 길이의 수열이 주어질 때 연속된 수들의 부분합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구해내야 한다. 조건 - N (10 ≤ N < 100,000) - S (0 < S ≤ 100,000,000) - 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수 과정 목표 값 S는 1억 이하의 수기 때문에 데이터 타입을 int로..

백준 2230 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 전 나의 생각 N개의 정수로 이루어진 수열 A에 대하여 두 수를 골랐을 때 그 차이가 M이상이면서 제일 작은 경우를 구해야 한다. 조건 - 1 ≤ N ≤ 100,000 - 0 ≤ M ≤ 2,000,000,000 - 0 ≤ |A[i]| ≤ 1,000,000,000 과정 N, M, A[i] 모두 int형의 범위를 넘지 않기 때문에 데이터 타입을 int로 설정해준..

백준 1477 https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄 www.acmicpc.net 풀이 전 나의 생각 고속도로에 있는 휴게소의 위치 N 개가 주어진다. 이때 휴게소 M 개를 추가적으로 설치할 때 휴게소가 없는 구간의 길이의 최댓값을 최소로 하는 값을 구해야 한다. 조건 - 0 ≤ N ≤ 50 - 1 ≤ M ≤ 100 - 100 ≤ L ≤ 1,000 - 1 ≤ 휴게소의 위치 ≤ L-1 - N+M < L - 모든 휴게소의 위치는 중복되지 않음 - 입력으로..