1. 두 포인터란? 포인터 두 개를 사용하여 배열이나 문자열을 탐색하는 알고리즘이다. 흔히 배열을 탐색하다 보면 완전탐색을 진행할 경우 O(N²)의 시간복잡도를 가진다. 하지만 투 포인터를 이용하면 동시에 포인터 두 개로 탐색하므로 O(N)의 시간 복잡도로 한 번에 탐색할 수 있다. 예시 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net #include #include using namespace std; int N, M, a..

어떤 수의 자릿수를 구하는 알고리즘은 크게 세 가지로 생각할 수 있다. 1. 나머지 연산자를 이용하기 아이디어 중학교 수학시간에 자릿수에 대해서 배웠다. 자연수 k = 소수(0.xxx) x 10ⁿ으로 나타낼 때 k는 n자리 자연수라고 표현한다. 예를 들어 1234 = 0.1234 x 10⁴ 이므로 1234는 네 자리 자연수이다. 따라서 10으로 나눈 몫이 0이 될때까지 계속 나누면 나눈 횟수가 자리수가 된다. 구현 #include using namespace std; int digit(int n){ int ret = 0; while(n!= 0){ n /= 10; ret++; } return ret; } int main() { int num; cin >> num; cout > n; int digit = f..

숫자 데이터를 처리하다 보면 각각의 자리를 직접 분해하여 가져와야 하는 경우가 생긴다. 자릿수를 구하는 알고리즘은 간단한데 자릿수를 분해하는 알고리즘은 조금 까다롭다. 1. 자릿수 분해란? 자연수의 자리를 하나씩 분해하는 것이다. 예를 들어 145를 자릿수 분해하면 일의 자리:1 십의자리: 4 백의 자리: 5 이렇게 분리할 수 있다. 자릿수를 분해하는 알고리즘은 크게 string을 이용하는 방법과 수학적인 방법을 떠올릴 수 있다. 2. 자릿수 분해 알고리즘 1) 반복문 이용하기 아이디어 중학교때 배운 자릿수의 개념을 이용하여 하나씩 가져오는 것이다. 구현 벡터를 이용하면 되는데 이 경우에 자릿수는 벡터의 크기이다. #include #include using namespace std; int a, b; v..

최적화(최대 or 최소)문제를 결정 문제로 바꾸어서 푸는 기법이다. 의심: 완전탐색, DP, 그리디로도 해결할 수 없는 최적화문제의 경우에 두 데이터간의 관계가 단순 비례 반비례에 따른 증감이며 Parameteric Search를 의심해볼 수 있다. 보통 감을 잡기가 매우 어려워서 나중에 돌아와서 떠올리면 베스트 파라메트릭 서치는 STL을 직접 이용할 수 있는 이분탐색과 달리 직접 변수를 설정하고 관계에 따라서 탐색의 범위를 지정해주어야 한다. ??? 예제: 랜선 자르기 백준 1654 주의 사항: 1. 무한 루프 주의: mid를 기준으로 선택의 범위가 균등한지 만약 균등하지 않다면 mid+1로 보정해줘서 무한루프를 방지해줘야함 2. 두 변수간의 관계주의: parameter과 target간의 관계(비례 반..

이번 글에서는 그리디 알고리즘에 대해 다루어 보겠습니다. 가장 대표적인 예제인 동전 문제와 회의실 배정 문제와 함께 다룰 예정이니 참고해 주세요 1. 탐욕법이란? 탐욕법이란 미래를 고려하지 않고 현재 가장 최선의 선택을 하는 알고리즘입니다. 쉽게 말하면 한 번 선택하고 난 후 앞이나 뒤를 전혀 돌아보지 않는 알고리즘입니다. 2. 특징 그리디 알고리즘에서는 다음의 특징을 가집니다. 그리디 선택 속성(Greedy Choice Property) 현재 선택은 미래의 선택에 영향을 미치지 않습니다. 이를 그리디 선택 속성이라고 합니다. 최적 부분 구조 현재 선택들이 모여 전체의 최적해를 보장해야만 믿고 현재 최선의 선택을 할 수 있습니다. 앞에서 말했듯이 미래의 선택을 고려하지 않고 과거도 돌아보지 않기 때문에 ..

이번 글에서는 해시 테이블에 대해 알아보겠습니다. 삼성 SW역량테스트 B형에서는 C++ 컨테이너, 파이썬의 모듈 등 이미 구현된 자료구조는 쓸 수 없어서 직접 구현해야 합니다. 그 경우를 제외하고는 해시 테이블을 직접 구현하는 일은 거의 없으므로 구현보다는 기능과 활용을 중심으로 다룰 예정입니다. 구현은 접은글로 자세하게 작성했으니 궁금하면 참고해 주세요.  1. 해시 테이블이란?해시 테이블은 아주 많은 양의 데이터를 저장하고 접근할 때 빠른 속도로 찾을 수 있는 자료구조입니다. 코테같은 알고리즘에서는 주로 1억이 넘어가는 데이터 ????를다루는데 쓰일까?많은 양의 데이터를 저장하고 탐색하는 경우 아무리 빨라도 O(n)의 시간복잡도를 가집니다. 하지만 해시 테이블은 key, value를 이용하여..

https://velog.io/@gnwjd309/data-structure-heap [자료구조] 힙(Heap) 이해하기 Heap이란 무엇인가요! velog.io

https://suyeon96.tistory.com/31 [자료구조] 우선순위 큐와 힙 (Priority Queue & Heap) 1. 우선순위 큐 1.1 우선순위 큐란? 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위 suyeon96.tistory.com