매일매일 알고리즘 공부/알고리즘 개념

DP(Dynamic Programming) 💡 DP Dynamic Programming : 동적계획법 (동적 프로그래밍) 복잡한 문제를 재귀적인 방법으로 해결하는 알고리즘 설계 기법이다. 주로 ⭐최적화 문제에 많이 사용되며, 부분 문제의 해답을 저장해서 같은 계산의 반복을 피해 계산 시간을 줄여준다. 핵심 : 이전에 계산한 값을 다음 단계에서 써 먹는다는 사실! 핵심 : 문제의 재귀적인 구조를 찾아라! DP 알고리즘은 중복된 계산을 줄인다는 점에서 굉장히 효율적인 알고리즘이다. DP의 주요 방법 탑다운(Top-down) 접근법 (메모이제이션) : 재귀를 사용하여 큰 문제에서 작은 문제로 나아가며, 각 단계의 결과를 캐시(메모리)에 저장한다. 바텀업(Bottom-Up) 접근법 (타뷸레이션) : 반복문을 사..

💡 👍🏻 후위식은 연산자를 피연산자 뒤에 놓고 표기하는 방법이다. 3 10 * → (피연산자) (피연산자) (연산자) 중위 표기법이란? 숫자와 숫자 사이에 연산자를 넣어서 식을 표현하는 것이다. 피연산자 사이에 연산자가 위치하는 식을 중위 표기법이라고 한다. 후위 표기법이란? 후위 표기법은 연산자가 피연산자 뒤에 위치한다. i++ , a++ 11+ 와 같이 표현하는 것을 후위 표기법이라고 한다. 💡 중위 표기법은 사람이 이해하기 쉽게 표현하는 방법이라면, 후위 표기법은 컴퓨터가 연산을 하기 쉽게 표현하는 방법이다. 후위 표기법을 계산하는 방법 1. 숫자(피연산자) 는 스택에 넣는다. 2. 연산자가 나오면 숫자 2개를 pop 해서 계산한다. 3. 계산한 결과(result) 를 다시 스택에 넣는다. 후위 표..

원형 큐 개념 👍🏻 원형 큐는 선형 큐와 마찬가지로 선입선출 형태의 데이터 구조이다. 선형 큐의 한계점을 해결하기 위해 구조화한 것으로, 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때, (rear+1) % 배열 사이즈 공식으로 OutOfBoundException 이 일어나지 않고 인덱스 0으로 순환하는 구조를 가진다. 선형 큐의 문제점 선형 큐는 데이터 삽입/삭제 시 메모리 낭비가 발생한다. 선형 큐의 인덱스는 항상 배열의 마지막 인덱스를 가리키고 있기 때문에, 앞쪽에서 dequeue 로 빈 공간이 발생하고 이를 활용할 수가 없다. 그렇다고 매번 빈 공간이 없도록 데이터를 앞당길 수도 없고... 원형 큐의 등장 선형 큐는 데이터를 가리키는 인덱스가 하나였지만, 원형 큐는 front, rear 로 두 ..

좌표 압축 💡 👍🏻 수의 범위가 매우 큰 상태에서 수의 값과 상관 없이 숫자의 대소 관계만 알면 될 때 이용하는 알고리즘이다. ✨ 수의 범위를 확 줄일 수 있다. 수의 값보다 크고 작은 순서가 중요하다. 좌표 압축 원리 좌표 압축은 정렬과 이분 탐색이 필요하다. 입력 받은 배열을 압축용 배열에 오름차순 정렬한다. (정렬 ⭐) 압축용 배열에서 중복 요소는 제거한다. (중복 제거 ⭐) 압축용 배열에 새로운 인덱스를 부여한다. (순서를 주는 것) 좌표 압축 예시 int [] arr = {2, 4, -10, 4, -9}; //오름차순 정렬 int [] arr_tmp = {-10, -9, 2, 4, 4}; //중복요소를 제거한다. {-10, 9, 2, 4} [0] [1] [2] [3] //원래 배열에 압축용 배열..

💡 👍🏻 [에라토스테네스의 체] 는 고대 그리스 수학자인 에라토스테네스가 만들어낸 소수를 판별하는 알고리즘이다. 마치 체를 가지고 수를 걸러내는 것 같아, '에라토스테네스의 채' 라고 부른다. 소수란 약수가 오로지 1인 수이다. 즉, 1을 제외한 수의 배수가 되는 수는 소수가 아니다. 소수를 대량으로 빠르고 정확하게 구할 때 이용한다. 지워지지 않은 수들이 소수이다. 에라토스테네스의 원리 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고 이후 하나 씩 지워가는 방법을 이용한다. 2부터 시작해서 특정 수의 배수에 해당되는 수를 모두 지운다. 2부터 시작해서 남은 수를 모두 출력한다. 🛠 예를 들어, 2부터 n까지의 수 중에서 소수를 구한다고 했을 때, 2는 소수니까 그대로 두고, n까지 순차..

유클리드 호제법 (GCD) 💡 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나이다. 호제법 = 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다. 명시적으로 기술된 알고리즘 중 가장 오래되었다고 알려져 있다. 원리 1️⃣ 2개의 자연수 a,b 에 대하여 a를 b로 나눈 나머지가 r이면 (단, a>b) , a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 2️⃣ 이 성질을 이용해 이번에는 b를 r로 나눈 나머지 r2 를 구하고, 다시 r을 r2 로 나눈 나머지를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수인 것이다. 접근방법 1️⃣ 반복문을 이용한 방법 2️⃣ 재귀를 이용한 방법 int GCD(int a, ..

상한가,하한가 구하기 💡 이진 탐색으로 상한가와 하한가를 구해서 원하는 숫자를 출력하자. - 백준 10816번- ‘중복 원수의 개수’ 를 알아내고 싶을 때, 중복 원소의 왼쪽 끝과 오른쪽 끝의 인덱스를 알아내서 계산하면 된다. 이진 탐색 개념을 이용하기에 배열은 사전 정렬 되어있어야 한다. 방법 찾으려는 값의 하한선, 상한선을 따로 구할 생각을 하자. 하한선은 찾으려는 값 이상의 값이 나타난 위치다. “이상” 이란 같거나 큰 수를 뜻한다. 상한선은 찾으려는 값의 초과 값이 나타난 위치다. “초과” 란 보다 큰 수를 뜻한다. 상한가, 하한가 예시 정렬된 배열에서 ‘숫자 10의 상한가, 하한가를 찾는다. (하한선은 최초 10 이 나오는 위치인 3, 상한선은 10을 넘어서는 최초 위치 6 이 나와야 한다.) ..

💡 👍🏻 Counting Sort 는 데이터를 서로 비교하는 정렬 알고리즘과 다르게, 데이터의 값을 카운팅하여 정렬하는 알고리즘이다. 쉽게 말하면 배열에 있는 값의 수를 카운팅해서 자리 찾아주는 알고리즘임. (내가 이해하기로 그럼) ✨ 카운팅 소트의 시간 복잡도는 O(n) 일반적인 정렬들의 알고리즘 시간 복잡도가 O(nlogn)인 것을 생각하면 속도가 매우 빠르다. 하지만, 수의 범위가 커지면 메모리를 많이 낭비하기 때문에 자주 사용하지 않는다. 카운팅 소트 원리 배열에서 max 값을 찾는다. 카운팅 배열 (max 값+1) 과 결과 배열 b 를 생성한다. 정렬할 배열의 값을 인덱스로 카운팅 배열에 카운팅한다 (counting++); 카운팅 배열을 직전 요소 더한 값으로 다시 저장한다. 정렬할 배열 값으로..

이진 탐색 💡 이진 탐색은 ‘정렬’ 되어 있는 배열에서 특정 값을 찾는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾으려는 대상 값 x와 비교한다. x가 중간 값보다 작으면 중간 값을 기준으로 좌측 데이터를 비교 x가 중간 값보다 크면 배열의 우측 데이터를 대상으로 다시 검색한다. 동일한 방법으로 다시 중간 값을 임의로 선택하고 비교한다. 이진 탐색 예시 ‘55’ 숫자를 찾아본다. {5, 24, 55, 67, 88, 92, 100} 1️⃣ 첫 번째 시도 먼저 가운데 임의의 값 67을 선택한다. 67 67 > 55 //두 값을 비교한다. = 중간 값 67 보다 작으므로 55은 67의 좌측에 존재함을 알 수 있다. 2️⃣ 두 번째 시도 {5, 24, 55} = 67의 좌측 배열 값을 대상으로 2..

백준 풀고 동생과 코드 리뷰 하던 중, 동생이 내가 푼 문제를 보고 "이거 비트마스킹? 그걸로 푸는거 아닌가?" 라고 해서 궁금해서 찾아본 비트마스킹의 정의. 몰랐는데 알고리즘 단골 문제 유형 중 하나인 것 같다...! 비트마스킹 (BitMasking) 비트마스킹 알고리즘 (2진수 표기법의 특징을 활용) * 비트마스킹 : 컴퓨터가 내부에서 모든 자료를 이진수로 표현하는 것을 이용해 정수의 * 이진수 표현을 자료구조로 쓰는 기법이다. * 더 빠른 수행시간, 더 간결한 코두, 더 적은 메모리 사용 효과를 볼 수 있다. 비트 연산자 & : 모든 비트를 AND 연산한다. (둘다 1이면 1, 아니면 0) * | : 모든 비트를 OR 연산한다. (둘다 0이면 0, 아니면 1) * ^ : 모든 비트를 XOR 연산한다..