BFS (너비 우선 탐색):
BFS는 그래프 탐색 알고리즘으로, 그래프의 모든 정점을 너비 우선 순서로 탐색합니다. 시작 정점에서 인접한 정점들을 모두 방문한 후에 다음 레벨의 정점들을 방문합니다. 이 알고리즘은 큐 자료 구조를 사용하여 방문할 정점을 추적합니다.
예제: A, B, C, D, E, F, G라는 정점들과 A-B, A-C, B-D, B-E, C-F, E-G라는 간선으로 연결된 그래프가 있다고 가정해봅시다. 정점 A에서 BFS를 시작하면 탐색 순서는 A, B, C, D, E, F, G가 됩니다.
DFS (깊이 우선 탐색):
DFS는 그래프 탐색 알고리즘으로, 그래프의 모든 정점을 깊이 우선 순서로 탐색합니다. 시작 정점에서 가능한 한 멀리까지 이동한 후에 되돌아와 다른 경로를 탐색합니다. 이 알고리즘은 스택 자료 구조나 재귀를 사용하여 방문할 정점을 추적합니다.
예제: 위에서 사용한 그래프에서 정점 A에서 DFS를 시작하면 탐색 순서는 A, B, D, E, G, C, F가 됩니다.
DSU (서로소 집합 자료 구조):
DSU는 서로소(공통 원소가 없는) 집합들의 모음을 관리하는 자료 구조입니다. 두 집합을 합치거나 두 원소가 같은 집합에 속하는지 확인하는 효율적인 연산을 제공합니다.
예제: 초기에 원소로 {1, 2, 3, 4, 5}를 개별 집합으로 나누었다고 가정해봅시다. {1, 2}와 {3, 4} 두 집합을 합쳐 {1, 2, 3, 4}라는 하나의 집합으로 만들거나, 원소 2와 3이 같은 집합에 속하는지 확인할 수 있습니다.
FFT (고속 푸리에 변환):
FFT는 시퀀스의 이산 푸리에 변환(DFT) 또는 그 역변환(역 FFT)을 효율적으로 계산하기 위한 알고리즘입니다. 이 알고리즘은 신호 처리나 데이터 압축 등 다양한 분야에서 시간 영역 신호를 주파수 영역 표현으로 변환하는 데 사용됩니다.
예제: 복소수 순서열 [1, 2, 3, 4]가 주어진 경우, FFT를 적용하여 주파수 영역 표현을 얻을 수 있습니다.
KMP (커누스-모리스-프랫 알고리즘):
KMP는 문자열 매칭 알고리즘으로, 긴 텍스트에서 패턴의 발생을 효율적으로 찾아냅니다. 패턴의 구조에 대한 정보를 활용하여 불필요한 비교를 피하고, 다음 비교가 시작되어야 할 위치를 결정하는 방식으로 동작합니다.
예제: "ABABABACABA"라는 텍스트 문자열과 그 안에서 "ABAC" 패턴을 찾고자 한다면, KMP 알고리즘을 사용하여 패턴이 텍스트에서 발생하는 위치를 찾을 수 있습니다.
게임:
게임은 사용자 또는 여러 플레이어가 참여하여 규칙에 따라 경쟁하거나 협력하는 활동을 말합니다. 게임은 다양한 장르와 종류가 있으며, 컴퓨터 게임, 보드 게임, 카드 게임 등 다양한 형태로 존재합니다. 게임은 즐기는 데 중점을 두지만, 목표를 달성하거나 승리를 차지하기 위한 전략과 기술을 요구하기도 합니다.
예제: 체스는 전략적인 보드 게임으로, 두 명의 플레이어가 서로의 말을 잡거나 상대편의 왕을 체크메이트(패배 상태)시키기 위해 움직이는 것입니다.
구간합:
구간합은 배열이나 리스트 등에서 주어진 구간 내의 원소들의 합을 계산하는 것을 말합니다. 구간합은 데이터 처리나 알고리즘 문제에서 자주 사용되며, 미리 구간 합을 계산해놓으면 특정 구간의 합을 빠르게 구할 수 있습니다.
예제: 배열 [1, 2, 3, 4, 5, 6, 7]이 주어진 경우, 2번째 원소부터 5번째 원소까지의 구간합은 2 + 3 + 4 + 5 = 14가 됩니다.
구현:
구현은 컴퓨터 프로그래밍에서 알고리즘 또는 기능을 실제로 코드로 작성하는 과정을 말합니다. 알고리즘을 구체적인 프로그래밍 언어로 변환하거나 원하는 기능을 구현하는 것을 의미합니다.
예제: 정렬 알고리즘을 구현한다면, 선택 정렬, 삽입 정렬, 퀵 정렬 등의 알고리즘을 선택하고 해당 알고리즘을 프로그래밍 언어로 구현합니다.
그래프:
그래프는 정점들과 그 사이의 연결 관계를 나타내는 자료 구조입니다. 그래프는 네트워크, 도로망, 소셜 네트워크 등 다양한 시스템을 모델링하고 분석하는 데 사용됩니다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성되며, 간선은 정점들 사이의 관계를 나타냅니다.
예제: 친구 관계를 그래프로 표현한다면, 각 사람을 정점으로 표현하고 친구 관계를 간선으로 표현할 수 있습니다.
그리디:
그리디(Greedy) 알고리즘은 각 단계에서 가장 최적인 선택을 하는 알고리즘입니다. 그리디 알고리즘은 각 선택이 지역적으로 최적이지만, 전체적인 최적해를 보장하지는 않을 수 있습니다.
예제: 거스름돈을 줄 때, 가장 큰 단위의 동전부터 사용하여 거스름돈을 주는 것은 그리디 알고리즘의 한 예입니다.
네트워크 플로우:
네트워크 플로우(Network Flow)는 그래프에서 한 정점에서 다른 정점으로 데이터가 흐르는 문제를 다루는 알고리즘입니다. 네트워크 플로우 알고리즘은 최대 흐름, 최소 컷 등을 계산하는 데 사용됩니다.
예제: 최대 유량 문제에서, 한 정점에서 다른 정점으로의 최대 데이터 전송량을 계산하는 것이 네트워크 플로우 알고리즘의 예입니다.
누적합:
누적합(Prefix Sum)은 배열이나 리스트에서 각 위치까지의 원소들의 합을 미리 계산하여 저장한 배열을 말합니다. 누적합을 구해놓으면 특정 구간의 합을 빠르게 구할 수 있습니다. 누적합은 구간합 문제를 효율적으로 해결하는 데 사용됩니다.
예제: 배열 [1, 2, 3, 4, 5, 6, 7]이 주어진 경우, 누적합을 계산하여 [1, 3, 6, 10, 15, 21, 28]과 같이 저장할 수 있습니다. 이때, 2번째 원소부터 5번째 원소까지의 구간합은 누적합에서 5번째 원소의 값을 빼고 1번째 원소의 값을 빼면 구할 수 있습니다.
다이나믹 프로그래밍:
다이나믹 프로그래밍(Dynamic Programming)은 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 부분 문제의 해답을 계산하고 저장하여 중복 계산을 피하며, 이를 활용하여 전체 문제의 해답을 도출합니다. 다이나믹 프로그래밍은 부분 문제의 최적해를 구하는 상향식 접근법을 사용합니다.
예제: 피보나치 수열을 다이나믹 프로그래밍으로 계산한다면, 이전의 두 항의 값을 더하여 다음 항을 계산하는 방식으로 전체 수열을 구할 수 있습니다.
링크드 리스트:
링크드 리스트(Linked List)는 데이터의 연속된 나열을 나타내는 자료 구조입니다. 각 데이터는 노드(Node)라고 부르는 객체로 구성되며, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있습니다. 링크드 리스트는 삽입과 삭제가 상대적으로 빠르며, 크기를 동적으로 조정할 수 있는 장점이 있습니다.
예제: 단순 연결 리스트(Singly Linked List)에서 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다. 이를 사용하여 데이터를 순차적으로 저장하고 탐색할 수 있습니다.
문자열:
문자열은 문자들의 나열을 나타내는 데이터 타입입니다. 문자열은 텍스트 데이터를 다루는 데 사용되며, 문자열의 길이와 문자에 접근하는 기능을 제공합니다. 문자열은 작은 따옴표('') 또는 큰 따옴표("")로 감싸서 표현합니다.
예제: "Hello, World!"라는 문자열은 문자 'H', 'e', 'l', 'l', 'o', ',', ' ', 'W', 'o', 'r', 'l', 'd', '!'의 나열을 나타냅니다.
배열:
배열(Array)은 동일한 데이터 타입의 원소들을 순차적으로 저장하는 자료 구조입니다. 배열은 인덱스를 사용하여 각 원소에 접근할 수 있으며, 연속된 메모리 공간에 원소들을 저장합니다. 배열의 크기는 미리 정의되어야 하며, 크기를 변경하기 어렵습니다.
예제: 정수형 배열 [1, 2, 3, 4, 5]는 0부터 4까지의 인덱스를 사용하여 각 원소에 접근할 수 있습니다.
백트래킹:
백트래킹(Backtracking)은 해를 찾는 도중에 가능성이 없는 경우를 배제하면서 탐색하는 알고리즘입니다. 주로 재귀적인 방법을 통해 구현되며, 한 단계씩 진행하다가 더 이상 진행할 수 없는 경우 되돌아가 다른 가능성을 탐색합니다. 백트래킹은 조합 문제, 스도쿠, N-Queen 문제 등에서 활용됩니다.
예제: N-Queen 문제에서 백트래킹을 사용하여 N개의 퀸을 서로 공격할 수 없는 위치에 배치하는 방법을 찾을 수 있습니다.
분할정복:
분할정복(Divide and Conquer)은 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 문제를 더 이상 나눌 수 없을 때까지 나누고, 각 부분 문제의 해답을 구한 뒤, 이를 결합하여 전체 문제의 해답을 얻습니다. 분할정복은 재귀적인 방식으로 구현되며, 대표적인 예로 병합 정렬, 퀵 정렬 등이 있습니다.
예제: 병합 정렬은 분할정복 기법을 사용하여 배열을 분할하고 정렬한 후, 합병하여 전체 배열을 정렬하는 알고리즘입니다.
비트:
비트(Bit)는 컴퓨터에서 데이터의 가장 작은 단위로, 0과 1의 값을 가집니다. 비트는 정보의 저장과 처리에 사용되며, 이진수 표현을 통해 데이터를 표현합니다. 비트 연산은 논리 연산이나 비트 단위의 이동, 비트마스크 등 다양한 작업에 활용됩니다.
예제: 10진수 숫자 5는 이진수로 101로 표현됩니다. 이때, 비트 연산을 사용하여 5의 이진 표현에서 특정 비트를 변경하거나 확인할 수 있습니다.
비트마스크:
비트마스크(Bitmask)는 이진수의 특정 비트를 활용하여 집합의 부분 집합을 나타내는 기법입니다. 각 비트가 집합의 원소에 대응되며, 0 또는 1로 표시하여 해당 원소의 포함 여부를 나타냅니다. 비트마스크는 집합 연산이나 조합을 효율적으로 처리하는 데 사용됩니다.
예제: 정수 5를 비트마스크로 표현하면 101이 되며, 이는 집합 {1, 3}을 나타냅니다. 비트 연산을 사용하여 비트마스크로 표현된 집합의 연산을 수행할 수 있습니다.
사고력:
사고력은 문제 해결 능력과 창의성을 의미합니다. 문제를 이해하고 분석하여 적절한 접근 방법을 도출하고, 다양한 가능성을 고려하여 문제를 해결하는 능력입니다. 사고력은 문제 해결 능력을 향상시키고, 새로운 아이디어나 해결책을 발견하는 데 도움을 줍니다.
세그먼트 트리:
세그먼트 트리(Segment Tree)는 구간에 대한 질의를 효율적으로 처리하기 위한 자료 구조입니다. 배열의 구간 합, 최소값, 최대값 등의 연산을 빠르게 수행할 수 있습니다. 세그먼트 트리는 트리 구조로 구성되며, 각 노드는 구간의 정보를 담고 있습니다.
예제: 세그먼트 트리를 사용하여 배열의 구간 합을 계산한다면, 주어진 구간에 해당하는 노드를 탐색하고, 구간 합을 계산하여 반환할 수 있습니다.
