분류 전체보기

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

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

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

이번에는 '세그먼트 트리(Segment Tree)'에 대해 알아보겠습니다. 세그먼트 트리는 코딩 테스트에서 자주 활용되는 자료 구조 중 하나이며, 세그먼트 트리의 개념과 문제 해결 방법을 이해하는 것은 코딩 테스트에서 도움이 됩니다. 세그먼트 트리의 개념 세그먼트 트리는 배열 형태의 데이터를 분할하여 구간 합, 최소값, 최대값 등을 빠르게 계산하기 위한 자료 구조입니다. 주로 배열의 구간에 대한 질의(Query)를 처리하는 데 사용됩니다. 세그먼트 트리는 완전 이진 트리 형태를 가지며, 각 노드가 해당 구간의 정보(합, 최소값 등)를 가지고 있습니다. 이러한 성질을 활용하여 원래 배열의 범위를 분할하고 각 구간에 대한 정보를 저장하므로써 질의 연산을 빠르게 수행할 수 있습니다. 세그먼트 트리 문제 접근 ..

이번에는 코딩 테스트에서 중요한 유형인 'Trees(트리)'에 대해 알아보겠습니다. 트리는 계층적인 구조를 가지며, 여러 개의 노드가 연결된 자료 구조입니다. 이번 글에서는 트리의 개념과 코딩 테스트에서 트리 문제를 접했을 때 어떻게 접근해야 하는지에 대해 자세히 알아보겠습니다. 트리의 개념 트리는 그래프 이론의 일부로, 계층적인 구조를 가진 비선형 자료 구조입니다. 그래프와 마찬가지로 노드(Node)와 간선(Edge)으로 이루어져 있지만, 다음과 같은 조건을 만족합니다. 사이클이 없다: 임의의 두 노드 사이를 연결하는 경로는 유일합니다. 연결되어 있다: 임의의 두 노드 사이를 연결하는 경로가 항상 존재합니다. 계층적 관계: 하나의 노드(루트)를 기준으로 다른 모든 노드들은 부모-자식 관계로 연결됩니다...

이번에는 코딩 테스트에서 중요한 유형인 'Number Theory(정수론)'에 대해 알아보겠습니다. 정수론은 정수와 그 연산에 대한 학문으로, 수학적인 개념과 원리를 활용하여 문제를 해결하는 방법입니다. 코딩 테스트에서도 자주 출제되는 유형 중 하나이며, 수학적 사고력과 논리적 접근이 요구됩니다. 정수론의 개념 정수론은 다양한 개념과 성질을 포함하고 있으며, 주요한 개념들을 소개하겠습니다. 소수(Prime Number): 1과 자기 자신으로만 나누어지는 양의 정수입니다. 소수 판별, 소인수분해 등의 문제에서 활용됩니다. 최대공약수(GCD): 두 수의 공통된 약수 중 가장 큰 수를 의미합니다. 유클리드 호제법을 사용하여 계산할 수 있습니다. 최소공배수(LCM): 두 수의 공통된 배수 중 가장 작은 수를 의..

이번에는 코딩 테스트에서 중요한 유형인 'Geometry(기하학)'에 대해 알아보겠습니다. 기하학은 공간의 형태와 크기, 상대적인 위치 등을 다루는 수학의 한 분야입니다. 기하학적 문제는 프로그래밍에서 다양한 분야에 활용되며, 복잡한 데이터를 다루고 분석하는 데 필요한 도구를 제공합니다. 기하학의 개념 기하학은 점, 선, 면 등의 도형과 그들 사이의 관계를 연구하는 수학 분야입니다. 프로그래밍에서 기하학적 문제는 주어진 조건과 요구사항을 이해하여 도형을 표현하고 연산하는 것을 요구합니다. 예를 들어 점과 선분의 거리 계산, 세 점이 이루는 각도 구하기, 두 직선이 교차하는지 판별하기 등이 있습니다. 기하학 문제 접근법 좌표 기반 접근: 평면 상에서 좌표를 사용하여 문제를 해결하는 경우가 많습니다. 좌표계..

오늘은 코딩 테스트에서 중요한 유형 중 하나인 'Sorting(정렬)'에 대해 이야기해보려 합니다. 정렬 알고리즘은 주어진 데이터를 일정한 순서대로 배열하는 알고리즘입니다. 정렬이란? 정렬은 데이터를 일정한 순서로 재배치하는 작업을 의미합니다. 주어진 데이터를 크기, 알파벳 순서 등의 기준에 따라 오름차순(ascending order)이나 내림차순(descending order)으로 정리할 수 있습니다. 일반적으로 사용되는 몇 가지 정렬 알고리즘과 관련된 개념들을 소개하겠습니다. 버블 정렬(Bubble Sort): 인접한 두 원소를 비교하여 필요에 따라 위치를 교환하는 방식으로 동작합니다. 반복적인 비교와 교환을 통해 가장 큰 원소가 마지막으로 이동하게 됩니다. 선택 정렬(Selection Sort): ..