분류 전체보기

이번 글에서는 소수 판정에 대한 개념과 코딩 테스트에서 소수 판정 문제를 해결하는 방법에 대해 알아보겠습니다. 소수는 많은 알고리즘 문제에서 자주 등장하는 중요한 주제 중 하나이므로, 이 글을 통해 여러분의 코딩 실력을 향상시킬 수 있기를 바랍니다. 소수의 개념 소수는 1과 자기 자신만으로 나누어 떨어지는 수입니다. 예를 들어, 2, 3, 5, 7은 모두 소수입니다. 반면에 4, 6, 8은 다른 수로도 나누어지므로 소수가 아닙니다. 코딩 테스트에서의 소수 판정 문제 접근 방법 가장 간단하고 직관적인 방법으로는 대상 숫자 n을 [2, √n] 범위의 모든 수로 나눠보는 것입니다. 만약 어떤 수 i로 n이 나누어진다면 n은 소수가 아닙니다. 이 방법은 시간 복잡도 O(√n)으로 비교적 간단하게 구현할 수 있습..

이번에는 꼭 알아야하는 머신러닝 알고리즘 중 하나인 "선형 회귀(Linear Regression)"에 대해 알아보려고 합니다. 선형 회귀는 데이터의 경향성을 가장 잘 설명할 수 있는 직선 형태의 모델을 찾는 기법으로, 여러분들을 위해 자세한 내용을 소개하겠습니다. 선형 회귀의 개념선형 회귀는 종속 변수와 한 개 이상의 독립 변수 간의 관계를 모델링하는 방법입니다. 주어진 데이터를 기반으로 최적의 직선을 찾아 예측 및 분석에 활용합니다. 선형 회귀는 단순 선형 회귀(Simple Linear Regression)와 다중 선형 회귀(Multiple Linear Regression)로 나뉩니다. 단순 선형 회귀: 단순 선형 회귀(Simple Linear Regression)는 종속 변수(Y)와 한 개의 독립 변..

투 포인터의 개념 투 포인터는 배열이나 리스트에서 두 개의 포인터(인덱스)를 활용하여 원하는 결과를 얻기 위한 알고리즘입니다. 주로 정렬된 배열이나 리스트에서 합, 차, 거리 등의 연산을 수행할 때 사용됩니다. 코딩 테스트에서의 투 포인터 문제 접근 방법 투 포인터 문제를 해결하기 위한 접근 방법은 다음과 같습니다. 시작점과 끝점 설정: 문제의 조건에 맞게 시작점과 끝점을 설정합니다. 일반적으로 시작점은 배열/리스트의 첫 번째 요소를 가리키고, 끝점은 마지막 요소를 가리킵니다. 조건 확인 및 이동: 두 포인터 사이의 조건을 확인하고 필요에 따라 각각의 포인터를 이동시킵니다. 예를 들어, 합이나 차가 주어진 값보다 큰 경우 한쪽 포인터를 왼쪽으로 이동시켜 값을 줄여나갑니다. 결과 도출: 원하는 결과가 나올..

우선순위 큐란? 우선순위 큐는 데이터들이 우선순위에 따라 처리되는 자료구조입니다. 각 요소는 우선순위 값과 함께 저장되며, 우선순위 값에 따라 요소들이 정렬됩니다. 일반적으로 작은 값이 높은 우선순위를 가지게 됩니다. 우선순위 큐를 사용하면 데이터를 삽입하거나 삭제할 때 항상 가장 우선순위가 높은(또는 낮은) 요소를 빠르게 접근할 수 있습니다. 이러한 특성으로 인해 다양한 문제에서 유용하게 활용됩니다. 일반적으로 파이썬에서는 heapq 모듈을 활용하여 간편하게 우선순위 큐를 구현할 수 있습니다. heapq 모듈은 최소 힙(min heap)의 형태로 구현되어 있으며, 최대 힙(max heap)을 구현하기 위해서는 값을 음수로 변환하여 활용하는 방법도 있습니다. 코딩 테스트에서의 우선순위 큐 문제 접근 방법..

이번에는 코딩 테스트에서 자주 등장하는 유형인 "분할 정복(Divide and Conquer)"에 대해 알아보려고 합니다. 분할 정복의 개념 분할 정복은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법입니다. 주어진 문제를 해결하기 위해서는 세 가지 단계로 나눌 수 있습니다. 분할(Divide): 주어진 문제를 작은 부분 문제로 분할합니다. 정복(Conquer): 각각의 작은 부분 문제를 재귀적으로 해결합니다. 통합(Combine): 작은 부분 문제들의 결과를 결합하여 원래의 큰 문제에 대한 최종 해답을 얻습니다. 이러한 단계들을 반복하여 원래의 큰 문제를 점차적으로 해결해 나갑니다. 코딩 테스트에서의 분할 정복 문제 접근 방법 기저 조건(Base Case) 설정: 재귀적인 호출을 멈추기 위한 기저 조..

이번에는 자주 사용되지는 않지만, 알아두면 좋을 법한 유형 중 하나인 분리 집합(Disjoint Set)에 대해 이야기해보려고 해요.분리 집합은 원소들을 서로 중복되지 않게 여러 개의 집합으로 나누고, 각각의 집합들에 대해 합집합(union)과 찾는(find) 연산을 수행하는 자료구조입니다.이 글에서는 분리 집합의 개념과 코딩 테스트에서 분리 집합 문제를 접하게 되었을 때, 어떻게 접근해야 하는지에 대해 간단히 알아보도록 하죠. ✨ 분리 집합의 개념분리 집합은 서로 중복되지 않는 부분 집합들로 나누어진 원소들의 데이터 구조입니다. 각각의 부분 집합은 대표 원소를 가지며, 같은 부분 집합에 속한 원소들은 같은 대표 원소를 공유해요. (당연한 얘기죠.)예를 들어서 {1, 2, 3}과 {4, 5}라는 두 개의..

이번에는 코딩 테스트에서 알면 유용한 유형 중 하나인 백트래킹에 대해 이야기해보려고 합니다. 백트래킹은 문제의 해를 찾는 과정에서 가능한 모든 후보들을 탐색하면서 해를 찾아가는 알고리즘 기법입니다. 이 글에서는 백트래킹의 개념과 코딩 테스트에서 백트래킹 문제를 접했을 때 어떻게 접근해야 하는지에 대해 자세히 알아보겠습니다. 백트래킹의 개념 백트래킹은 "역추적"이라는 뜻을 가지고 있으며, 주어진 문제의 조건을 만족하는 해를 찾기 위해 탐색하다가 조건을 만족하지 않으면 되돌아가서 다른 경우를 탐색하는 방법입니다. 이러한 방식으로 가능한 모든 경우를 조사함으로써 최적의 해를 찾아낼 수 있습니다. 백트래킹은 대부분 재귀 함수로 구현되며, 일반적으로 다음과 같은 단계로 진행됩니다. 문제의 조건과 제약 사항을 정의..

이번에는 코딩 테스트에서 종종 유용하게 사용되는 다익스트라(Dijkstra) 알고리즘에 대해 이야기하려고 합니다. 다익스트라 알고리즘은 최단 경로 문제를 해결하는 데 사용되며, 가중치가 있는 그래프에서 시작 정점으로부터 모든 정점까지의 최단 경로를 찾아줍니다. 다익스트라 알고리즘이란? 다익스트라 알고리즘은 하나의 시작 정점에서 모든 정점까지의 최단 거리를 구하는 그리디한 방법입니다. 이를 위해 우선순위 큐(힙)을 활용하여 현재까지의 최단 거리 정보를 업데이트합니다. 다익스트라 알고리즘의 접근 방법은 다음과 같습니다. 시작 정점을 선택하고 해당 정점까지의 거리를 0으로 초기화합니다. 나머지 정점들까지의 거리를 무한대로 초기화합니다. 현재 선택된 정점과 연결된 모든 인접한 정점들에 대해 최소 거리 갱신을 시..