전체 글

[python] 재귀 알고리즘 - 최대공약수 GCD - 유클리드 호제법

안녕하세요. 이번 포스팅은 재귀 알고리즘에 대해서 다뤄보았습니다. 재귀는 다양한 알고리즘에서 활용이 되는데요. 특히, 재귀를 모르고 지나친다면 다른 재귀에 기반하여 풀 수 있는 고등 알고리즘에 대해 알 수 없게 된다는 점이 있습니다.  재귀로 쉽게 풀 수 있는 대표적인 알고리즘 중 하나인 최대공약수 찾는 알고리즘에 대해서 다뤄보겠습니다. 예를 들어 9 x 24 인 직사각형이 있다고 가정하겠습니다. 쉽게 범용적으로 풀 수 있는 방법 중 하나는 다음처럼 정사각형으로 분할이 될 때까지 쪼개는 방법이 있는데요. 로직 자체는 간다합니다.위 첫번째 그림처럼 9 x 24 크기의 직사각형에서 짧은 변의 길이인 9를 한 변으로 하는 정사각형으로 나눠줍니다. 그러면 2개의 9x9 정사각형이 만들..

투 포인터 (two pointer) 알고리즘이란?

투 포인터란? '투 포인터'라는 기법은 문자열 string 또는 배열 array 기반의 알고리즘 문제에서 자주 사용할 수 있는 효과적인 기법입니다. 구체적으로 투 포인터도 여러 가지 방식이 있지만, 대개는 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략으로 볼 수 있습니다. 알고리즘 문제를 풀 때, 일반적인 반복문 접근 또는 브루트 포스 방식을 활용하다 보면 타임아웃에 직면하게 되는 경우가 종종 있습니다. 투 포인터 방식을 활용하면 복잡도를 한단계 낮출 수 있습니다. ==> $O(N^k)$ --> $O(N^{k-1})$ 투 포인터는 크게 두가지 방법으로 응용할 수 있습니다. 앞쪽 첫번째에서 시작하는 포인터 & 뒤쪽 끝에서 시작하는 포인터 빠른 포인터가 느린 포인터..

[leetcode 42] Trapping Rain Water - hard

오늘은 리트코드(leetcode) 42번 문제 trapping rain water에 관해 풀어보겠습니다. (링크: https://leetcode.com/problems/trapping-rain-water/description/) 문제는 높이를 입력받아 비 온 뒤 얼마나 많은 물이 쌓일 수 있는지 계산을 요구하는 문제입니다. 이 문제는 높이와 너비 모든 공간을 차례대로 살펴보면서 풀어나간다면 $O(n^2)$만큼의 시간 복잡도로 풀이가 가능합니다. 하지만 시간 복잡도가 높기 때문에, 더 효율적인 풀이를 찾는 것이 권장됩니다. 풀이: 투 포인터 활용 투 포인터를 활용하면 $O(n)$의 시간 복잡도로 문제를 풀 수 있다고 생각했습니다. 우선 다음 그림을 보겠습니다. 위 그림에서 주목할 부분은 '가장 높은 막대..

[AWS] 클라우드 컴퓨팅이란? - 서버, 네트워크, 클라이언트

AWS Cloud Practitioner 자격증 취득 공부 기록용 Cloud Service 기본적으로 클라우드 서비스에 대해 알기 위해서 우리는 클라이언트, 네트워크, 서버 개념에 대해 간단하게 알아야 할 필요가 있다. 네트워크는 클라이언트 (나)와 서버 (목적지)를 연결해주는 역할을 한다. 일상 생활에서 비유해보자면, 네트워크는 우체통 역할을 한다고 할 수 있다. 내가 특정 자원을 사용하기 위해 서버에 요청한다면, 매번 직접 가는 것보다 우체통을 통한 접근이 훨씬 효율적이라고 볼 수 있다. 기본적으로 클라이언트와 서버는 ip 주소를 갖고 있으며, 네트워크는 이를 이용해 서로를 연결해준다. 서버 구성 요소 서버는 다음과 같은 요소로 구성이 되어 있다. compute: CPU memory: RAM stor..

[백준 19532] 수학은 비대면 강의입니다 / Cramer's Rule / 브루트 포스

이번에는 백준 브루트 포스 문제 중 연립방정식을 풀어야 하는 '수학은 비대면강의입니다'를 풀어보자. 이 문제는 크게 두 가지 방법으로 풀 수 있다. 브루트 포스 (for문 반복문 활용) Cramer 공식 (수학 지식 필요) 1번은 모든 시도를 다 해보는 것이기 때문에 우리가 쉽게 생각할 수 있는 부분이라고 생각이 들고 2번은 수없이 많은 수학 문제를 풀면서 얻은 내공 또는 선형대수학을 공부하던 시절을 기억해야 하기에 비전공자라면 쉽게 떠오르지 않을 수 있다. 하지만 2번이 더 효과적이라는 것!! 그렇지만 브루트 포스 관점에서 1번이 오히려 백준이 요구하는 정답에 가깝지 않나 생각이 든다. 방법 1: 브루트 포스 브루트 포스는 생각보다 간단하다. 모든 값은 -999와 999사이의 정수 값으로 할당이 되고,..

[SQL] 프로그래머스 특정 물고기를 잡은 총 수 구하기 - 조인 & 상관중첩질의

프로그래머스 Lv1 다음 문제를 풀어보자. FISH_INFO와 그리고 FISH_NAME_INFO 두 개의 테이블이 존재하고, join을 활용하면 쉽게 풀리는 문제이다. 하지만 단순하게 하나의 SQL 방법에 의존하게 되면, 향후 복잡한 쿼리를 사용할 때 제한적인 생각에 갇힐 수도 있다. 따라서 상관 중첩 질의를 이용해서도 풀이를 작성해놨다. (상관 중첩 질의 내용 포스팅은 여기로) Join 문을 이용한 코드 SELECT count(*) AS FISH_COUNT FROM fish_info as f INNER JOIN fish_name_info as n ON f.fish_type = n.fish_type WHERE n.fish_name in ('BASS', 'SNAPPER') ; 위 코드는 단순하게 전체 결과..

[백준 24313] 점근적 표기 1 문제 풀이 & 해설 - 파이썬

백준 24313 문제에 대해 풀어보겠습니다. 이 문제는 알고리즘 수행 시간에 관한 문제로 "점근적 표기 (asymptotic notation)"에 관해 알고 있는지를 묻고 있습니다. Background: 점근적 표기 점근적 표기에 대해 간략히 설명을 하자면, Big-O를 계산할 때 입력값의 크기에 따라 함수가 얼마나 빨리 커지는지 알아볼 때 중요하지 않은 항과 상수 계수를 제거하면서 이해를 방해하는 불필요한 부분을 없앤 표기법이라고 볼 수 있습니다. 즉, 간략한 예로 $ y = 0.0006n^3 - 1000 $라고 했을 때, $O(y)=n^3$ 가 되는 반면에, $ x = 1000n^2 + 1000 $의 Big O는 $O(x)=n^2$ 가 되기 마련입니다. 따라서 y의 수행시간이 x보다 더 크다고 할 수..

[python] 등차수열과 등차수열의 합

알고리즘 및 코딩 테스트를 진행하다보면, 이따금 수학적 공식을 알고 있다면 생각보다 쉽게 풀리는 문제들이 있습니다. 수많은 공식들을 모두 외울 수도 없지만, 기본적인 내용은 짚고 넘어가면 도움이 될 수 있습니다. 그 중에서도 오늘은 등차수열에 관해 다뤄보려고 합니다. 등차수열의 기본 공식: n 번째 항 구하기 등차수열에서 n번째 항을 구하는 공식은 다음과 같습니다. $$ a_n = a_1 + (n-1)d $$ 여기서 각 기호는 다음을 의미합니다. $a_n$: $n$번째 항 $a_1$: 첫번째 항 $d$: 공차 $n$: 항의 순서 이 공식은 등차수열의 어느 항이든지 첫 번째 항과 그 항의 순서를 통해 계산할 수 있게 해줍니다. 등차수열의 기본 공식은 주로 수열의 특정 항을 찾을 때 사용되는데, 간단..