개인공부(c++) (5) 썸네일형 리스트형 [C/C++] 그리디 알고리즘 문제풀이 1 16435 스네이크버드 수요일은 알바하는 날이라 문제 업로드를 못했다.. 오늘도 귀찮아서 자기 전에 끄적끄적 올리고 있는데 열심히 해야지 운동한다고 힘이 쭉쭉 빠진다 기운이 읍네 읍어 쉬운 문제고 난이도는 실버5정도라고 한다. 제출 수도 적어서 안풀까 했는데 그냥 올리는 문제 #include #include using namespace std; int main(){ int N, L; cin >> N >> L; int arr[N]; for(int i=0; i [C/C++]백준 4796_캠프, 그리디 알고리즘 그리디 알고리즘을 공부하다가 관련 문제를 풀어보기 시작했다 간단하게 그리디 알고리즘이란 지금 순간에서 최적의 답을 선택해서 적합한 결과를 도출해내는 알고리즘이다. 예를 들어 양갈래 길이 여러개 있는 길을 갈때 갈림길에서 그 순간에 제일 적게 걸리는 길을 선택해 가며 가는 방법인데 굉장히 합리적으로 보일 수 있지만 장기적으로는 적합하지 않은 방법일 수 있다. 순간의 최적의 해지만 전체로는 최적의 해가 아닐 가능성이 높기 때문이다. 위와 같이 서울에서 부산을 갈때 잘 동작한다. 그리디 알고리즘은 탐욕 선택 속성과 최적 부분 구조 특성을 가지는 문제들을 해결하는데 강점이 있는데 서울에서 부산을 바로 갈때는 그리디 알고리즘이 부적합하지만 서울에서 대구를 거쳐 부산을 가야하는 특수한 경우에는 최적의 요건을 충족시.. [C/C++] STL sort() 정렬 공부를 하다가 문득 궁금해졌는데 매번 코딩 테스트에선 정렬 알고리즘을 사용해야하나 싶었다. 결론부터 말하면 아니다. 퀵 정렬처럼 제일 빠른 정렬을 사용해야될 것 같은 맘에 문제들을 풀때 직접 함수를 만들어 정렬해왔는데 헤더 파일에 있는 STL Sort 라이브러리를 사용하면 되더라. O(NlogN)의 시간 복잡도를 가지기 때문이다. 입력의 크기가 커질 경우 효율적으로 정렬하기 위해 진화된 정렬 방식을 사용하는데 Sort() 함수는 이에 최적화 되어있다. #include #include using namespace std; int main(void){ int arr[10] = {6, 2, 9, 8, 7, 1, 4, 5, 3, 10}; // 정렬 // 첫번째 인자 = 배열의 포인터 // 두번째 인자 = .. [c/c++] 백준 1978_소수 찾기 소수 찾기 문제 처음에는 간단하게 생각했는데 여러가지 방법이 있더라 평소에 하던 방법은 직접 입력된 수를 1부터 자기 자신까지 다 나누어 보면서 반복문을 돌렸다. O(N)의 시간만큼 소요된다. 이 방법을 사용한 사람들 코드를 보니 그렇게해도 시간 초과는 안되는듯? 그래도 시간 적게 돌리고 싶어서 고민 다른 방법으로는 자신의 루트 값까지 반복문을 돌리면서 나뉘어 지는지 확인 곱셈의 특성 상 약수가 짝지어 이루어지기 때문에 루트 아래로만 나뉘어 지는지 확인해도 자연스럽게 약수 판별이 가능 O(√N) 의 시간 복잡도를 가지며 시간이 반절로 줄어든다. 에라토스테네스의 체라는 소수 판별 알고리즘이 있었다. 이건 또 무슨 수학자람 시간복잡도 O(Nlog(logN))를 가지는데 증명 과정을 보니 패스하도록 하자. 위.. [c/c++] 백준 10757_큰수 A+B 파이썬은 a+b, 자바는 biginteger를 사용해서 문제를 쉽게 해결 가능하나 c++로는 숫자를 문자열로 받아 직접 계산. #include #include #include using namespace std; int N, sum; int num1[10001], num2[10002]; string s1, s2, tmp; vector vec; int main(){ cin >> s1 >> s2; //문자열 형태로 s1, s2를 입력받음 if(s1.size() < s2.size())//문자열 길이 비교해서 두 수중에서 더 큰걸 s1으로 설정 { tmp = s1; s1 = s2; s2 = tmp; } for(int i=0; i= 10) { num1[i - 1]++; sum -= 10; } vec.push_ba.. 이전 1 다음
