코딩테스트

투 포인터 (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)$의 시간 복잡도로 문제를 풀 수 있다고 생각했습니다. 우선 다음 그림을 보겠습니다. 위 그림에서 주목할 부분은 '가장 높은 막대..

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

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

[백준 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$: 항의 순서 이 공식은 등차수열의 어느 항이든지 첫 번째 항과 그 항의 순서를 통해 계산할 수 있게 해줍니다. 등차수열의 기본 공식은 주로 수열의 특정 항을 찾을 때 사용되는데, 간단..

[SQL] 조건에 부합하는 중고거래 댓글 조회 (프로그래머스)

프로그래머스 SQL LV1 문제중 가장 질문 게시판이 핫한 문제중 하나를 들고 와봤다. 이 문제는 두 테이블 (게시판 & 댓글)을 활용하여 쿼리를 작성하는 전형적인 join 과 관련된 문제이다. 이 문제는 DATE 형태만 제대로 작성하면 문제없이 원하는 결과물을 만들 수 있다. 올바른 DATE 포맷 사용하기 -> DATE_FORMAT() 함수 활용 SELECT b.TITLE, b.BOARD_ID, r.REPLY_ID, r.WRITER_ID, r.CONTENTS, DATE_FORMAT(r.CREATED_DATE, '%Y-%m-%d') AS CREATED_DATE FROM USED_GOODS_BOARD b INNER JOIN USED_GOODS_REPLY r ON b.BOARD_ID = r.BOARD_ID ..

[백준 9506] 약수 합 - 파이썬

백준 9506번 문제는 약수들의 합을 구해 완전수 (perfect number)인지 아닌지를 판별하는 문제입니다. 저는 다음과 같이 풀었습니다. while 문으로 exit (-1)전까지 입력을 받습니다. 1부터 n까지 for문을 돌면서, 나머지가 없는 즉, 모든 약수 (factor)를 리스트에 기록합니다. 약수의 합이 입력 값(n)과 같은지 확인하고 맞다면 형식에 맞춰 출력을 진행 if __name__ == '__main__': while True: n = int(input()) result = [] if n == -1: break else: for i in range(1, n): if n % i == 0: result.append(i) if n == sum(result): result = list(ma..

[백준 11005] 진법 변환 2 - 파이썬

백준 11005번은 '주어진 10진법 수 N을 사용자가 지정한 진법 B로 변환하는 알고리즘'을 만드는 문제입니다. 원리만 이해하면 생각보다 간단하게 풀 수 있습니다. 간단한 예시를 통해 이해하고 답을 보겠습니다. 예시 10진수 10을 2진수로 변환하는 경우: N = 10, B = 2 10진수 -> B진법 변환은 나머지를 기록해둘 필요가 있습니다. 또한 10진수 값 N 을 B로 나눴을 때 몫을 기억해둘 필요가 있습니다. 지속적으로 업데이트 해주어야 합니다. 10 % 2 = 0 --> 나머지 = "0" N // B : 10 // 2 = 5 --> 몫 = "5" N = 5 (i.e. N = N // B) 5 % 2 = 1 --> 나머지 = "1" N // B: 5 // 2 = 2 --> 몫 = "2" 2 % ..