본문 바로가기
728x90

Algorithm128

10828 스택 스택 성공 시간 제한메모리 제한제출정답맞은 사람정답 비율 0.5 초 (추가 시간 없음) 256 MB 57572 22011 16136 40.290% 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N .. 2020. 1. 6.
[Level1]소수의 합(에라토스테네스의 체) [연습문제] C/C++ 소수 찾기1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)제한 조건n은 2이상 1000000이하의 자연수입니다.입출력 예nresult10453입출력 예 설명입출력 예 #1 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환입출력 예 #2 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환#define TRUE 1 #define FALSE 0 #include #include using namespace std; int solution(int n) { int answer = 0, Prime_count = 0; int isPrime = TR.. 2018. 10. 2.
[Level1] 두 정수 사이의 합 [연습문제] C/C++ 두 정수 사이의 합두 정수 a, b가 주어졌을 때 a와 b 사이에 속한 모든 정수의 합을 리턴하는 함수, solution을 완성하세요. 예를 들어 a = 3, b = 5인 경우, 3 + 4 + 5 = 12이므로 12를 리턴합니다.제한 조건a와 b가 같은 경우는 둘 중 아무 수나 리턴하세요.a와 b는 -10,000,000 이상 10,000,000 이하인 정수입니다.a와 b의 대소관계는 정해져있지 않습니다.입출력 예abreturn35123335312 풀이1)#include #include using namespace std; long long solution(int a, int b) { long long answer = 0; int step =0, temp = 0; step = (a - b); if (ste.. 2018. 10. 1.
[Level1] 문자열 내림차순으로 배치하기 [연습문제] C/C++ 문자열 내림차순으로 배치하기문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요. s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다.제한 사항str은 길이 1 이상인 문자열입니다.입출력 예sreturnZbcdefggfedcbZ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #define MAX_SIZE 7 #include #include #include using namespace std; string solution(string s) { string get_string; get_string.. 2018. 9. 20.
[Level1] 문자열 내 마음대로 정렬하기[연습문제] C/C++ 문자열 내 마음대로 정렬하기문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1의 문자 u, e, a로 strings를 정렬합니다.제한 조건strings는 길이 1 이상, 50이하인 배열입니다.strings의 원소는 소문자 알파벳으로 이루어져 있습니다.strings의 원소는 길이 1 이상, 100이하인 문자열입니다.모든 strings의 원소의 길이는 n보다 큽니다.인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.입출력 예stringsnreturn[sun, bed, car]1[car, be.. 2018. 9. 20.
[Level1] 문자열 내 p와 y의 개수 [연습문제] C/C++ 문자열 내 p와 y의 개수대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 리턴합니다. 단, 개수를 비교할 때 대문자와 소문자는 구별하지 않습니다.예를들어 s가 pPoooyY면 true를 return하고 Pyy라면 false를 return합니다.제한사항문자열 s의 길이 : 50 이하의 자연수문자열 s는 알파벳으로만 이루어져 있습니다.입출력 예sanswerpPoooyYtruePyyfalse입출력 예 설명입출력 예 #1 'p'의 개수 2개, 'y'의 개수 2개로 같으므로 true를 return 합니다.입출력 예 #2 'p.. 2018. 9. 20.
K-means, Approx_k Clustering(의사코드, 근사비율) □ K-means 알고리즘 - k평균 클러스터링 알고리즘은 클러스터링 방법 중 분할법에 속한다. ex) N개의 데이터 오브젝트를 입력 받았다면, 분할법은 N보다 작거나 같은 K개의 그룹으로 나누는데, 이 때 각 군집은 클러스터를 형성하게 된다. (1개 이상의 데이터 오브젝트로 구성된 k개의 그룹으로 나누는것) 이 때 군집을 나누는 과정에서 같은 그룹 내 데이터 오브젝트 끼리 유사도는 증가 다른 그룹에 있는 데이터 오브젝트와의 유사도는 감소. - 최초에는 무작위 k개의 중심 1)데이터를 선정하고, 해당 데이터로부터 각 2)데이터의 거리(유클리디언, 맨하탄 등)을 계산한다. 그 거리의 평균이 작은 곳으로 3)중심점을 변경하고, 4)다시 거리를 계산하는 것을 반복하여 최적의 군집을 찾을 수 있다. (유클리디언.. 2016. 11. 16.
크러스컬 알고리즘(KruskalMST) □ 크러스컬 알고리즘은 최소비용 생성나무(spanning tree 스패닝 트리)를 찾는 알고리즘이다. (생성나무란 그래프 이론에서 모든 꼭짓점을 포함하는 부분 나무이다.) 크러스컬의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클(cycle)을 포함하지 않는다는 조건에 근거하여, 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택. □ 크러스컬 알고리즘의 순서 - 먼저, 그래프의 각 간선(edge)들을 가중치의 오름차순으로 정렬. - 정렬된 간선들의 리스트에서 싸이클을 형성하지 않는 간선을 찾아 최소비용신장 트리(MST)의 집합에 추가 - 만약 사이클을 형성하면 그 간선은 버린다. □ 시간 복잡도KruskalMST(G)입력 : 가중치 그래프 G=(V,E), |V|=n,.. 2016. 9. 29.
728x90