본문 바로가기

분류 전체보기49

이분탐색 (Binary Search) 기법 오름차순으로 정렬된 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘입니다. 기초적인 알고리즘인 만큼 PS에서 자주 사용할일은 없지만 문제의 조건에서 주어진 수의 규모가 크고 반복해야 할 일이 많다면 해당 기법을 시도해보아야 합니다. 대표적 문제 : 프로그래머스 - 입국심사 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 기본적인 이분탐색 코드는 다.. 2021. 10. 8.
Sort 함수의 커스터마이징, 특정 조건 정렬 알고리즘 문제를 풀다보면 Algorithm 헤더에 포함된 Sort 함수를 자주 이용합니다. 기본적으로 디폴트 함수를 이용해 오름차순 정렬을 이용합니다. #include #include using namespace std; void main(){ int arr[10] = { 2,8,4,6,7,5,1,3,10,9 }; sort(arr, arr + 10); for (int i = 0; i < 10; i++) { cout 2021. 10. 4.
PS에 필요한 String 컨테이너 기본 지식 String 컨테이너는 C++ 표준 라이브러리이지만 STL에 포함시키진 않는다. 문자만을 원소로 저장하기 때문에 유사 컨테이너라 불린다. 코딩테스트를 포함한 여러 PS 문제에서는 문자열 조작이 다양하게 출시되기 때문에 String 컨테이너와 생성자, 멤버함수를 암기하면 편리하다. # 생성자 string str; string str("Hello"); string str("Hello",2); //해당 문자열에서 'He'만 기록 string str(5,'H'); string str(str2.begin(), str2.end()); // 반복자 2개 이용 # 멤버함수 str.front(); // 맨 앞 문자리턴 str.back(); // 맨 뒤 문자리턴 str.substr(i,j); //i부터 j까지 자른 str.. 2021. 9. 9.
기수정렬 (Radix Sort) 기수정렬이란 = 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘 계수정렬과 유사하지만 더 많은 메모리를 차지하고 더 빠른 시간 복잡도를 가진다 ( 정렬횟수 X N) 구현시 주의할점 * 배열의 가장 큰 수를 찾아 정렬 반복회수를 구한다. * 1의자리부터 10의 자리, 100의 자리 순서로 정렬을 진행한다. * 계수정렬과 같이 0,1,2,3,4,5,6,7,8,9 정렬중인 버킷에 넣는 과정을 진행할때는 누적값을 함께 계산해야한다. (=> 해당 누적값이 추후 결과배열의 인덱스로 이용됨) * 정렬의 반복은 배열의 최댓값이 더이상 나눠지지 않을때 (소수점으로 몫이 나올때) 까지 진행된다. #define CRT_SECURE_NO_WARNING #include #include using namespace std;.. 2021. 8. 26.

티스토리툴바