알고리즘12 [프로그래머스] level 1 - 크레인 인형뽑기 게임 #include #include #include using namespace std; int solution(vector board, vector moves) { int answer = 0; stack s; for(int i=0;i moves의 원소를 하나씩 꺼내 board의 열에 해당하는것을 표현할수 있도록 재정의함. 3. board 배열안 원소가 0이 아닐경우 (비어있지 않는 경우) 비교함 => 스택이 비어있는 초기의 경우 , board 에서 moves 에 해당되는 원소를 스택에 저장한다. 그다음 순서부터는 board 에서 moves 에 해당되는 원소 와 스택에 저장된 값을 비교한다. 바로 다음 중복되는 경우를 파악하기 위해 직전에 뽑은값과 현재 뽑은 원소를 비교하는것이다. 값을 비교했을때 같은 경우.. 2020. 5. 4. [프로그래머스] level 1 - 완주하지 못한 선수 #include #include #include using namespace std; string solution(vector participant, vector completion) { string answer = ""; int a=0; sort(participant.begin(),participant.end(),less()); sort(completion.begin(),completion.end(),less()); for(int i=0;i 순서는 문제푸는데 상관없어보이기 때문에 정렬함 3. 같지않으면 participant를 답에 넣음 => 같지않으면 completion만 변하도록 함 , 같은 이름일 경우가 존재하므로 completion 만 변하도록 하는것이 깔끔함 2020. 5. 3. 탐욕적 알고리즘 탐욕 알고리즘그리디 알고리즘은 동적 프로그래밍 사용시 지나치게 많은 일을 한다는것에서 착안된 알고리즘 이다.각 단계에서 최선의 선택을 하는 기법이다.각단계에서 최선의 선택이 전체의 최선을 만든다는 가정하에 시작된다.동적 계획법보다 효율적이만 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장은 없다.탐욕적 알고리즘은 동적 계획법보다 수행시간이 훨씬 빠르다.시간이나 공간적인 제약으로 인해 최적해를 찾기어려울경우, 근사해를 찾는 용도로 쓰인다.예시문제 가장 적은 수의 동전으로 해당 액수를 구성해주는것이 최적의 해이다. 우리는 140원의 거스름돈을 만들어 줘야한다.우리가 100원, 50원, 10원 동전을 여러개 가지고 있다는 가정하에 탐욕적알고리즘을 사용할 경우, 140원 보다 작으면서 후보 목록중에서 가장 .. 2018. 12. 24. 완전탐색 # **완전탐색** 문제를 해결하는 방법중 가장 기초 가능한 모든 경우를 시도해 보는것입니다. 문제가 주어지면 제일먼저 완전 탐색법으로 시도해보아야합니다. 가능한 모든 경우 = 탐색 공간 (search space) : 고려해야하는 모든 경우 완전 탐색법은 가능한 모든경우를 하나도 빠짐없이 모두 고려하기 때문에 틀릴 경우가 가장 적지만, 시간은 최대로 소요됩니다. 모든 가능성을 따져봐야 하기때문에 문제의 크기가 클수록 , 실행시간이 지수적으로 증가할수 있습니다. 대회에 참가하거나 아주 어려운 문제에 직면한 경우, 완전 탐색법을 적용하는것이 좋습니다. 실행시간 제한에 의해 실패할수 있지만, 정답 크기가 적은 경우에 부분점수를 획득할 수 있기때문입니다. 완전 탐색을 할 수있는 방법 1. brute force .. 2018. 12. 10. 이전 1 2 3 다음