Algorithm (17) 썸네일형 리스트형 [완전탐색] 소수 찾기 완전 탐색을 하기 위해서 케이스를 배열에 담고 splice를 이용하여서 재귀하는 방식을 이용하였다. 첫번째 인자에는 남은 케이스를 두번째 인자에는 현재 타겟을 이용하였고, 남은 케이스의 길이를 반복하였다. 중복을 체크하기 위해서 Set을 이용하였는데, has와 add 메소드를 파악해두자. 1 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 35 function solution(numbers) { var answer = 0; var numberArray = numbers.split(''); var checkNumber = new Set() recursion(numberArray,''); fun.. [탐욕법] 체육복, 구명보트 탐욕법(Greedy) 어떤 문제를 접했는데 당연히 DP로 해결하는 문제라고 생각했다. 다만 조건이 꽤 다양한 편이라서 성가신 문제라고 생각했는데, 효율성에서 완전 엉망이 됬다. 탐욕법은 DP와 같이 다양한 케이스중 최적해를 찾을 때 사용되는 알고리즘이다. 그리고 이는 DP보다 빠르다. 체육복 굉장히 어려운 문제는 아니다만, DP로 오해하면 한 없이 복잡해진다. 최적의 경우, 최대한 많이, 그리고 많은 조건을 키워드로 탐욕법이라는 것을 유추해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #include using namespace std; int student[35]; int solution(int n, vector lost.. [DP] N으로 표현, 타일 장식물, 정수 삼각형 N으로 표현 계속해서 추적해야 하는 값이 수의 케이스이기 때문에 배열을 리턴한다. d[n] = n개를 사용하여 만든 수의 모음 d[n] 은 d[n-i] + d[i] ( 이 때, i는 1부터 n-1) 까지 이 때 중복된 값은 딱히 제거하지 않아도 상관없으나, 말 그대로 중복해서 계산하기 때문에 중복을 무시하기 위해 set을 이용한다. 마지막으로 목적하는 값이 있다면 해당 인덱스를 리턴한다. 아닌 경우에는 -1을 리턴한다. 1 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 35 36 #include #include #include using namespace std; int N; unorder.. [힙(Heap)] 더 맵게, 라면 공장, 이중 우선순위 큐 힙은 완전이진트리자료구조이다. 완전 이진 트리는 다음과 같은 성격을 지닌다. 1. 이진 트리는 하나의 부모에 두개의 자식을 지닌다. 2. 값은 자식의 왼쪽부터 순서대로 입력받는다. 3. 부모는 자식보다 무조건 크거나 작고( 정렬 기준에 따라 다르다.) 고로 Root 노드는 가장 크거나 가장 작다. 이와 같이 힙 구조를 이용하면 완전히 정렬하지 않더라도, 최대값 혹은 최소값을 구할 수 있게 된다. (일반적인 정렬은 nlogn의 시간만큼 드는 반면 힙은 깊이만큼만 실행하므로 logn만큼의 시간 복잡도가 생긴다.) c++ 에서는 이와 같은 힙을 활용해서 만든 STL Container인 우선순위 큐가 있다. 우선순위 큐를 이용하면 모두 정렬하지 않아도 최대값 혹은 최소값을 하나씩 구할 수 있다. 우선순위 큐의 .. [Hash] Map(STL Container) 이해하기 (완주하지 못한 선수, 위장) 들어가기 앞서... 자바스크립트로 Hash를 처리하려면 다음 포스팅을 보자 https://moonsupport.tistory.com/235 Javascript로 Hash 처리하기 c++이나 자바 파이썬의 map, Hashmap, dictionary과 같이 Hash처리하기 위해 마땅히 좋은 방법이 없는거 같다. 아니면 내가 모르는 거겠지... 오랜만에 한 번 사용해봤는데 너무 미숙해서 정리를 하고자 한다. 1 v.. moonsupport.tistory.com 사용법 헤더 파일 #include 선언 map 변수명 추가 및 삭제 변수명[key] = value : key를 인덱스로 value를 값으로 배열처럼 삽입가능 insert(make_pair(key,value)) : pair 형태로 추가 erase(key.. [정렬2] ABC, 수열 정렬, 전화번호부 목록,거북이 ABC 오름차순 내림차순이 아니라 ABC를 통해 임의적으로 정렬하는 방식이다. 미리 배열을 정렬해두고 입력 받은 string 값을 charAt으로 접근하는 방식으로 문제를 해결 할 수 있다. 1 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 #include #include #include #include using namespace std; int main(void) { vector numVector(3); for(int i=0; i> numVector[i]; } sort(numVector.begin(), numVector.end()); string abc; cin >> abc ; for(int i =0; i [DFS] DFS/DFS, 타겟넘버, 네트워크, 단어변환 DFS/BFS 그래프 검색은 다음과 같은 특징을 지닌다. 1. 배열간의 연결들로 이루어진 배열을 지닌다. 2. 방문에 대한 기록을 가지는 배열을 지닌다. 3. 연결되어 있고 방문하지 않은 노드들에 대하여 Search를 진행한다. DFS의 경우는 위의 특성과 더불어 다음과 같은 특성을 가진다. 1. 재귀 함수를 이용한다. ( 스택도 사용한다고 하지만 아직 보지 못함 ) 2. 재귀 함수를 사용하기 때문에 첫번째 요소의 방문 여부는 함수 밖에서 처리한다. 3. 이를 이용하여 깊이 우선으로 탐색한다. (가능한 끝까지 모든 연결된 자식노드 먼저 처리) BFS의 경우는 그래프 특성과 더불어 다음과 같은 특성을 지닌다. 1. queue를 이용한다. 2. 함수안에서 첫번째 요소에 대한 방문여부를 지정한다. 3. 이를 .. [정렬] K번째 수, 가장 큰 수, H-Index, 수 정렬하기, 나이순 정렬, 단어 정렬 K번째 수 알고리즘 이미지 splice를 통해 배열을 자르고 새로운 배열에 추가한다. 이후에 정렬을 하고 N번째 값을 리턴한다. 문제 따라서 해결 하면 되는 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include #include #include #include using namespace std; vector solution(vector array, vector commands) { vector answer; vector tempArr; for(vector arr : commands) { tempArr.clear(); tempArr.assign(array.begin() + arr[0] - 1 , array.begin() + arr[1]); /.. 이전 1 2 3 다음
