분류 전체보기

제1회 임스의 메이플컵 (The 1st lms0806's Maple Cup) · Arena #6 www.acmicpc.net 알고리즘 대회 카테고리에서는 참가했던 알고리즘 대회마다 풀이할 수 있는 한에서 문제 풀이를 진행해보고자 합니다. :0 이번 글에서는 가장 먼저 참가했었던 "제1회 임스의 메이플컵 (The 1st lms0806's Maple Cup) · Arena #6" 대회에 대한 문제를 다뤄보겠습니다. A번 : 임스의 메이플컵 29790번: 임스의 메이플컵 첫 번째 줄에 메이플컵에 지원한 지원자의 문제 해결 개수 $N$과 유니온 레벨 $U$, 최고 레벨 $L$이 공백을 사이에 두고 주어진다. $(1 \le N \le 130\,000;$ $1 \le U \le 12\,500;$ $1 \le L \..

이번에는 IT 기업 코딩 테스트에서 가끔씩 등장하곤 하는 유형 중 하나인 "위상 정렬"에 대해 이야기해보려고 합니다. 위상 정렬은 그래프 이론의 개념으로, 방향 그래프에서 각 노드들의 선행 순서를 지켜주는 정렬 방법입니다. 위상 정렬이란? 위상 정렬은 일종의 선후 관계를 가진 작업들을 순서에 맞게 나열하는 알고리즘입니다. 주로 작업 스케줄링, 종속성 관리, 컴파일러 등 다양한 분야에서 활용됩니다. 간단하게 설명하자면, 방향 그래프(Directed Graph)에서 각 노드들 사이의 선후 관계가 주어질 때, 모든 노드를 방향성을 지켜 나열하는 것을 의미합니다. 이때, 그래프 내에 사이클(Cycle)이 존재하면 위상 정렬은 불가능합니다. 코딩 테스트에서의 위상 정렬 문제 해결 전략 진입 차수(In-degree..

이번 글에서는 최소 스패닝 트리(Minimum Spanning Tree)에 대한 개념과 코딩 테스트에서 이 문제를 해결하는 방법에 대해 알아보겠습니다. 최소 스패닝 트리는 그래프 이론의 주요 주제 중 하나입니다. 최소 스패닝 트리(Minimum Spanning Tree)의 개념 최소 스패닝 트리란, 가중치가 있는 연결 그래프에서 모든 정점을 가장 적은 비용으로 연결하는 부분 그래프입니다. 주어진 그래프의 모든 정점을 포함하면서 사이클이 없고, 가중치의 합이 최소인 부분 그래프를 찾는 것이 목표입니다. 최소 스패닝 트리에 사용되는 알고리즘 크루스칼 알고리즘: 간선들을 가중치 순으로 정렬한 후, 사이클을 형성하지 않으면서 간선을 추가하여 최소 스패닝 트리를 만듭니다. 모든 간선을 가중치 순으로 정렬합니다. ..

배낭 문제(Knapsack Problem)의 개념 배낭 문제란, 제한된 용량을 가진 배낭에 최대 가치를 담을 수 있는 물건들의 조합을 찾는 문제입니다. 각각의 물건은 가치와 부피(또는 무게)를 가지고 있으며, 우리의 목표는 주어진 용량 내에서 최대 가치를 얻을 수 있는 조합을 찾는 것입니다. 0/1 배낭 문제: 가장 기본적인 형태인 0/1 배낭 문제에서는 각각의 물건은 단 하나씩만 선택할 수 있습니다. 즉, 해당 물건을 전부 넣거나 아예 넣지 않거나 둘 중 하나만 선택할 수 있습니다. 코딩 테스트에서의 배낭 문제 접근 방법 일반적으로 0/1 배낭 문제를 해결하기 위해서 아래 일련의 단계를 거치는 다이나믹 프로그래밍(DP) 기법을 사용합니다. DP 테이블 초기화: DP 테이블은 (물건 개수+1) x (배낭..

이번 글에서는 소수 판정에 대한 개념과 코딩 테스트에서 소수 판정 문제를 해결하는 방법에 대해 알아보겠습니다. 소수는 많은 알고리즘 문제에서 자주 등장하는 중요한 주제 중 하나이므로, 이 글을 통해 여러분의 코딩 실력을 향상시킬 수 있기를 바랍니다. 소수의 개념 소수는 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)을 구현하기 위해서는 값을 음수로 변환하여 활용하는 방법도 있습니다. 코딩 테스트에서의 우선순위 큐 문제 접근 방법..