IT/알고리즘

이분 탐색(Binary Search)은 코딩 테스트에서 많이 등장하는 알고리즘 중 하나이다.탐색 알고리즘 중 가장 기본적인 알고리즘으로, 특정 값을 빠르게 찾는 로직이다.오늘은 이분 탐색에 대해 정리해보도록 하겠다. 이분 탐색이란? 이분 탐색(Binary Search): 정렬된 배열에서 탐색 범위를 절반씩 줄여나가면서 특정 값을 찾는 알고리즘 이분 탐색 알고리즘의 중요한 포인트는 정렬된 배열이 필요하다는 점이다.왜냐하면 이분 탐색은 데이터가 정렬되었다는 가정 하에 동작하기 때문이다. 그렇다면 이분 탐색의 알고리즘이 어떻게 동작하는지 살펴보도록 하자.   이분 탐색의 원리 이분 탐색을 하기 위해서는 left, right, mid 3개의 위치값이 필요하다.이분 탐색의 알고리즘은 다음과 같이 동작한다. ① 초..

그리디 알고리즘은 각 단계에서 그 순간이 최선이라고 생각하며 선택하는 방식이다.겉보기엔 간단하고 직관적이지만 항상 최적의 해를 보장하지는 않는다.이번 포스터에선 그리디 알고리즘의 개념과 특징, 그리고 예시를 통해 알아보도록 하겠다.  그리디 알고리즘이란 무엇인가 그리디(Greedy): 문제를 해결할 때 각 단계에서 가장 최선이라고 생각되는 선택을 함으로써 전체 해를 구하는 방식  그리디를 사용하는 이유 그리디 알고리즘을 사용하면 많은 이점이 있습니다.완전 탐색이 아닌, 최적의 해를 구하는 성질에 의한 경우만 탐색하면 되기 때문입니다.  구현이 간단하고 빠름그리디 알고리즘은 성질에 따라 로직을 구현하면 되기 때문에 다른 알고리즘보다 구현하기 쉽다.  계산 속도가 빠름전체 경우가 아닌, 이미 성질에 의해 정..

비트마스크는 주어진 문제를 효율적으로 해결하기 위한 강력한 도구로, 특히 상태를 간단하게 표현하거나 부분 집합을 다룰 때 유용하다. 코딩 테스트에서는 메모리와 연산 시간을 절약할 수 있어 많이 활용되며, 비트 연산의 기본 개념만 이해해도 문제 해결에 큰 도움이 된다. 이번 글에서는 비트마스크의 기본 원리와 활용 예제를 통해 그 응용법을 살펴보겠다.  비트마스크(Bitmask)란? 비트 마스크: 비트 연산을 사용하여 데이터를 효율적으로 처리하는 기법 보통 상태를 표현하거나 조작할 때 유용하며, 특히 메모리를 절약하고 빠른 계산을 필요로 하는 상황에 유용하다. 이진수의 각 비트를 이용하여 여러 상태를 표현한다. 그래서 int형 value 하나로 32개의 Boolean 상태를 표현할 수 있다.이러한 구조를 통..

깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)은 그래프 탐색에서 자주 사용되는 기본적인 알고리즘이다.DFS는 한 노드의 끝까지 탐색한 후 돌아오는 방식이고, BFS는 가까운 노드부터 차례로 탐색해 나가는 방식이다.오늘은 DFS와 BFS의 동작 원리와 구현 방법, 그리고 각각의 특징과 활용 사례를 알아보도록 하겠다. 깊이 우선 탐색(DFS) DFS: 가능한 깊은 경로를 따라 탐색하다가 더 이상 깊이 갈 수 없을 때 뒤로 돌아가서 다른 경로를 찾는 방식stack 혹은 재귀 함수를 통해 구현할 수 있다.  DFS 응용탐색 경로: 미로 찾기 및 퍼즐 문제 등에서 특정 목표 지점에 도달하는 경로 탐색백트래킹 문제: 조합, 순열 생성 등에서 백트래킹 기법과 함께 활용사이클 탐지: 그래프에서 사이클이 존재하는지..

그래프(Graph)는 노드와 간선으로 이루어진 자료구조로, 객체 간의 관계를 표현하며 다양한 응용 분야에서 사용된다. 주로 탐색 알고리즘에는 BFS, DFS가 있고, 최단 경로와 최소 신장 트리 등 다양한 그래프 알고리즘에 활용된다. 오늘은 코딩 테스트에서 자주 등장하는 자료구조인 그래프에 대해 알아보도록 하겠다.  그래프 (Graph) 정의 그래프(Graph): 노드와 간선으로 이루어진 자료구조 그래프는 데이터 구조의 일종으로, 객체 간의 관계를 나타내는 데 사용된다.노드(Node, 또는 Vertex)와 간선(Edge)으로 구성되며, 두 노드 간의 연결을 나타낸다.주로 소셜 네트워크 및 지도 경로 탐색, 웹 페이지 간의 링크 구조, 게임 월드 맵 등에 주로 사용된다. 💡  노드(Node): 그래프에서..

완전 탐색과 백트래킹은 코딩 테스트에서 중요한 탐색 기법으로, 문제에서 가능한 모든 경우의 수를 고려하여 최적의 해답을 찾는 데 사용된다. 오늘은 완전 탐색과 백트래킹이 어떤 개념인지 알아보도록 하겠다. 완전 탐색 (Brute Force)  완전 탐색(Brute Force)은 모든 가능한 경우를 무식하게 하나하나 다 확인하는 방식으로 문제를 해결한다. 가능한 모든 조합, 모든 배열 등을 전부 시도해본 뒤 조건에 맞는 결과를 찾는다.따라서 완전 탐색은 가장 단순한 방법이지만, 시간 복잡도가 클 수 있으니 입력의 크기를 잘 확인해야 한다. 간단한 문제로 확인해보겠다.   백준 2309번: 일곱 난쟁이https://www.acmicpc.net/problem/2309 ✅ 코드 확인더보기#include #incl..

순열과 조합은 코딩 테스트에서 자주 등장하는 개념으로, 데이터를 나열하거나 선택하는 문제를 해결하는 데 필수적이다.  이러한 개념을 이해하고 활용하면 효율적인 알고리즘 설계와 문제 해결에 큰 도움이 된다. 오늘은 순열과 조합에 대해 개념과 코드에 대해 알아보도록 하겠다. 순열(permutation) 순열(permutation): 여러 개의 요소를 특정 순서에 따라 배열하는 경우의 수  예를 들어, 3개의 숫자 1, 2, 3을 모두 사용해 순열을 구하는 경우 P(3, 3) = 3! = 6이 되어 6가지 경우의 수가 나온다.- (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) 시간 복잡도는 얼마일까?O(n!)이다. n개의 요소가 있다면 첫 번..

최근 개발자들이 취업을 준비할 때 필수 관문이 된 코딩 테스트에서 다양한 언어들이 사용되지만, 그중에서도 많은 개발자들이 C++을 선호하는 경향이 있다. 오늘은 C++이 코딩 테스트에서 유리한 이유과 장점에 대해서 분석해보도록 하겠다. 빠른 실행 속도 C++의 실행 속도는 다른 언어에 비해 상당히 빠른 편이다. 일반적인 알고리즘 문제의 경우, Python보다 약 10 ~ 100배 정도 빠른 실행 속도를 보이며, Java보다 약 1.2 ~ 2배 정도 빠른 것으로 평가된다. 특히 수백만 개의 반복 연산이나 대규모 데이터 구조를 다룰 때 속도 차이가 두드러진다.  C++은 컴파일 시점에 기계어 코드로 변환되므로, 실행 시간에는 기계어 수준에서 곧바로 연산이 이루어진다. 반면 Python과 같은 인터프리터 언어..

최소 신장 트리(MST: Minimum spanning tree)는 그래프에서 모든 노드를 연결할 때 사용된 Edges의 가중치의 합을 최소로 하는 트리를 의미한다. MST의 특징은 다음과 같다. 사이클을 포함하지 않는다. (사이클이 포함되면 가중치의 합이 최소가 될 수 없는 모순 발생) N개의 노드가 있다면 Edge의 개수는 N-1개다. MST를 구할 때 사용하는 알고리즘은 다음과 같다. 크루스칼(kruskal) 알고리즘 프림(Prim) 알고리즘 이 포스터에선 크루스칼 알고리즘으로 MST를 구현해보도록 하겠다. MST: 크루스칼 알고리즘 크루스칼 알고리즘으로 MST를 구할 땐 Union-Find 알고리즘을 사용한다. Union-Find 알고리즘에 대해 익숙하지 않다면 아래 포스터를 참고하자. https..

플로이드-워셜(Floyd-warshall) 알고리즘은 모든 노드에 대해 그래프에서 최단 거리를 구하는 알고리즘이다. 이 알고리즘의 특징은 다음과 같다. 음수 가중치가 있어도 수행할 수 있다. 동적 계획법(Dynamic Programming) 원리를 따른다. 시간 복잡도는 O(V ^ 3)으로 많이 느린 편에 속한다. 그래서 N이 1000개 이상인 경우에는 사용하기 어렵다. 플로이드-워셜 자료구조 먼저 그래프를 표현할 인접 행렬이 필요하다. 인접 행렬은 2개의 노드 인덱스와, 1개의 거리 요소로 구성되어 있다. 이 자료구조 하나로 플로이드-워셜 알고리즘을 구현할 수 있다. 플로이드-워셜 원리 플로이드-워셜의 핵심 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존..