분류 전체보기

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

비트마스크(Bitmask)란? 비트마스크는 컴퓨터 메모리의 이진수 표현을 활용하여 집합을 나타내는 방식입니다. 각 원소를 이진수의 한 자리로 대응시켜 해당 원소의 포함 여부를 나타냅니다. 따라서, 집합 연산을 비트 연산으로 처리할 수 있어 간결하고 빠른 알고리즘 구현이 가능합니다. 비트마스크를 사용하기 위해 알아야 할 주요 개념은 다음과 같습니다. 이진수 표현: 숫자를 이진수로 변환하여 각 자릿수가 원소에 대응되도록 합니다. AND(&), OR(|), XOR(^): 비트 연산자들을 활용하여 집합 연산(교집합, 합집합, 차집합 등)을 수행합니다. 시프트(Shift): 왼쪽 시프트() 연산자를 사용하여 비트를 이동시킵니다. 부분집합 생성: 모든 부분집합을 생성하거나, 주어진 조건에 맞는 부분집합만 생성할 수..

이번에는 코딩 테스트에서 반드시 알아야 하는 주제 중 하나인 깊이 우선 탐색(DFS, Depth-First Search)에 대해 이야기하려고 합니다. DFS는 그래프 탐색 방법 중 하나로, 시작 노드에서부터 가능한 한 깊숙히 들어가며 그래프를 탐색하는 방식입니다. DFS(Depth-First Search)란? DFS는 그래프 탐색 알고리즘 중 하나로, 깊이를 우선으로 탐색하는 방식입니다. 시작 노드에서부터 한 경로를 따라 더 이상 갈 수 없을 때까지 탐색하고, 다시 돌아와서 다른 경로를 탐색합니다. 이 과정은 스택(Stack) 또는 재귀 함수를 통해 구현할 수 있습니다. DFS에서 사용되는 주요 개념은 다음과 같습니다. 스택(Stack): DFS는 스택 자료구조를 활용하여 현재 위치에서 갈 수 있는 경로..

조합론(Combinatorics)이란? 조합론은 원소들의 집합에서 부분집합을 선택하거나 원소들을 순서에 따라 배열하는 등의 연산을 다루는 수학 분야입니다. 이를 통해 가능한 경우의 수, 순열, 조합 등 다양한 문제를 해결할 수 있습니다. 조합론에서 자주 사용되는 개념들은 다음과 같습니다. 팩토리얼(Factorial): 양의 정수 n에 대해서 n!은 1부터 n까지 모든 양의 정수를 곱한 값입니다. 순열(Permutation): 서로 다른 n개 중에서 r개를 선택하여 나열하는 경우의 수를 계산합니다. (순서가 중요) 조합(Combination): 서로 다른 n개 중에서 r개를 선택하는 경우의 수를 계산합니다. (순서가 중요하지 않음) 이항 계수(Binomial Coefficient): 주어진 크기 n과 k에..

오늘은 코딩 테스트에서 알고 가면 좋은 유형인 'Prefix Sum(누적 합)'에 대해 이야기해보려고 합니다. 누적 합(Prefix Sum)이란? 누적 합은 배열의 원소들을 순차적으로 더한 값을 저장하는 배열로, 각 원소는 이전 원소까지의 모든 원소의 합을 나타냅니다. 이를 통해 구간합, 구간 평균 등 다양한 연산을 빠르게 수행할 수 있습니다. 누적 합 문제 접근 방법 코딩 테스트에서는 누적 합 개념이 종종 활용됩니다. 예를 들어, 주어진 리스트에서 연속된 부분 리스트 중 최대 / 최소 / 평균 값을 찾기 주어진 리스트에서 특정 값보다 크거나 작은 부분 리스트 개수 세기 등 위와 같은 문제들은 일반적으로 반복문으로 해결할 경우 시간 복잡도가 O(N^2)이 됩니다. 하지만, 누적 합을 활용하면 시간 복잡도..

이번에는 코딩 테스트에서 꼭 알아야하는 유형 중 하나인 BFS(Breadth-First Search)에 대해 알아보겠습니다. BFS는 그래프 탐색 알고리즘 중 하나로, 너비 우선으로 탐색을 수행하는 방법입니다. 이전 그래프 이론 및 탐색 포스팅에서 간략하게 설명하였는데, 이번 글에서는 BFS의 개념과 코딩 테스트에서 BFS 문제를 접했을 때 어떻게 접근해야 하는지에 대해 자세하게 설명하도록 하겠습니다. BFS란? BFS는 그래프 탐색 방법 중 하나로, 시작 정점에서부터 인접한 정점들을 먼저 모두 방문한 후, 다음 단계의 인접 정점들을 차례대로 방문하는 방식입니다. 이러한 너비 우선 탐색은 큐(Queue) 자료구조를 활용하여 구현됩니다. BFS의 동작 원리는 다음과 같습니다. 시작 정점을 큐에 넣고 방문 ..

이번에는 코딩 테스트에서 꼭 알아야하는 유형 중 하나인 이분 탐색(Binary Search)에 대해 알아보겠습니다. 이분 탐색은 정렬된 배열 또는 리스트에서 원하는 값을 찾는 데에 사용되는 강력한 알고리즘입니다. 이분 탐색은 매우 효율적이며, O(logN)의 시간 복잡도를 가지므로 많은 문제에서 활용됩니다. 이분 탐색(Binary Search)의 개념 이분 탐색은 주어진 정렬된 배열(또는 리스트)에서 중간값을 기준으로 찾고자 하는 값이 왼쪽 부분 배열에 위치하는지 오른쪽 부분 배열에 위치하는지를 판단하여, 찾고자 하는 값이 있을 범위를 반으로 줄여가며 검색합니다. 이 과정을 반복하여 최종적으로 원하는 값을 찾게 됩니다. 일반적인 이분 탐색의 과정은 다음과 같습니다. 시작 인덱스(left)와 끝 인덱스(r..

이번에는 애드 혹(Ad Hoc) 유형의 문제를 해결하는 방법과 코딩 테스트에서 이러한 문제에 접근하는 방법에 대해 설명하겠습니다. 애드 혹(Ad Hoc)이란?애드 혹은 "특정 상황에 맞춰서"라는 뜻을 가지고 있습니다. 알고리즘 분류 중에서도 일종의 잡다한 문제 유형으로 분류됩니다. 이러한 문제들은 주로 직관과 간단한 로직을 활용하여 해결할 수 있으며, 복잡한 자료구조나 알고리즘이 필요하지 않은 경우가 많습니다. 애드 혹 문제 해결 전략애드 혹 유형의 문제는 주로 실생활에서 우리가 자주 마주치는 상황과 유사하거나 실제 데이터에 적용할 수 있는 경우가 많습니다. 따라서 일상적인 경험과 직관을 활용하여 문제에 접근하면 도움이 됩니다.코딩 테스트에서 애드 혹 유형의 문제를 효율적으로 해결하기 위해서는 다음과 같..