본문 바로가기

알고리즘7

백준 1208번 부분수열의 합 2 - 문제 설명 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. - 입력 1) 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 2) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. * 주어지는 정수의 절댓값은 100,000을 넘지 않는다. - 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. * 문제 풀이의 핵심 1. 브루트포스 부분수열의 합 2 문제는 주어진 집합의 모든 부분수열을 구한 뒤 더한 값이 S가 되는지 되지 않는지에 대해서 검사해야하는 문제 입니다. N의 제한은 1에서 시작해 최대 40 이기 때문에 집.. 2020. 11. 26.
프로그래머스 섬 연결하기 - 문제 설명 n개의 섬 사이에 다리를 건설하는 비용이 주어질 때 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 하는 solution 작성 - 입력 1) 섬의 개수 n (1 사용언어 : C++ > 에디터 : Visual Studio 2017 > 궁금한점은 댓글로 남겨주세요 - 참고 1) gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html 2) gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html 2020. 9. 6.
프로그래머스 순위 - 문제 설명 n명의 권투선수의 1:1 경기 기록을 가지고 있을 때, 주어진 경기기록을 가지고 정확한 순위를 매길 수 있는 권투선수의 수를 return 하는 solution 함수 작성 - 입력 1) 선수의 수 : 1 2020. 9. 3.
프로그래머스 N으로 표현 - 문제 설명 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하는 solution 함수 작성 - 입력 1) N (1 궁금한점은 댓글로 남겨주세요 - 참고 : https://mungto.tistory.com/61 2020. 9. 1.
백준 1655번 가운데를 말해요 - 문제 설명 수빈이는 동생에게 '가운데를 말해요' 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. - 입력 첫째 줄에는 수빈이가 외치는 정수의 개수 N (1 > N; int i; for (i = 0; i > arr[i]; } q_max.push(arr[0]); cout q_min.top()) { int t1 = q_min.top(); q_min.pop(); int t2 = q_max.top(); q_max.pop(); q_min.push(t2); q_max.push(t1); } cout 사용언어 :.. 2020. 8. 12.
백준 12015번 가장 긴 증가하는 부분 수열 2 - 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램 작성 ex) A = {10,20,10,30,20,50} 인 경우 가장 긴 증가하는 부분 수열은 {10,20,30,50} 이다. 길이는 4이다. - 입력 첫째 줄에 수열 A의 크기 (1 > A[i]; } lis.push_back(A[0]); int l_idx = 0; for (i = 1; i 에디터 : Visual Studio 2017 > 궁금한점은 댓글.. 2020. 8. 10.
백준 1300번 K번째 수 - 문제 설명 배열 A는 크기가 N*N 인 2차원 배열, 배열 B는 크기가 N*N 인 1차원 배열 A[i][j] = i * j 로 이루어진 2차원 배열의 모든 원소를 배열 B에 넣고 오름차순 정렬했을 때 B[k]의 값을 구하는 문제 ※ 배열 A와 B의 인덱스는 1부터 시작한다. - 입력 첫째 줄에 배열의 크기 N (1 k; long long left = 1; long long right = (N * N); while (left = k) { right = mid; } else { left = mid + 1; } } cout 사용언어 : C++ > 에디터 : Visual Studio 2.. 2020. 8. 6.

티스토리툴바