프로그래머스를 풀다가 누군가 독특한 방법으로 약수의 개수를 구하는 걸 발견해서 성능을 테스트 해보기로 했다. 우선 내가 작성한 알고리즘이다. num까지 순회할 필요 없이 제곱근까지 순회하며 2개씩 더하는 방식이다. int getNumberOfDivisor(int num = 1020) { int last = sqrt(num); int count = (pow(last, 2) == num) ? -1 : 0; for (int i = 1; i
Level 1. 기사단원의 무기 약수의 개수를 효율적으로 구하는 것이 중점인 문제였다. 나는 num의 제곱근만큼 순회하면서 나머지 연산을 이용해 계산하였다. #include #include using namespace std; int getNumberOfDivisor(int num) { int last = sqrt(num); int count = (pow(last, 2) == num) ? -1 : 0; for (int i = 1; i
Level 1. 대충 만든 자판 어려운 문제는 아니었다. keymap에서 가장 작은 위치를 찾으면 된다. #include #include using namespace std; vector solution(vector keymap, vector targets) { size_t size = targets.size(); vector answer(size, 0); for (int i = 0; i < size; ++i) { for (char c : targets[i]) { int pos = -1; for (string key : keymap) { int p = key.find(c); pos = (p == -1) ? pos : (pos == -1) ? p : min(p, pos); } if (pos == -1) {..
Level 1. 실패율 stages 벡터를 정렬하거나 count_if() 함수를 이용할 수도 있지만 나는 각 스테이지별 도달한 사람 수를 미리 계산하여 사용했다. 1 ~ N을 갖는 인덱스 배열을 만들고 실제 정렬은 reached_users 벡터에 인덱스를 전달해 수행할 수 있다. stable_sort() 함수를 사용하면 같은 순위를 갖는 원소의 순서를 유지할 수 있다. #include #include #include using namespace std; // i+1번째 스테이지에 도달한 사람 = i번째 스테이지를 클리어한 사람 // (i번째 스테이지에 도달한 사람 - i번째 스테이지를 클리어한 사람) / i번째 스테이지에 도달한 사람 // i번째 스테이지에 있는 사람 / i번째 스테이지에 도달한 사람 f..
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 최단 작업 우선 스케줄링 처리 시간이 짧은 작업을 우선적으로 배치해 전체 수행 시간을 줄이는 방법이다. 가능한 많은 작업의 대기 시간을 줄이기 위해서는 짧은 작업을 우선적으로 처리해야 한다. 최단 작업 우선 스케줄링의 예 프로세스 수행 시간에 따른 CPU 할당 순서 지정 ... #include #include #include #include using namespace std; template auto compute_waiting_times(vector& service_times) { size_t size = service_times.size(); vector W(size, 0); for (int i = 1; i < size; ++i) W[i] =..
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 탐욕법 매번 탐욕스럽게 현재 상황에서의 최적해를 선택하는 방법이다. 탐욕법의 해가 항상 최적해가 되는 것은 아니다. 다음의 두 가지를 만족하면 탐욕법을 통해 최적해를 구할 수 있다. 최적 부분 구조(Optimal Substructure): 문제 P의 최적해가 P의 부분 문제들의 최적해로 구성될 경우 탐욕 선택(Greedy Choice): 문제 P의 지역적 최적해를 반복적으로 선택해 전체 최적해를 구할 수 있는 경우 탐욕법의 예 다익스트라(Dijkstra) 알고리즘 지도에서의 최단 경로 계산 등 최단 작업 우선(SJF, Shortest Job First) 스케줄링 총 대기 시간 단축 등